Задача 01A. Entropy

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке Python функцию, вычисляющую значение энтропии заданной выборки.

entropy(y) =  − v = set(y)p(v)log p(v)

где set(y) — множество уникальных значений вектора y.


import numpy as np

def entropy(y: np.ndarray) -> float:
    """Computes entropy value for labels `y`.
    
    Arguments:
        y: 1d array of integers, sample labels
        
    Returns:
        float, entropy value for labels `y`"""
    pass

Функция принимает единственный параметр y — одномерный np.array, значения классов в обучающей выборке.

При решении задачи следует использовать натуральный логарифм.

Формат выходных данных

Код должен содержать только реализацию функции. Запрещено пользоваться любыми готовыми реализациями вычисления функции entropy.


Задача 01B. Gini

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке Python функцию, вычисляющую значение gini impurity заданной выборки.

gini(y) = 1 − v = set(y)p2(v)

где set(y) — множество уникальных значений вектора y.


import numpy as np

def gini(y: np.ndarray) -> float:
    """Computes gini impurity value for labels `y`.
    
    Arguments:
        y: 1d array of integers, sample labels
        
    Returns:
        float, gini impurity value for labels `y`"""
    pass

y — одномерный np.array — значения классов в выборке

Формат выходных данных

Код должен содержать только реализацию функции. Запрещено пользоваться любыми готовыми реализациями вычисления функции gini.

Примеры тестов

Стандартный вход Стандартный выход
1
3 2 4 4 2 0 1 3 0 1
0.8

Задача 01C. Decision tree split

Входной файл:Стандартный вход   Ограничение времени:10 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать следующие функцию на языке Python.


def tree_split(X, y, criterion)   # col, row of best split

X — двумерный np.array — обучающая выборка

y — одномерный np.array — значения классов в обучающей выборке

criterion — строковое значение — вид критерия 'var', 'gini' или 'entropy'

tree_split должен возвращать номер признака и номер значения из обучающей выборки, которое будет использоваться в качестве порогового

Таким образом, tree_split возвращает наилучшее бинарное разделение по правилу вида xcol ≤ X[row, col]

Формат выходных данных

Код должен содержать только реализацию функции.


Задача 02A. OneRule boosting

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Пусть имеется задача классификации f(x) = yxNny{0,1}. Требуется написать программу, строящую классификатор методом градиентного бустинга, используя в качестве базовой модели OneRule регрессор. Получаемый классификатор имеет вид F(x) = 11 + e − H(x), где H(x) = h0 + ki = 1hi(x), 1⩽ k⩽ n, h0 — независимое приближение, hi обученные OneRule регрессоры. В качестве функции ошибки используется L(y, F(x)) =  − (ylog(F(x)) + (1 − y)log(1 − F(x))).

При построении классификатора необходимо использовать следующий алгоритм

Входные данные:

Алгоритм:

  1. Обозначить
  2. Вычислить независимое приближение h0 = log|{yj|yj∈ y,yj = 1}||{yj|yj∈ y,yj = 0}|;
  3. Обозначить H0(x) = h0F0(x) = 11 + e − H0(x);
  4. Для каждого i = 0, k − 1
    1. Вычислить остатки ri,j =  − ∂ L(yj, Fi(Xj))∂ F(Xj) = yj − Fi(Xj), j = 1,m;
    2. Обучить OneRule регрессоры на остатках, R = {{trt |t∈ Tl,rt = {ri,j|Xj,l = t}} | l∈ I};
    3. Выбрать лучший регрессор h = arg minh∈ R{mj = 1(ri,j − h(xj))2m};
    4. Обозначить
      • hi + 1 = {tsum(rt)sum(Pt)|(t, rt)∈ h,Pt = {Fi(Xj)(1 − Fi(Xj))|Xj,l = t}};
      • Hi + 1(x) = Hi(x) + hi + 1(x);
      • Fi + 1(x) = 11 + e − Hi + 1(x);
      • I = I{l}, где l — номер признака, на котором был обучен лучший регрессор;
  5. Fk — искомый классификатор

Формат входных данных

Первая строка входного файла содержит натуральные числа m,n,k — количество примеров, признаков и базовых регрессоров соответственно. В следующих m строках содержится n + 1 целое число — значения признаков и номер класса примера. Гарантируется, что уникальные значения каждого признака образуют множество {i|i0,s − 1}.

Формат выходных данных

