Пусть имеется задача классификации f(x) = y, x∈Nn, y∈{0,1}.
Требуется написать программу, строящую классификатор методом градиентного бустинга,
используя в качестве базовой модели OneRuleрегрессор.
Получаемый классификатор имеет вид F(x) = 11 + e − H(x),
где H(x) = h0 + k∑i = 1hi(x), 1⩽ k⩽ n,
h0 — независимое приближение, hi обученные OneRuleрегрессоры.
В качестве функции ошибки используется
L(y, F(x)) = − (ylog(F(x)) + (1 − y)log(1 − F(x))).
При построении классификатора необходимо использовать следующий алгоритм
Входные данные:
X = {xj}, xj∈Nn — список значений признаков примеров обучающий выборки,
y = {yj}, yj∈{0, 1} — список значений классов обучающей выборки,
k∈N, k⩽ n — количество базовых регрессоров.
Алгоритм:
Обозначить
m = |y| — количество примеров выборки
I = {i|i = 1,n} — номера доступных для использования признаков;
Tl = {Xj,l|j = 1,m} — уникальные значения признака с номером l;
I = I∖{l}, где l — номер признака, на котором был обучен лучший регрессор;
Fk — искомый классификатор
Формат входных данных
Первая строка входного файла содержит натуральные числа m,n,k — количество примеров, признаков и базовых регрессоров соответственно. В следующих m строках содержится n + 1 целое число — значения признаков и номер класса примера. Гарантируется, что уникальные значения каждого признака образуют множество {i|i∈0,s − 1}.
Формат выходных данных
Первая строка выходного файла должна содержать независимое приближение h0. В следующих k строках необходимо вывести описания базовых регрессоров — номер признака, на котором был обучен регрессор, и список предсказываемых регрессором значений в порядке возрастания значения признака. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.
Пусть заданы 4 набора точек: squares, circles, moons, spirals,
которые можно скачать здесь.
Требуется на языке Python реализовать 4 функции,
преобразующие соответствующие наборы точек так,
чтобы они были идеально разделимы линейным
методом опорных векторов,
а именно sklearn.svm.SVC(kernel='linear').
Спектакль многомерного театра теней проходит следующим образом
При подготовке сцены устанавливают l полупрозрачных экранов, с использованием которых будет происходить действие спектакля;
n актёров располагаются по разные стороны экранов так, что те, кто находится за экраном видны как тени. Так как экранов несколько, актёры могут быть видны по-разному в зависимости от расположения экрана с которого зритель наблюдает спектакль.
Театр существует уже очень давно, поэтому руководство приказало изменить спектакль, чтобы привлечь больше зрителей. Так как актёры не хотят изучать новые действия, было принято решение изменить их расположение относительно экрана с номером k, то есть те, кто находился за экраном, должны теперь оказаться перед ним, и наоборот. Однако при этом положение актёров относительно других экранов должно остаться прежним. Театр обратился к Вам с этой задачей, но скрыл расположение экранов, чтобы избежать раскрытия всех секретов спектакля, согласившись лишь предоставить информацию о том, с какой стороны экранов находится каждый из актёров. Работа будет принята, если правила расположения будут нарушены не более чем у 5% актёров.
Формат входных данных
Первая строка входного файла содержит натуральные числа n, m, l, k — количество актёров, размерность пространства, количество экранов и индекс, для которого нужно изменить расположение. В следующих n строках содержится по m вещественных чисел — текущее положение актёра, и l чисел 0 или 1 — положение актёра относительно экрана.
Формат выходных данных
Выходной файл должен содержать n строк по m вещественных чисел — новые положения актёров. Так как размер файла может оказаться очень большим, числа необходимо выводить не более чем с тремя знаками после запятой.
Требуется реализовать на языке Python набор функций, выполняющие этапы применения оператора Кэнни:
import numpy as np
from typing import Tuple
def gaussian_blur(img: np.ndarray, kernel: Tuple[int, int], sigma: float) -> np.ndarray:
'''Blurs an image using Gaussian filter.
Arguments:
img: input image, a 2d np.ndarray.
kernel: gaussian kernel size.
sigma: gaussian kernel standard deviation.
Returns:
Blurred image, a 2d np.ndarray of the same size and dtype as `img`.
'''
pass
def magnitude_and_direction(img: np.ndarray, kernel: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
'''Applies a filter to the image and computes magnitude and direction of the gradient.
The filter is applied using 'reflect' mode for border pixels, i.e. dcb|abcd|cba
Arguments:
img: input image, a 2d np.ndarray.
kernel: the filter kernel, a 2d np.ndarray with odd dimension sizes.
The kernel is applied over x dimension, kernel.T is applied over y
Returns:
Magnitude and direction of the gradient, two 2d np.ndarray objects of the same size and dtype as `img`.
The direction values lie in range [0, 2 * pi].
'''
pass
def edge_thinning(magnitude: np.ndarray, direction: np.ndarray) -> np.ndarray:
'''Performs edge thinning step of Canny algorithm using 0°, 45°, 90°, 135°, 180° (=0°) gradient direction
as described here https://en.wikipedia.org/wiki/Canny_edge_detector#Gradient_magnitude_thresholding_or_lower_bound_cut-off_suppression.
If the angle is equally close to two groups, the group with lower angle value is selected.
Arguments:
magnitude: magnitude of image gradient, a 2d np.ndarray.
direction: direction of image gradient, a 2d np.ndarray.
Returns:
Boolean mask of suppressed pixels (False if a pixel is suppresed, True if preserved), a 2d np.ndarray of the same size as `magnitude` and dtype bool.
'''
pass
def edge_tracking(magnitude: np.ndarray, mask: np.ndarray, low_threshold: float, high_threshold: float) -> np.ndarray:
'''Performs edge tracking step of Canny algorithm. The thresholds are inclusive.
Arguments:
magnitude: magnitude of image gradient, a 2d np.ndarray.
mask: pixel suppression mask, obtained by edge_thinning function.
low_threshold: weak pixel threshold.
high_threshold: strong pixel threshold.
Returns:
A 2d np.ndarray of the same size as `magnitude` and dtype bool, representing detected edges.
'''
pass
Формат выходного файла
Код решения должен содержать только импортируемые модули, определение и реализацию функций.
Требуется реализовать на языке Python функцию, выполняющую классическое преобразование Хаффа для поиска прямых. Функция должна иметь следующий интерфейс
import numpy as np
from typing import List, Tuple
def hough_lines(
image: np.ndarray,
rho: float,
theta: float,
threshold: int,
min_theta: float = 0,
max_theta: float = np.pi) -> list[tuple[float, float, int]]:
"""Finds lines in a binary image using the standard Hough transform.
Arguments:
image: 2d np.ndarray of bool
rho: distance resolution
theta: angle resolution
theshold: only lines with votes > `threshold` are returned
min_theta: minimal angle value
max_theta: maximal angle value
Returns:
lines: a list of tuples (distance, angle, votes), detected lines sorted by votes in descending order
"""
pass
При реализации функции сетка по расстоянию должна строиться на интервале [ − (w + h), w + h + rho). При построении аккумулятора голос отдаётся за расстояние, округлённое к ближайшему индексу (round half to even). После построения аккумулятора должна проводиться его фильтрация согласно правилу âi,j = {ai,j,ai − 1,j< ai,j,ai,j − 1< ai,j,ai + 1,j⩽ ai,j,ai,j + 1⩽ ai,j0,else..
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Формат входных данных
Аргументы функции:
image: двумерный массив булевых значений
rho: разрешающая способность аккумулятора по расстоянию
theta: разрешающая способность аккумулятора по углу
threshold: возвращает прямые, для которых количество голосов больше `threshold`
min_theta: минимальный рассматриваемый угол
max_theta: максимальный рассматриваемый угол
Формат выходных данных
Функция возвращает список троек (расстояние, угол, количество голосов) для каждой прямой в порядке убывания по количеству голосов.
Ограничения
Гарантируется, что 0⩽ min_theta⩽ max_theta⩽π.
Примеры тестов
№
Стандартный вход
Стандартный выход
1
lines.jpgimage = cv2.Canny(cv2.imread('lines.jpg'), 500, 550).astype(bool)
print(*(f'{i} {j:.3f} {k}' for i, j, k in hough_lines(image, 1, np.pi / 360, 210)), sep='\n')
Требуется реализовать на языке Python функцию, выполняющую преобразование Хаффа для поиска окружностей. Функция должна иметь следующий интерфейс
import numpy as np
from typing import List, Tuple
def hough_circles(
image: np.ndarray,
accumulator_resolution: float,
min_distance: int,
canny_threshold: int,
center_threshold: int,
radius_threshold: int,
min_radius: int,
max_radius: int) -> List[Tuple[float, float, float, int]]:
"""Finds circles in a gray image using Hough transform
Arguments:
image: 2d np.ndarray of float
accumulator_resolution: step size for accumulators
min_distance: minial distance between circle centers
canny_threshold: upper threshold for Canny edge detector
center_threshold: minimal number of votes for a center to be accepted
radius_threshold: minimal number of votes for a radius to be accepted
min_radius: minimal circle radius
max_radius: maximal circle radius
Returns:
circles: a list of tuples (x, y, radius, votes), detected circles sorted by votes in descending order
"""
pass
При построении аккумуляторов, голос отдаётся за индекс, округлённый к ближайшему целому (rounding half to even).
После построения аккумулятора для центров окружностей должна проводиться его фильтрация согласно правилу âi,j = {ai,j,ai − 1,j< ai,j,ai,j − 1< ai,j,ai + 1,j⩽ ai,j,ai,j + 1⩽ ai,j0,else..
При выборе радиуса окружности лучшим считается такой радиус r с количеством голосов c, для которого частное cr является максимальным.
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Формат входных данных
Аргументы функции:
image: двумерный массив чисел с плавающей точкой, чёрно-белое изображение
accumulator_resolution: разрешающая способность аккумуляторов
min_distance: минимально допустимое расстояние между центрами окружностей
canny_threshold: верхний порог алгоритма Кэнни, нижний порог считать равным canny_threshold / 2
center_threshold: минимальное количество голосов для принятия центра
radius_threshold: минимальное количество голосов для принятия радиуса
Требуется реализовать на языке Python класс, описывающий полносвязный слой нейронной сети:
import numpy as np
from typing import Optional, Tuple, Union
class Dense:
"""Implements fully-connected layer"""
def __init__(self, n_in: int, n_out: int, use_bias: bool = True):
"""Initializes Dense layer.
The weights are initialized using uniformly distributed values in range [-1, 1]. Bias vector is not initialized if `use_bias` is False.
Weigths matrix has the shape (`n_in`, `n_out`), bias vector has the shape (`n_out`, ).
Arguments:
n_in: Positive integer, dimensionality of input space.
n_out: Positive integer, dimensionality of output space.
use_bias: Whether the layer uses a bias vector."""
pass
@property
def weights(self) -> tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]:
"""Returns weights used by the layer."""
pass
@property
def input(self) -> np.ndarray:
"""Returns the last input received by the layer"""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Performs the layer forward pass.
Arguments:
x: Input array of shape (`batch_size`, `n_in`)
Returns:
An array of shape (`batch_size`, `n_out`)"""
pass
def grad(self, gradOutput: np.ndarray) -> tuple[np.ndarray, tuple[np.ndarray, np.ndarray]] | tuple[np.ndarray, tuple[np.ndarray]]:
"""Computes layer gradients
Arguments:
gradOutput: Gradient of loss function with respect to the layer output, an array of shape (`batch_size`, `n_out`).
Returns:
A tuple object:
Gradient of loss function with respect to the layer input, an array of shape (`batch_size`, `n_in`)
Gradient of loss function with respect to the layer's weights:
An array of shape (`n_in`, `n_out`).
Optional array of shape (`n_out`, )."""
pass
Для реализации класса разрешено использовать только модуль numpy.
Формат выходных данных
Код решения должен содержать только импортируемые модули, определение и реализацию класса.
Требуется реализовать на языке Python класс, описывающий двумерный свёрточный слой нейронной сети:
import numpy as np
class Conv2D:
"""Implements 2d convolution layer"""
def __init__(self,
n_in: int,
n_out: int,
kernel_size: tuple[int, int],
strides: tuple[int, int] = (1, 1),
padding: str = 'valid',
use_bias: bool = True,
dilations: tuple[int, int] = (1, 1)
):
"""Initialized Conv2D layer.
The weights are initialized using uniformly distributed values in range [-1, 1]. Bias vector is not initialized if `use_bias` is False.
Weights tensor has the shape (`kernel_size[0]`, `kernel_size[1]`, `n_in`, `n_out`), bias vector has the shape (`n_out`, ).
Arguments:
n_in: Positive integer, dimensionality of input space.
n_out: Positive integer, dimensionality of output space.
kernel_size: Pair of positive integers, convolution kernel dimensions.
strides: Pair of positive integers, convolution strides along each dimension.
padding: Either 'valid' or 'same', padding to be used by the layer, see explanation below.
use_bias: Whether the layer uses a bias vector.
dilations: Pair of positive integers, convolution kernel dilations along each dimension.
Padding:
'valid': no padding is applied.
'same': padding along every dimension is computed as follows
if dimension_size % stride == 0:
total_pad = max((kernel_size - 1) * dilation + 1 - stride)
else:
total_pad = max((kernel_size - 1) * dilation + 1 - dimension_size % stride)
pad_before = total_pad // 2
pad_after = total_pad - pad_before"""
pass
@property
def weights(self) -> tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]:
"""Returns weights used by the layer. Weight tensor and bias vector if use_bias is True"""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Performs the layer forward pass.
Arguments:
x: Input array of shape (`batch_size`, `height`, `width`, `n_in`).
Returns:
An array of shape (`batch_size`, `new_height`, `new_width`, `n_out`)."""
pass
def grad(self, x: np.ndarray, gradOutput: np.ndarray) -> tuple[np.ndarray, tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]]:
"""Computes layer gradients
Arguments:
gradOutput: Gradient of loss function with respect to the layer output, an array of shape (`batch_size`, `new_height`, `new_width`, `n_out`).
Returns:
A tuple object:
Gradient of loss function with respect to the layer input, an array of shape (`batch_size`, `height`, `width`, `n_in`)
Gradient of loss function with respect to the layer's weights:
An array of shape (`kernel_size[0]`, `kernel_size[1]`, `n_in`, `n_out`).
Optional array of shape (`n_out`, )."""
pass
Для реализации класса разрешено использовать только модуль numpy.
Формат выходных данных
Код решения должен содержать только импортируемые модули, определение и реализацию класса.
Требуется решить задачу классификации табличных данных с использованием изученных моделей машинного обучения.
Требования к датасету
Датасет должен иметь табличный формат (каждый пример задаётся списком признаков и значением целевой переменной).
Датасет должен быть предназначен для задачи классификации.
Датасет должен содержать не менее 5k строк.
Перед использованием датасет должен быть согласован с преподавателем.
Каждый датасет может быть использован не более чем двумя студентами в группе.
Модели машинного обучения
Требуется использовать следующие модели машинного обучения:
OneRule,
Логистическая регрессия,
k ближайших соседей,
Байесовский классификатор,
Деревья решений,
Бустинг,
Метод опорных векторов,
Многослойный перцептрон,
Ансамбль.
Распределение баллов
Максимальное количество баллов за задачу — 10.
Обучение моделей, до + 5
Тестирование моделей: метрики качества (accuracy, f1, roc auc), график confusion matrix, roc auc, до + 3
Исследование важности признаков и оценка их влияния на предсказание, до + 2
Отправка решения
В качестве решения принимается файл с исходным кодом, например jupyter notebook. В систему требуется отправить ссылку на файл, размещённый в открытом доступе (Google Colab, Github, Google Drive и др.), указав среду разработки "Answer text". После отправки решение необходимо сдать преподавателю лично до начала зачётной недели.
Экзамен проводится очно. В случае невозможности очного присутствия необходимо заранее договориться с преподавателем о дистанционной сдаче.
После взятия билета студент готовится в ответу. При подготовке можно использовать произвольные материалы и доступ в Интернет.
В докладе необходимо максимально кратко упомянуть все важные элементы доставшейся темы/вопроса. После доклада преподаватель задаёт несколько уточняющих вопросов.
