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

Условие

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

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

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

Задача B. Линейная регрессия ≡

Условие

Требуется написать программу, которая вычисляет коэффициенты линейной регрессии y = a ⋅ x + b. Коэффициенты предполагается вычислять методом наименьших квадратов.

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

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

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

Выходные данные должны содержать 2 числа a и b — коэффициенты регрессии с точностью не менее трёх знаков после запятой.

Ограничения

1 < N < 10⁵

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

2
1 2
3 4

1 2

5
1 2 3 4 5
6 3 5 3 -3

-1.8 8.2

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

Условие

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

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

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

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

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

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

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

Условие

Требуется реализовать следующие функции на языке 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])

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

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

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

Условие

Требуется реализовать следующие функцию на языке 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 ближайших соседей!

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

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

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

Задача F. 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 — количество соседей, которые нужно рассматривать

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

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

Задача G. Логистическая регрессия. Основы ≡

Условие

Пусть задана логистическая регрессия для задачи бинарной классификации

f: X↦ y, X ⊆ Rⁿ, y = { − 1, 1}

f(x, θ) = σ(nx∑iθ_i)

σ(x) = 11 + e^− x

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

import numpy as np

def logistic_func(theta: np.ndarray, x: np.ndarray) -> float:
    """Computes logistic regression value for sample x.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        x: 1d array of float, sample to compute value for
    
    Returns:
        float, logistic regression value
    """
    pass

def logistic_func_all(theta: np.ndarray, X: np.ndarray) -> np.ndarray:
    """Computes logistic regression value for all samples in matrix X.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        X: 2d array of float, row-major matrix of samples
        
    Returns:
        1d array of float, logistic regression values for all samples in matrix X
    """
    pass
    
def cross_entropy_loss(theta: np.ndarray, X: np.ndarray, y: np.ndarray) -> float:
    """Computes binary cross entropy loss for logistric regression with parameters `theta`
    on samples `X` and true labels `y`.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        X: 2d array of float, row-major matrix of samples
        y: 1d array of int, true class lables from set {-1, 1}
        
    Returns:
        float, cross entropy loss value
    """
    pass
    

def grad_cross_entropy_loss(theta: np.ndarray, X: np.ndarray, y: np.ndarray) -> np.ndarray:
    """Computes gradient of binary cross entropy loss for logistic regression
    with parameters `theta` on samples `X` and true values `y`.
    
    Arguments:
        theta: 1d array of float, regresion coefficients
        X: 2d array of float, row-major matrix of samples
        y: 1d array of int, true class labels from set {-1, 1}
        
    Returns:
        1d array of float, cross entorpy gradient with respect to `theta`
    """
    pass

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

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

Задача H. 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

Задача I. 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.

Задача J. 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]

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

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