Первая строка выходного файла должна содержать независимое приближение h0. В следующих k строках необходимо вывести описания базовых регрессоров — номер признака, на котором был обучен регрессор, и список предсказываемых регрессором значений в порядке возрастания значения признака. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.

Ограничения

10⩽ m⩽ 1750

5⩽ n⩽ 6034n⩽ k⩽ n

3⩽ s50

Примеры тестов

Стандартный вход Стандартный выход
1
10 4 4
2 0 0 0 1
1 2 0 0 0
2 2 0 1 1
0 2 1 0 1
2 0 1 0 1
0 2 0 0 1
0 1 1 0 1
0 2 0 1 0
1 0 0 0 0
1 0 0 1 0
0.405
0 0.625 -2.5 1.667
3 0.813 -1.88
2 -0.113 1.14
1 -0.56 1.05 0.26

Задача 03A. Kernel trick

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Пусть заданы 4 набора точек: squares, circles, moons, spirals, которые можно скачать здесь.

Требуется на языке Python реализовать 4 функции, преобразующие соответствующие наборы точек так, чтобы они были идеально разделимы линейным методом опорных векторов, а именно sklearn.svm.SVC(kernel='linear').


import numpy as np

def transform_squares(X: np.ndarray) -> np.ndarray:
    pass

def transform_circles(X: np.ndarray) -> np.ndarray:
    pass

def transform_moons(X: np.ndarray) -> np.ndarray:
    pass

def transform_spirals(X: np.ndarray) -> np.ndarray:
    pass

При решении задачи запрещено использовать условные операторы и операторы сравнения.

Формат входных данных

Каждая функция принимает двумерный np.array, имеющий размеры (1200, 2). Функции проверяются в порядке их определения в задаче.

Формат выходных данных

Результатом работы функции должен являться двумерный массив преобразованных точек, имеющий тот же размер, что и исходный.


Задача 03B. Многомерный театр теней

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Спектакль многомерного театра теней проходит следующим образом

Театр существует уже очень давно, поэтому руководство приказало изменить спектакль, чтобы привлечь больше зрителей. Так как актёры не хотят изучать новые действия, было принято решение изменить их расположение относительно экрана с номером k, то есть те, кто находился за экраном, должны теперь оказаться перед ним, и наоборот. Однако при этом положение актёров относительно других экранов должно остаться прежним. Театр обратился к Вам с этой задачей, но скрыл расположение экранов, чтобы избежать раскрытия всех секретов спектакля, согласившись лишь предоставить информацию о том, с какой стороны экранов находится каждый из актёров. Работа будет принята, если правила расположения будут нарушены не более чем у 5% актёров.

Формат входных данных

Первая строка входного файла содержит натуральные числа n, m, l, k — количество актёров, размерность пространства, количество экранов и индекс, для которого нужно изменить расположение. В следующих n строках содержится по m вещественных чисел — текущее положение актёра, и l чисел 0 или 1 — положение актёра относительно экрана.

Формат выходных данных

Выходной файл должен содержать n строк по m вещественных чисел — новые положения актёров. Так как размер файла может оказаться очень большим, числа необходимо выводить не более чем с тремя знаками после запятой.

Ограничения

25⩽ n⩽ 7500

10⩽ m⩽ 175

2⩽ l⩽ 5

0⩽ k < l

Примеры тестов

Стандартный вход Стандартный выход
1
25 10 2 0
-0.2 -3.2 -0.5  0.5 -1.6 -3.1  1.0  3.6  2.1 -3.3 1 1
 0.6 -3.0  0.5  0.7 -0.9 -3.4  3.5  2.9  3.8 -2.9 1 1
-0.3 -2.1 -0.3  0.7 -0.4 -3.5  3.7  1.0 -2.8 -2.5 0 1
 0.8 -4.0  0.3 -0.6 -0.0 -3.4  2.6 -3.4 -2.3  1.8 0 0
 0.8 -1.9 -0.2  0.8 -1.4 -2.0  2.1  3.6 -3.3 -3.1 0 1
 0.5 -3.4 -1.2 -1.0  0.2 -2.7  2.9 -2.1  2.9  3.1 1 0
-0.5 -3.6  2.2 -0.2 -1.0 -2.4  2.8 -5.0  3.0  3.0 1 0
 0.6 -1.1 -0.1  0.8 -1.9 -3.2  1.8  2.2 -1.1 -2.6 0 1
