Пусть имеется задача классификации 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 строках необходимо вывести описания базовых регрессоров — номер признака, на котором был обучен регрессор, и список предсказываемых регрессором значений в порядке возрастания значения признака. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.
Пусть задан некоторый язык, описываемый множеством слов W, |W| = m, m∈N.
Требуется построить наивный байесовский классификаторf: B↦ C = {i}k − 1i = 0,
где {0, 1}m⊇ B = ⋃l∈N,μ∈ Wl{δw(μ)|w∈ W} — множество представлений всех возможных сообщений составленных на языке W в виде мешка слов,
δw — мера Дирака, δx(A) = {1,x∈ A,0,x∉ A..
При этом процесс классификации происходит следующим образом
Сформировать базовый классификатор с априорными вероятностями классов p(c∈ C) = 1k и условными вероятностями слов p(w∈ W|c∈ C) = 1m;
Для каждого поступившего сообщения μi и его класса ci
Получить предсказание ^ci по μi с использованием текущего классификатора;
Обновить классификатор с использованием сообщения μi и настоящего значения его класса ci.
Формат входных данных
Первая строка входного файла содержит натуральные числа n, m, k — количество сообщений, мощность языка и количество классов соответственно. В каждой их следующих n строк содержится m чисел 0 или 1 и одно натуральное число ci — представление сообщения в виде мешка слов и значение его класса.
Формат выходных данных
Выходной файл должен содержать n натуральных чисел — предсказанное значение класса каждого сообщения на момент его получения.
Пусть задано вещественное пространство Rn. Требуется написать программу, классифицирующую точки с использованием байесовского классификатора B(x) = argmaxi = 0,m − 1(πifNk(μi, Σi)(x)m − 1∏j = 0,i≠ jλi,j), где m — количество классов, πi — априорная вероятность класса, fNk(μi, Σi) — функция плотности многомерного нормального распределения Nk(μi, Σi) со средним μi и матрицей ковариацииΣi, λi,j — штраф за ошибочною классификацию класса i в качестве класса j.
Формат входного файла
Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λ — m строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате xi,0, xi,1, …, xi,n − 1, ci, где xi,j вещественные числа — координаты точки i, ci∈{0,1,…,m − 1} — класс точки. Последние l строк содержат по n вещественных чисел — координаты точек тестовой выборки.
Формат выходного файла
Выходной файл должен содержать l целых чисел — предсказанные классы точек тестовой выборки.
Пусть заданы 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.
Формат выходных данных
Код решения должен содержать только импортируемые модули, определение и реализацию класса.
