Задача 1A. One Rule ≡

Условие

Требуется реализовать классификатор, использующий алгоритм One Rule.

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

Первая строка входных данных содержит два целых числа N и K — количество примеров в обучающей выборке и количество признаков соответственно.

Вторая строка содержит K слов, разделённых пробелом — названия признаков объектов.

Следующие N строк содержат обучающую выборку, каждая строка содержит по K + 1 слов, первые K слов описывают значения признаков, слово номер K + 1 содержит метку класса — 0 или 1.

Следующая строка содержит одно целое число M — количество примеров в тестовой выборке.

Далее идёт тестовая выборка, содержащая M строк по K слов. Гарантируется, что каждое значение каждого признака встречается в обучающей выборке хотя бы один раз.

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

Выходные данные должны содержать M чисел — результаты классификации алгоритма One Rule после обучения на первых N примерах.

В случае если несколько признаков дают одинаковый результат на обучающей выборке, то следует выбрать тот, который встречается раньше.

Если по какому-то значению можно с одинаковой вероятностью предсказать как 0 так и 1, то следует предсказывать 1.

Ограничения

1 ≤ N, M, K ≤ 100

Суммарная длина строк не превосходит 10⁵

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

10 4
Outlook Temperature Humidity Windy
overcast hot high FALSE 1
sunny mild high FALSE 0
overcast mild high TRUE 1
rainy mild normal FALSE 1
overcast hot normal FALSE 1
rainy mild high FALSE 1
rainy cool normal FALSE 1
rainy mild high TRUE 0
sunny hot high FALSE 0
sunny hot high TRUE 0
4
rainy cool normal TRUE
sunny cool normal FALSE
overcast cool normal TRUE
sunny mild normal TRUE

1
0
1
0

Задача 1B. Экстраполяция ≡

Условие

Имеется фиксированная неизвестная функция f(x), она одинаковая для всех тестов. Даны значения функции f(x), f(x + 1), f(x + 2), …, f(x + N − 1). Требуется определить значение функции f в точке x + N.

Для понимания структуры функции следует воспользоваться двумя тестами: первый из них приведён в примере. Второй тест можно скачать ЗДЕСЬ.

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

Первая строка входного файла содержит одно целое число N.

Вторая строка входного файла содержит N вещественных чисел — значения функции f в точках x, x + 1, x + 2, …, x + N − 1.

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

Выходной файл должен содержать одно число — f(x + N) с точностью не менее двух знаков после запятой.

Ограничения

3 ≤ N ≤ 10⁵

 − 10⁸ ≤ x ≤ 10⁸

 − 10⁹ ≤ f(x) ≤ 10⁹

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

5
700.949074 715.616206 726.958614 730.983909 730.427020

732.2357177317001

Задача 1C. Простой график ≡

Условие

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

import matplotlib.pyplot

def draw(plt: matplotlib.pyplot, x: list) -> None:
    pass

График должен быть нарисован зелёным цветом 'green' и содержать координатную сетку. Оси должны быть подписаны, выражение для оси ординат должно быть выражением на языке LaTeX, таким же, как в тексте задачи, в inline режиме отображения математических выражений $...$.

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

Код решения должен содержать только реализацию функции. Код НЕ должен самостоятельно сохранять изображение в файл или выводить изображение на экран.

Задача 2A. Градиентный спуск ≡

Условие

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

class GradientOptimizer: def __init__(self, oracle, x0): self.oracle = oracle self.x0 = x0 def optimize(self, iterations, eps, alpha): pass

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

Метод optimize принимает максимальное число итераций для критерия остановки, L2-норму градиента, которую можно считать оптимальной, а также learning rate. Метод возвращает оптимальную точку.

Оракул имеет следующий интерфейс:

class Oracle: def get_func(self, x): pass def get_grad(self, x): pass

x имеет тип np.array вещественных чисел.

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

Код должен содержать только класс и его реализацию. Он не должен ничего выводить на экран.

Задача 2B. Gradient Descent with Momentum ≡

Условие

Требуется реализовать на языке Python класс GDM, который описывает алгоритм градиентного спуска с моментом и имеет следующий интерфейс:

Параметрами алгоритма являются:

• alpha — скорость затухания момента,
• eta — learning rate.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию:

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

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

Задача 2C. Nesterov Accelerated Gradient ≡

Условие

Требуется реализовать на языке Python класс NesterovAG, который описывает алгоритм ускоренного градиента Нестерова и имеет следующий интерфейс