-0.6 -5.7 -1.4  0.3  0.6 -2.9  3.8 -7.1  3.0 -0.0 1 0
 0.3 -3.5 -0.4  0.9 -0.3 -2.9  1.8  2.6 -3.3 -2.6 0 1
 0.6 -2.8 -0.6 -0.2  0.1 -3.8  3.6 -2.6  3.8  2.3 1 0
-1.2 -2.5 -0.0  1.6  0.1 -2.9  4.1 -2.2 -3.0  2.3 0 0
-0.1 -2.9  2.5  0.3 -0.2 -1.4  4.6  3.7 -5.4 -2.9 0 1
-0.6 -3.4  0.8  0.2  0.8 -3.6  3.8 -3.4  3.4  2.1 1 0
 1.1 -3.0  0.1 -0.2 -1.1 -3.7  4.6  2.1  4.3 -2.8 1 1
-1.4 -2.2 -1.5  1.4  0.3 -2.7  3.7 -3.3 -3.7  4.8 0 0
-0.7 -2.5 -0.8  0.4 -0.2 -1.9  3.7 -2.3 -3.4  3.4 0 0
-0.6 -2.5  0.4 -0.8  1.9 -2.7  4.3  3.9 -3.7 -3.1 0 1
-2.0 -5.1 -0.9  2.1  1.4 -3.9  1.6 -4.9  2.1  2.0 1 0
-0.6 -2.1 -1.2  1.3  1.1 -2.6  1.0  3.2  1.9 -2.7 1 1
 0.7 -2.8  1.5  0.1 -0.8 -3.9  4.4 -2.3  4.2  2.4 1 0
 0.0 -3.5 -0.3  1.3  0.8 -0.4  2.8  2.3  2.4 -3.1 1 1
-0.4 -2.5 -2.0  0.1 -0.7 -3.8  4.6 -2.0 -4.0  2.4 0 0
 0.0 -3.1  0.3  1.2  0.0 -0.7  4.3 -3.5 -5.2  2.4 0 0
 0.1 -2.1  0.2 -0.0  0.3 -2.1  2.8  1.2 -3.4 -2.3 0 1
 0.7 -1.6 -0.3  0.6 -2.3 -3.4  1.5  3.2 -1.0 -3.4
 1.6 -1.0  0.7  0.9 -1.8 -3.7  4.2  2.4  0.1 -3.0
-0.6 -2.7 -0.4  0.6 -0.1 -3.4  3.5  1.2 -1.6 -2.5
 0.7 -4.2  0.3 -0.6  0.1 -3.4  2.5 -3.3 -1.8  1.8
 0.4 -2.7 -0.3  0.7 -1.0 -1.9  1.8  3.8 -1.8 -3.1
 1.4 -1.7 -1.0 -0.8 -0.6 -3.0  3.5 -2.5 -0.4  3.0
 0.4 -2.0  2.4 -0.1 -1.7 -2.7  3.3 -5.4 -0.1  2.9
 0.5 -1.3 -0.1  0.8 -1.8 -3.2  1.7  2.3 -0.6 -2.6
 0.5 -3.6 -1.2  0.5 -0.4 -3.3  4.5 -7.6 -0.9 -0.1
 0.1 -3.9 -0.4  0.9 -0.1 -2.8  1.7  2.7 -2.6 -2.6
 1.6 -1.0 -0.4 -0.0 -0.7 -4.1  4.2 -3.0  0.4  2.2
-1.5 -3.1 -0.1  1.5  0.4 -2.8  3.9 -2.0 -1.8  2.3
-0.8 -4.3  2.4  0.2  0.4 -1.2  4.1  4.0 -2.8 -2.9
 0.4 -1.5  1.0  0.4 -0.1 -3.9  4.4 -3.9 -0.2  2.0
 2.1 -1.0  0.3 -0.0 -2.0 -4.0  5.3  1.6  0.5 -2.9
-1.9 -3.1 -1.6  1.3  0.7 -2.5  3.4 -3.1 -2.0  4.8
-1.1 -3.3 -0.9  0.3  0.2 -1.8  3.4 -2.1 -1.9  3.4
-0.9 -3.0  0.3 -0.8  2.1 -2.6  4.1  4.0 -2.7 -3.1
-0.9 -3.1 -0.7  2.3  0.5 -4.3  2.3 -5.4 -1.7  1.9
 0.3 -0.5 -1.0  1.4  0.4 -2.9  1.5  2.8 -1.2 -2.8
 1.6 -1.0  1.7  0.3 -1.6 -4.2  5.0 -2.7  0.8  2.3
 1.0 -1.6 -0.1  1.5 -0.1 -0.7  3.4  1.8 -1.2 -3.2
-1.0 -3.7 -2.1 -0.0 -0.2 -3.6  4.2 -1.7 -1.8  2.4
-0.8 -4.6  0.1  1.1  0.7 -0.4  3.8 -3.1 -2.4  2.5
-0.3 -2.8  0.1 -0.1  0.6 -2.0  2.6  1.4 -2.0 -2.3

Задача 04A. Canny

Входной файл:input.jpg   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке 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

Формат выходного файла

Код решения должен содержать только импортируемые модули, определение и реализацию функций.

Примеры тестов

Входной файл (input.jpg) Выходной файл (output.txt)
1

input.jpg
img = cv.imread('input.jpg') img = cv.cvtColor(img, cv.COLOR_BGR2GRAY).astype(float) blur = gaussian_blur(img, (5, 5), 1) magnitude, direction = magnitude_and_direction(blur, np.array([[1, 0, -1], [2, 0, -2], [1, 0, -1]])) mask = edge_thinning(magnitude, direction) edges = edge_tracking(magnitude, mask, 0.1 * np.max(magnitude), 0.2 * np.max(magnitude)) cv.imwrite('sample.png', edges.astype(int) * 255)

sample.png

Задача 04B. Hough Lines

Входной файл:Стандартный вход   Ограничение времени:4 сек
Выходной файл:Стандартный выход   Ограничение памяти:1024 Мб
Максимальный балл:3000  

Условие

Требуется реализовать на языке 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,jai,j,ai,j − 1ai,j,ai + 1,j⩽ ai,j,ai,j + 1⩽ ai,j0,else..

При решении задачи запрещено использовать любые готовые реализации алгоритма.

Формат входных данных

Аргументы функции:

Формат выходных данных

Функция возвращает список троек (расстояние, угол, количество голосов) для каждой прямой в порядке убывания по количеству голосов.

Ограничения

Гарантируется, что 0⩽ min_theta⩽ max_thetaπ.

Примеры тестов

Стандартный вход Стандартный выход
1

lines.jpg
image = 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')
 450 0.314 636
 460 0.314 580
 216 0.785 580
-908 2.635 429
 522 2.094 420
 933 1.370 393
 944 1.370 373
 532 2.094 369
 590 2.199 328
 227 0.785 305
-897 2.635 288
-115 2.915 286
1464 0.646 283
  57 1.815 281
 582 2.199 279
  65 1.815 271
 373 1.274 265
  55 1.815 263
 381 1.274 259
  63 1.815 258
-106 2.915 255
-833 2.801 225
-826 2.793 218
-824 2.801 218
-817 2.793 217
1475 0.646 212

Задача 04C. Hough Circles

Входной файл:Стандартный вход   Ограничение времени:3 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:3000  

Условие

Требуется реализовать на языке 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,jai,j,ai,j − 1ai,j,ai + 1,j⩽ ai,j,ai,j + 1⩽ ai,j0,else..

При выборе радиуса окружности лучшим считается такой радиус r с количеством голосов c, для которого частное cr является максимальным.

При решении задачи запрещено использовать любые готовые реализации алгоритма.

Формат входных данных

Аргументы функции:

Формат выходных данных

Функция возвращает список четвёрок (x, y, радиус, количество голосов) для каждой окружности в порядке убывания по количеству голосов.

Примеры тестов

Стандартный вход Стандартный выход
1

circles.png
image = cv2.cvtColor(cv2.imread('circles.png'), cv2.COLOR_BGR2GRAY) print(*(f'{x} {y} {r} {c}' for x, y, r, c in hough_circles(image, 1, 50, 250, 50, 50, 50, 250)), sep='\n')
301 217 203 143
216 163 100 139
384 273 101 138
352 135 101 131
246 305 100 126

Задача 05A. Dense

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке 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.

Формат выходных данных

Код решения должен содержать только импортируемые модули, определение и реализацию класса.


Задача 05B. Activations

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:18  

Условие

Требуется реализовать на языке Python классы, описывающие различные функции активации:


import numpy as np