import numpy as np

class NesterovAG:
    '''Represents a Nesterov Accelerated Gradient optimizer

    Fields:
        eta: learning rate
        alpha: exponential decay factor
    '''

    eta: float
    alpha: float

    def __init__(self, *, alpha: float = 0.9, eta: float = 0.1):
        '''Initalizes `eta` and `aplha` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the current gradient is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• alpha — скорость затухания момента,
• eta — learning rate.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 2D. AdaGrad ≡

Условие

Требуется реализовать на языке Python класс AdaGrad, который описывает алгоритм адаптивного градиентного спуска и имеет следующий интерфейс

import numpy as np

class AdaGrad:
    '''Represents an AdaGrad optimizer

    Fields:
        eta: learning rate
        epsilon: smoothing term
    '''

    eta: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, epsilon: float = 1e-8):
        '''Initalizes `eta` and `epsilon` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 2E. RMSProp ≡

Условие

Требуется реализовать на языке Python класс RMSProp, который описывает одноименный алгоритм и имеет следующий интерфейс

import numpy as np

class RMSProp:
    '''Represents an RMSProp optimizer

    Fields:
        eta: learning rate
        gamma: exponential decay factor
        epsilon: smoothing term
    '''

    eta: float
    gamma: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, gamma: float = 0.9, epsilon: float = 1e-8):
        '''Initalizes `eta`, `gamma` and `epsilon` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• gamma — коэффициент затухания,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 2F. Adam ≡

Условие

Требуется реализовать на языке Python класс Adam, который описывает одноименный алгоритм и имеет следующий интерфейс

import numpy as np

class Adam:
    '''Represents an Adam optimizer

    Fields:
        eta: learning rate
        beta1: first moment decay rate
        beta2: second moment decay rate
        epsilon: smoothing term
    '''

    eta: float
    beta1: float
    beta2: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, beta1: float = 0.9, beta2: float = 0.999, epsilon: float = 1e-8):
        '''Initalizes `eta`, `beta1` and `beta2` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• beta1 — коэффициент затухания первого момента,
• beta2 — коэффициент затухания второго момента,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 3A. Линейная регрессия. Основы ≡

Условие

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

def linear_func(theta, x)                  # function value
def linear_func_all(theta, X)              # 1-d np.array of function values of all rows of the matrix X
def mean_squared_error(theta, X, y)        # MSE value of current regression
def grad_mean_squared_error(theta, X, y)   # 1-d array of gradient by theta

theta — одномерный np.array

x — одномерный np.array

X — двумерный np.array. Каждая строка соответствует по размерности вектору theta

y — реальные значения предсказываемой величины

Матрица X имеет размер M × N. M строк и N столбцов.

Используется линейная функция вида: h_θ(x) = θ₁ x₁ + θ₂ x₂ + ...  + θ_n x_N

Mean squared error (MSE) как функция от θ: J(θ) = 1MM∑i = 1(y_i − h_θ(x⁽ⁱ⁾))². Где x⁽ⁱ⁾ — i-я строка матрицы X

Градиент функции MSE: ∇ J(θ) = { ∂ J∂ θ₁, ∂ J∂ θ₂, ..., ∂ J∂ θ_N}

Пример

X = np.array([[1,2],[3,4],[4,5]])

theta = np.array([5, 6])

y = np.array([1, 2, 1])

linear_func_all(theta, X) # --> array([17, 39, 50])

mean_squared_error(theta, X, y) # --> 1342.0

grad_mean_squared_error(theta, X, y) # --> array([215.33333333, 283.33333333])

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

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

Задача 3B. Найти линейную регрессию ≡

Условие

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

def fit_linear_regression(X, y)   # np.array of linear regression coefs

X — двумерный np.array. Каждая строка соответствует отдельному примеру.

y — реальные значения предсказываемой величины

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

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

Задача 3C. Lasso ≡

Условие

Пусть имеется задача регрессии f(x) = a ⋅ x + b ≈ y. Требуется найти коэффициенты регрессии a, такие, что |{a_i | a_i ∈ a, a_i = 0}| = k,  0 < k ⩽ |a| = m. При этом должно выполняться условие R² = 1 − n∑i = 1(y_i − f(X_i))²n∑i = 1(y_i − y)² ⩾ s. При решении задачи предполагается использование алгоритма Lasso.

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

Данные для обучения содержатся в файле. Качество модели будет рассчитано на скрытом наборе данных

Первая строка входных данных содержит натуральное число N — количество тестов. В следующих N блоках содержится описание тестов. Первая строка блока содержит целые числа n — количество примеров обучающей выборки, m — размерность пространства, k — необходимое количество нулевых коэффициентов, и вещественное число s — минимальное значение метрики R². Следующие n строк содержат по m + 1 вещественному числу — координаты точки пространства и значение целевой переменной y.

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

Решение должно представлять собой текстовый файл содержащий N строк — коэффициенты a и b линейной регрессии разделённые символом пробел.

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

1
10 5 1 0.8
-0.5  -0.26 -0.11 -0.66  0.49 -24.89
 0.08 -0.38  0.6   1.29  0.42  62.2
 0.82  0.12  0.54  1.33 -0.82  47.55
-0.36  0.54 -0.6   0.55 -0.01 -15.96
-0.91 -0.71  0.59  1.0   0.43 -11.11
-0.97 -0.78  0.2  -0.93  1.24 -17.04
 0.29  0.77 -0.87 -0.05 -0.71 -38.97
 0.19 -0.16  1.0   0.63  1.79 188.63
 0.22 -2.38  3.0   0.22 -0.53  23.32
 0.36 -0.84  1.05 -1.06 -0.06  15.31

43.69 0.0 10.48 16.86 46.25 6.39

Задача 3D. МНК: квадратичная зависимость ≡

Условие

Некоторая теоретическая модель предполагает зависимость переменной Y от переменной X по следующему закону: Y = a * X² + b * X + c.

Требуется по N наблюдениям методом наименьших квадратов оценить параметры a, b и c данной модели.

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

Первая строка входного файла содержит одно целое число N.

Следующие N строк содержат по два числа — x_i и y_i

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

Выходной файл должен содержать три вещественных числа a, b и c с точностью до двух знаков после десятичной точки.

Ограничения

3 ≤ N ≤ 1000

1 ≤ |x_i|, |y_i| ≤ 5000

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

5
4 1
2 3
0 5
3 2
1 4

0.000000 -1.000000 5.000000

6
3 1
4 2
6 2
1 1
5 1
2 10

-0.142857 0.400000 3.600000

Задача 4A. k-point crossover ≡

Условие

Требуется на языке Python реализовать методы точечного кроссовера.

Функция single_point_crossover(a, b, point) выполняет одноточечный кроссовер, значения справа от точки кроссовера меняются местами.

Функция two_point_crossover(a, b, first, second) выполняет двухточечный кроссовер, значения между точек кроссовера меняются местами.

Функция k_point_crossover(a, b, points) выполняет k-точечный кроссовер, значения между каждой чётной парой точек меняются местами.

Функции должны иметь следующий интерфейс

import numpy as np

def single_point_crossover(a: np.ndarray, b: np.ndarray, point: int) -> tuple[np.ndarray, np.ndarray]:
    """Performs single point crossover of `a` and `b` using `point` as crossover point.
    Chromosomes to the right of the `point` are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        point: crossover point

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()


def two_point_crossover(a: np.ndarray, b: np.ndarray, first: int, second: int) -> tuple[np.ndarray, np.ndarray]:
    """Performs two point crossover of `a` and `b` using `first` and `second` as crossover points.
    Chromosomes between `first` and `second` are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        first: first crossover point
        second: second crossover point

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()