class Activation:
    """Base activation class"""

    def __init__(self):
        self._input = None

    @property
    def input(self):
        """Returns the last input received by the activation"""
        return self._input

    def __call__(self, x: np.ndarray) -> np.ndarray:
        """Computes activation output
        
        Arguments:
            x: Input array of shape (`batch_size`, ...)

        Returns:
            An array of the same shape as `x`"""
        raise NotImplementedError()

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        """Computes loss gradient with respect to the activation input.
        
        Arguments:
            gradOutput: Gradient of loss function with recpect to the activation output.
                An array of the same shape as the array received in `__call__` method.

        Returns:
            An array of the same shape as `gradOutput`"""
        raise NotImplementedError()
    

class ReLU(Activation):
    """Implements ReLU activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class LeakyReLU(Activation):
    """Implements LeakyReLU activation layer"""

    def __init__(self, slope: float = 0.03):
        """Initializes LeakyReLU layer.

        Arguments:
            slope: the slope coeffitient of the activation."""
        pass

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class GeLU(Activation):
    """Implements GeLU activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class SiLU(Activation):
    """Implements SiLU (swish) activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class Softplus(Activation):
    """Implements Softplus (SmoothReLU) activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class ELU(Activation):
    """Implements ELU activation layer"""

    def __init__(self, alpha: float = 1):
        """Initializes ELU layer.

        Arguments:
            alpha: the alpha coeffitient of the activation."""
        pass

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class Sigmoid(Activation):
    """Implements Sigmoid activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class Tanh(Activation):
    """Implements Tanh activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass


class Softmax(Activation):
    """Implements Softmax activation layer"""

    def __call__(self, x: np.ndarray) -> np.ndarray:
        """Computes Softmax activation output
        
        Arguments:
            x: Input array of shape (`batch_size`, `n_features`)

        Returns:
            An array of the same shape as `x`"""
        pass

    def grad(self, gradOutput: np.ndarray) -> np.ndarray:
        pass

Функции активации тестируются в порядке их определения в задаче циклично, то есть activation_idx = (test_idx − 1mod 9.

Формат выходных данных

Код решения должен содержать только импортируемые модули, определение и реализацию классов.


Задача 05C. Conv2D

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:25  

Условие

Требуется реализовать на языке 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.

Формат выходных данных

Код решения должен содержать только импортируемые модули, определение и реализацию класса.


Задача 06A. Классификация табличных данных

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Требуется решить задачу классификации табличных данных с использованием изученных моделей машинного обучения.

Требования к датасету

Модели машинного обучения

Требуется использовать следующие модели машинного обучения:

Распределение баллов

Максимальное количество баллов за задачу — 10.

Отправка решения

В качестве решения принимается файл с исходным кодом, например jupyter notebook. В систему требуется отправить ссылку на файл, размещённый в открытом доступе (Google Colab, Github, Google Drive и др.), указав среду разработки "Answer text". После отправки решение необходимо сдать преподавателю лично до начала зачётной недели.


Задача 07A. Устный экзамен

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Билет выбирается независимо и случайно из следующего списка:

Деревья решений.
  • Понятие энтропии, определение информации по Шеннону.
  • Понятие дерева решений. Процесс обучения.
  • Gini impurity, information gain.
  • Случайный лес (Random forest).
  • Bagging, выборка признаков.
  • Дерево регрессии.
  • Сокращение дерева (pruning).
Бустинг (Boosting).
  • Понятие бустинга.
  • Градиентный бустинг.
  • OneRule Boosting.
  • Adaboost.
  • Бустинг деревьев.
Метод опорных векторов (SVM)
  • Постановка задачи линейного SVM для линейно разделимой выборки.
  • Линейный SVM в случае линейно неразделимой выборки.
  • Задача оптимизации SVM. Двойственная задача.
  • Kernel trick. Виды ядер.
Классическое машинное зрение.
  • Фильтрация изображений. Sobel, Gauss.
  • Алгоритм детекции границ Canny.
  • Алгоритм Хаффа поиска прямых (Hough lines).
  • Алгоритм Хаффа поиска окружностей (Hough circles).
Нейронные сети.
  • Полносвязный слой. (Dense, Fully connected).
  • Свёрточный слой. (Convolution).
  • Pooling.
  • Функции активации.
  • Метод обратного распространения ошибки.

Экзамен проводится очно. В случае невозможности очного присутствия необходимо заранее договориться с преподавателем о дистанционной сдаче.

После взятия билета студент готовится в ответу. При подготовке можно использовать произвольные материалы и доступ в Интернет.

В докладе необходимо максимально кратко упомянуть все важные элементы доставшейся темы/вопроса. После доклада преподаватель задаёт несколько уточняющих вопросов.


0.774s 0.032s 59