def k_point_crossover(a: np.ndarray, b: np.ndarray, points: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
    """Performs k point crossover of `a` and `b` using `points` as crossover points.
    Chromosomes between each even pair of points are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        points: one-dimensional array, crossover points

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()

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

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

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

0 1 2 3 4 4 3 2 1 0
9 8 7 6 5 5 6 7 8 9

0 1 2 6 5 4 3 7 8 9
9 8 7 3 4 5 6 2 1 0

0 1 7 6 5 5 6 7 8 0
9 8 2 3 4 4 3 2 1 9
            

Задача 4B. Stochastic universal sampling ≡

Условие

Требуется на языке Python реализовать алгоритм Stochastic universal sampling.

Функция должна иметь следующий интерфейс

import numpy as np

def sus(fitness: np.ndarray, n: int, start: float) -> list:
    """Selects exactly `n` indices of `fitness` using Stochastic universal sampling alpgorithm. 

    Args:
        fitness: one-dimensional array, fitness values of the population, sorted in descending order
        n: number of individuals to keep
        start: minimal cumulative fitness value

    Return:
        Indices of the new population"""

    raise NotImplementedError()

Параметрами функции являются:

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

Функция возвращает список индексов выбранных особей

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

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

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

10 4 1
            

Задача 5A. Poisson regression ≡

Условие

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

f(x, θ) = exp(n∑i = 1θ_i x_i + θ₀) ,

где n — количество признаков.

Модель оптимизирует следующую функцию потерь

l(X, y, θ) = 1mm∑i = 1(y_ilogy_if(X_i, θ) − y_i + f(X_i, θ)) + α2n∑i = 1θ2i ,

где m — количество примеров, α — параметр регуляризации.

Для оценки качества модели используется метрика D²

D² = 1 − D(y, ŷ)D(y, y) ,

где y — среднее значение вектора y,

D(y, ŷ) = 2mm∑i = 1(y_ilogy_iŷ_i − y_i + ŷ_i) .

Класс должен иметь следующий интерфейс

from __future__ import annotations

import numpy as np


class PoissonRegression:
    r"""Implements a generalized linear model with log link function[1]

        f(x, \theta) = \exp(\sum\limits_{i=1}^n\theta_ix_i + \theta_0)

    The model optimizes the following loss

        l(X, y, \theta) = \frac{1}{m}\sum\limits_{i=1}^n(y_i\log\frac{y_i}{f(X_i, \theta)} - y_i + f(X_i, \theta)) + \frac{\alpha}{2}\sum\limits_{i=1}^n\theta_i^2

    where n, m are numbers of features and samples respectively, $\alpha$ -- regularization strength.

    Parameters:

        use_bias: bool, default = True
            Whether the model uses bias term.

        alpha: float, default = 1
            L2 regularization strength.

    References:

        [1]: https://en.wikipedia.org/wiki/Generalized_linear_model#Link_function
    """
    
    def __init__(self, use_bias: bool = True, alpha: float = 1):
        """Initializes `use_bias` and `alpha` fields."""
        pass


    def predict(self, X: np.ndarray) -> np.ndarray:
        """Computes model value on feature matrix `X`.

        Arguments:

            X: 2d array of float, feature matrix.

        Returns:

            1d array of float, predicted values.
        """
        pass


    def loss(self, X: np.ndarray, y: np.ndarray) -> float:
        """Computes loss value on feature matrix `X` with target values `y`.

        Arguments:

            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.

        Returns:

            loss value
        """
        pass


    def score(self, X: np.ndarray, y: np.ndarray) -> float:
        r"""Computes D^2 score on feature matrix `X` with target values `y`.

        The score is defined as

            D^2 = 1 - \frac{D(y, \hat{y})}{D(y, \overline{y})}

        where D(y, \hat{y}) = 2(y\log\frac{y}{\hat{y}} - y + \hat{y}).

        Arguments:
            
            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.

        Returns:

            score value
        """
        pass


    def fit(self, X: np.ndarray, y: np.ndarray, *,
            eta: float = 1e-3, beta1: float = 0.9, beta2: float = 0.999,
            epsilon: float = 1e-8, tol: float = 1e-3, max_iter: int = 1000) -> PoissonRegression:
        """Optimizes model loss w.r.t model coefficitents using Adam[1] optimization algorithm.
        Initially model coefficients are initialized with zeros.

        Arguments:

            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.
            eta: learning rate.
            beta1: first moment decay rate.
            beta2: second moment decay rate.
            tol: threshold for L2-norm of gradient.
            max_iter: maximal number of iterations.

        Returns:

            self

        References:

            [1]: https://ruder.io/optimizing-gradient-descent/index.html#adam
        """
        pass


    @property
    def coeffs(self) -> np.ndarray:
        """Returns 1d array of float, coefficients used by the model excluding bias term."""
        pass
    

    @property
    def bias(self) -> float:
        """Returns bias term used by the model. If `use_bias = False` returns 0."""
        pass

Для оптимизации должен быть использован алгоритм Adam. Оптимизация начинается с нулевой начальной точки θ = {0}ni = 0.

При решении задачи запрещено использовать любые модули, кроме numpy и scipy.special.

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

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

Задача 6A. Распределение задач ≡

Условие

Группа разработчиков работает над проектом. Весь проект разбит на задачи, для каждой задачи указывается ее категория сложности (1, 2, 3 или 4), а также оценочное время выполнения задачи в часах. Проект считается выполненным, если выполнены все задачи. Для каждого разработчика и для каждой категории сложности задачи указывается коэффициент, с которым, как ожидается, будет соотноситься реальное время выполнения задачи данным разработчиком к оценочному времени. Считается, что все разработчики начинают работать с проектом в одно и тоже время и выделяют для работы одинаковое время. Необходимо реализовать программу, распределяющую задачи по разработчикам, с целью минимизировать время выполнения проекта (получить готовый проект за минимальный промежуток времени). Поиск решения необходимо реализовать с помощью генетического алгоритма.

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

В качестве решения принимается текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Решение набирает количество баллов, вычисляемое по следующей формуле: Score = 10⁶T_max. T_max — наибольшее среди всех разработчиков время, затраченное на выполнение выданных соответствующему разработчику задач.

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

Первая строка входного файла содержит целое число N количество задач.

Вторая строка — N целых чисел от 1 до 4 категорий сложности задач.

Третья строка — N вещественных положительных чисел оценочного времени для задач.

Четвертая строка – целое число M, количество разработчиков .

Следующие M строк содержат по 4 вещественных положительных числа — коэффициенты каждого разработчика.

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

Первая и единственная строка выходного файла содержит N целых чисел w_i — номер разработчика, назначенного на i - ю задачу.

Ограничения

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

3
1 1 4
5.2 3.4 4
2
1 1 2 5
0.7 1 1.2 1.5

1 2 2

Задача 6B. Распределение задач. Загрузка решения ≡

Условие

Требуется загрузить решение задачи Распределение задач. Баллы за задачу устанавливаются после ручной проверки отправленного решения.

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

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

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

• По одному баллу выставляется за преодоление каждого из порогов 0.155, 0.16, 0.165.
• Два балла за качество, эффективность решения и использованных методов.

Задача 7A. Метод ближайших соседей. Основы ≡

Условие

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

def knn_predict_simple(X, y, x, k)     # array of pairs -- class and number of votes of neighbors

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

y — реальные значения классов в обучающей выборке

x — одномерный np.array-- тестовый пример

k — количество соседей, которые нужно рассматривать

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

Для поиска ближайшего примера использовать евклидово расстояние.

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

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

Задача 7B. Leave-one-out (метод скользящего контроля) ≡

Условие

Требуется реализовать функцию leave-one-out score на языке Python. Результат функции должен быть целочисленным, то есть его НЕ следует нормировать на размер выборки.

def loo_score(predict, X, y, k)     # integer loo score for predict function

predict — функция predict(X, y, x, k) , обучающая некоторый алгоритм на выборке X, y с параметром k и дающая предсказание на примере x

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

y — реальные значения классов в обучающей выборке

k — количество соседей, которые нужно рассматривать

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

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

Задача 7C. Border ratio ≡

Условие

Пусть на некотором наборе точек X = {x_i}ni = 1, x_i ∈ R^m задана функция f: R^m↦N. Требуется написать программу, вычисляющую значение border ratio α(x) = ∥x̂ − y∥₂∥ x − y∥₂, ∀ x ∈ X, где y = arg miny ∈ X, f(x) ≠ f(y)∥ x − y∥₂, x̂ = arg minx̂ ∈ X, f(x) = f(x̂)∥x̂ − y∥₂.

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

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

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

Выходной файл должен содержать n вещественных чисел — значения border ratio каждой точки с точностью не менее трёх знаков после запятой.

Ограничения

6 ⩽ n ⩽ 1500

2 ⩽ m ⩽ 50

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

6 2
0 0 0
0 2 1
1 2 0
4 2 1
3 0 1
4 0 0

0.5 1.0 1.0 0.5 1.0 1.0

10 2
0 0 0
0 2 0
4 2 0
6 2 0
4 4 1
6 1 1
6 6 1
0 5 2
0 6 2
0 7 2

0.6 1.0 1.0 1.0 1.0 1.0 0.25 1.0 0.75 0.6

Задача 8A. Entropy ≡

Условие

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

Задача 8B. Gini ≡

Условие

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

gini(y) = 1 − ∑v = set(y)p²(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.

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

3 2 4 4 2 0 1 3 0 1

0.8

Задача 8C. Decision tree split ≡

Условие

Требуется реализовать следующие функцию на языке 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 возвращает наилучшее бинарное разделение по правилу вида x^col ≤ X[row, col]

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

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

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

Условие

Вопрос на устном экзамене

Укажите вопрос, который будете отвечать на экзамене.

1. Введение
• Основные термины и задачи машинного обучения.
• Признаки, их виды и свойства. Переход между категориальными и численными признаками.
• Функция потерь. Оптимизация.
• Ошибки первого и второго рода. Метрики качества: accuracy, precision, recall, F1-score.
• Случайный поиск. Перебор по сетке.
• Проблемы работы с данными высокой размерности.

2. Градиентный спуск (gradient descent)
• Производная, частные производные, градиент. Методы оценки градиента.
• Градиентный спуск, проблема выбора шага.
• Стохастический градиентный спуск.
• Использование момента. Метод Нестерова.
• Метод отжига.
• Adagrad, Adadelta, RMSProp, Adam.
• AMSGrad, AdamW, YellowFin, AggMo, Quasi-Hyperbolic Momentum, Demon.

3. Линейная регрессия (linear regression)
• Постановка задачи линейной регрессии. Вероятностная интерпретация.
• Метод наименьших квадратов. Алгебраическое и оптимизационное решения.
• Ковариация, корреляция.
• Коэффициент деретминации (критерий R²).
• Анализ остатков. Гомоскедастичность. Квартет Анскомба.
• Решение для неквадратных и плохо обусловненных матриц.
• Регуляризация LASSO, Ridge, Elastic.
• Обобщённые аддитивные модели (generalized additive models).
• Partial Least Squares

4. Логистическая регрессия (logistic regression)
• Сигмоид.
• Метод наибольшего правдоподобия.
• Логистическая регрессия для меток  − 1, 1.
• Обобщённые линейные модели (generalized linear models)
• Пробит-регрессия (probit regression)

5. Глобальная оптимизация. Генетический алгоритм (genetic algorithm)
• Многопараметрическая оптимизация.
• Доминация и оптимальность по Парето.
• Функция качества (fitness). Аппроксимация качества.
• Общая идея генетического алгоритма.
• Представление генома.
• Методы селекции: пропорционально качеству, универсальная выборка (stochastic universal sampling), с наследием (reward-based), турнир. Стратегия элитизма.
• Методы кроссовера. Двух и много-точечный, равномерный (по подмножествам), для перестановок.
• Мутация. Влияние на скорость обучения.
• Управление популяцией. Сегрегация, старение, распараллеливание.
• Генетическое программирование.

6. Деревья решений (decision trees)
• Понятие энтропии, определение информации по Шеннону.
• Понятие дерева решений.
• Метрики: примеси Джини (Gini impurity), добавленная информация (information gain).
• Алгоритмы ID3, CART.
• Борьба с оверфиттингом: bagging, выборки признаков (random subspace method).
• Ансамбли, случайный лес (Random Forest).
• Деревья регрессии. Метрика вариации.
• Непрерывные признаки. Использование главных компонент вместо признаков.
• Сокращение дерева (pruning).
• Другие алгоритмы вывода правил: 1-rule, RIPPER, bayesian rule lists
• Комбинация с линейной регрессией (RuleFit).

7. Метрики и метрическая кластеризация (metrics)
• Понятие и свойства метрики. Ослабление требования к неравенству треугольника.
• Метрики L₁, L₂, Хемминга, Левенштейна, косинусное расстояние.
• Потеря точности нормы в высоких размерностях.
• Нормализация координат. Предварительная трансформация пространства признаков.
• Метрика Махаланобиса.
• Понятие центроида и представителя класса.
• Центроидные алгоритмы: k-means, k-medoid. Алгоритм Ллойда.

8. Метод ближайших соседей (k-NN)
• Базовый алгоритм классификации методом 1-NN и k-NN. Преимущества и недостатки.
• Кросс-валидация методом "без одного" (leave one out).
• Определение границ, показатель пограничности (border ratio).
• Сжатие по данным. Понятия выброса, прототипа, усвоенной точки. Алгоритм Харта (Hart).
• Регрессия методом k-NN.
• Взвешенные соседи.
• Связь с градиентным спуском. Стохастическая формулировка, softmax.
• Метод соседних компонент (neighbour component analysis)
• Связь с выпуклой оптимизацией. Метод большого запаса (Large margin NN)
• Оптимизация классификатора, k-d деревья, Hierarchical Navigable Small World
• Хеши чувствительные к локальности, хеши сохраняющие локальность

Ссылка на подготовленные материалы (Github, Google Drive и др.). Шпаргалка для ответа на выбранный вопрос.