Билеты 1-8

Алгоритм — это инструкция, определяющая последовательность действий для преобразования исходных данных в требуемый результат. Пример: алгоритм сортировки чисел (например, пузырьковая сортировка), который упорядочивает массив чисел по возрастанию.

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

Статистический подход основан на использовании вероятностных моделей данных, таких как плотности распределения вероятностей, функции распределения и статистические характеристики (например, дисперсия, ковариация). Методы включают байесовские и небайесовские методы, например, метод максимального правдоподобия.

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

Задача распознавания заключается в отнесении объекта к одному из заранее определенных классов на основе его признаков. Пример: распознавание рукописных цифр (отнесение изображения цифры к классу от 0 до 9).

Кластеризация — это разбиение множества объектов на группы (кластеры) на основе их сходства. В отличие от классификации, кластеризация не требует заранее заданных классов и используется для поиска структуры в данных.

Задача оценивания заключается в определении неизвестных параметров объекта на основе данных. Виды оценивания: параметрическое (оценка параметров известного распределения) и непараметрическое (оценка вида распределения).

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

Отбор признаков необходим для сокращения размерности данных и выделения наиболее значимых характеристик объекта. Методы: фильтрация, обертывание (wrapper methods), встроенные методы (embedded methods).

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

Кластеризация может использоваться для предварительного разбиения данных на группы, которые затем используются как классы для задачи распознавания. Пример: кластеризация клиентов по поведению, а затем классификация новых клиентов на основе этих кластеров.

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

Плотность распределения вероятностей описывает вероятность того, что случайная величина примет определенное значение. В статистическом подходе она используется для моделирования данных и принятия решений на основе вероятностных моделей.

Метрики: евклидово расстояние, расстояние Махаланобиса, косинусное расстояние. Они измеряют степень сходства или различия между объектами в многомерном пространстве.

Пример: анализ текста, где слова или символы разбиваются на непроизводные элементы (например, буквы или морфемы), и затем анализируются их отношения для построения грамматики языка.

Нейронные сети, такие как сверточные нейронные сети (CNN), обучаются на наборе изображений с метками классов. После обучения сеть может классифицировать новые изображения, определяя, к какому классу они принадлежат.

Обучение с учителем использует размеченные данные (с метками), например, классификация или регрессия. Обучение без учителя работает с немаркированными данными, например, кластеризация или поиск ассоциативных правил.

Функция правдоподобия p(x/ωi​) — это условная плотность распределения вероятностей для вектора признаков x при условии, что объект принадлежит классу ωi​. Она показывает, насколько вероятно получить данные xx для класса ωi​.

Решающее правило α(x) — это функция, которая относит объект с признаками xx к одному из классов ωi​. Оно определяет, к какому классу следует отнести объект на основе его признаков.

Области решений Γ1​ и Γ2​ определяются на основе отношения правдоподобия:

Граница между областями задается уравнением ll(x)=l0​.

Отношение правдоподобия — это отношение функций правдоподобия для двух классов:

Оно используется для сравнения с порогом l0​ при принятии решения.

Порог l0 определяется на основе штрафных функций и априорных вероятностей:

Если l(x)≥l0​, то объект относится к классу ω1​, иначе — к классу ω2​.

Правило МУР минимизирует ожидаемые потери (риск) для каждого объекта. Для каждого x выбирается решение αi​, которое минимизирует условный риск:

Это означает, что объект x относится к классу ωi​, если:

Апостериорная вероятность P(ωi​/x) вычисляется по формуле Байеса:

где

Условный риск r(αi​/x) — это ожидаемые потери при принятии решения αiαi​ для объекта с признаками xx. Он вычисляется как:

где λ(αi​/ωj​) — штраф за принятие решения αiαi​, когда истинный класс ωj​.

Штрафные функции λij​ учитывают потери, возникающие при принятии решения αiαi​, когда истинный класс ωj​. Обычно потери при ошибке (например, λ12​ или λ21​) больше, чем потери при правильном распознавании (например, λ11​ или λ22​).

Априорная вероятность P(ωi​) — это вероятность появления объекта класса ωi​ до получения данных (априорное знание о том, насколько часто встречается каждый класс).

Условный риск r(αi​/x) — это ожидаемые потери при принятии решения αiαi​ при наблюдении данных x. В случае симметричных штрафных функций с нулевой платой за правильное решение, минимизация условного риска эквивалентна максимизации апостериорной вероятности:

Таким образом, правило минимума условного риска совпадает с правилом максимума апостериорной вероятности.

Байесовская теория решений — это подход к принятию решений, основанный на вероятностных моделях. Она использует априорные вероятности классов и функции правдоподобия для вычисления апостериорных вероятностей, на основе которых принимаются решения.

Критерий максимального правдоподобия используется, когда априорные вероятности классов неизвестны или равны. В этом случае решение принимается в пользу класса, который лучше всего объясняет наблюдаемые данные:

Для двух классов решающее правило критерия максимального правдоподобия выглядит следующим образом:

Если отношение правдоподобия больше 1, выбирается класс ω1, иначе — класс ω2.

• Правило МАВ учитывает как априорные вероятности классов, так и функции правдоподобия.

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

Правило максимума апостериорной вероятности (МАВ) — это решающее правило, при котором решение принимается в пользу класса с наибольшей апостериорной вероятностью:

Это правило минимизирует вероятность ошибки, если штрафы за все ошибки одинаковы.

Штрафные функции λij​ — это функции, которые определяют потери при принятии решения αi​, когда истинным классом является ωj​. В случае симметричных штрафных функций с нулевой платой за правильное решение:​

Это означает, что все ошибки считаются одинаково значимыми.

Разделяющая функция gi​(x) — это функция, которая используется для определения принадлежности вектора признаков xx к одному из классов ωi​. Решение принимается на основе максимума значений разделяющих функций: ωi выбирается, если gi(x)≥gj(x)для всех j≠i.

Обобщенная структура решающего правила заключается в выборе класса с максимальным значением разделяющей функции. Если gi(x)— значение разделяющей функции для класса ωi, то объект относится к классу ωiωi​, если gi(x)≥gj(x) для всех j≠ij.

Граница между двумя классами ω1​ и ω2​ определяется уравнением g1(x)−g2(x)=0. Это уравнение задает поверхность, разделяющую области решений Γ1​ и Γ2​.

Вероятность правильного распознавания Pc​(i) — это вероятность того, что объект класса ωi​ будет правильно отнесен к этому классу. Она вычисляется как интеграл плотности распределения p(x/ωi​) по области решений Γi​:

Общая ошибка распознавания Es​ вычисляется как сумма произведений априорных вероятностей классов p(ωi​) на вероятности ошибок ϵer​(i):

Ошибка первого рода α: Вероятность отнесения объекта класса ω1 к классу ω2​. Вычисляется как:

Ошибка второго рода β: Вероятность отнесения объекта класса ω2 к классу ω1​. Вычисляется как:

1. Прямое интегрирование: Интегрирование плотностей p(x/ωi) по областям решений Γi​.

2. Анализ одномерных распределений: Использование центральной предельной теоремы для аппроксимации распределений разделяющих функций.

3. Граница Чернова: Использование верхних границ для оценки вероятностей ошибок.

4. Статистическое моделирование: Прямое моделирование и подсчет ошибок.

Граница Чернова — это верхняя граница для вероятности ошибки, которая используется для оценки ошибок распознавания. Для двух классов она вычисляется как:

где

а t — параметр, лежащий в интервале от 0 до 1.

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

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

Это позволяет упростить вычисления и анализ.

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

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

Априорные вероятности — это вероятности появления объектов различных классов до получения данных. Они влияют на решающее правило через порог l0​. Если априорные вероятности классов равны, порог равен нулю, и разделяющая граница проходит посередине между центрами классов.

Функции правдоподобия — это условные плотности распределения вероятностей для вектора признаков при условии, что объект принадлежит определённому классу. В данном случае они описываются гауссовскими распределениями: p(x/ωi)=N(x,mi,C), где mi​ — математическое ожидание, а C — матрица ковариации.

Разделяющая функция для двух классов с одинаковыми матрицами ковариации имеет вид:

Эта функция линейна относительно компонент вектора x.

Решающее правило — это правило, которое определяет, к какому классу отнести объект на основе значения разделяющей функции. Для двух классов правило выглядит так:

если g′′(x)≥l0​, то объект относится к классу ω1 , иначе — к классу ω2​.

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

Расстояние Махаланобиса — это мера расстояния между двумя точками в пространстве с учётом ковариационной структуры данных. В задаче распознавания оно определяет, насколько далеко друг от друга находятся центры классов. Чем больше это расстояние, тем меньше вероятность ошибки.

Для случая с тремя и более классами разделяющая функция для каждого класса iiимеет вид:

Объект относится к классу i, если

для всех j≠i

Для трёх и более классов области решений представляют собой многоугольники, грани которых являются отрезками прямых линий. Эти отрезки образуются при попарном разделении классов. На рисунках в билете показаны примеры таких областей для трёх и четырёх классов.

Априорные вероятности гипотез — это вероятности p(ωj​), которые задают вероятность того, что объект принадлежит классу ωj до того, как были получены данные. Формула:

Функция правдоподобия для гауссовского распределения задается формулой:

где mi — математическое ожидание, а Ci — матрица ковариации для класса ωiωi​.

Разделяющая функция для двух классов с разными ковариационными матрицами C1 и C2​ имеет вид:

квадратичный характер, и граница между классами может быть гиперсферой, гиперэллипсоидом, гиперпараболоидом и т.д.

Если математические ожидания и матрицы ковариаций разные, граница между классами может иметь вид параболы, гиперболы или других поверхностей второго порядка. Например:

• Для разных мат. ожиданий и ковариаций граница может быть параболой.

• Для одинаковых мат. ожиданий и разных дисперсий граница будет окружностью.

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

Гауссовская аппроксимация — это метод, при котором распределение разделяющей функции g′′(x) аппроксимируется гауссовским распределением. Это позволяет оценить вероятности ошибок, используя математические ожидания и дисперсии g′′(x) для каждой гипотезы.

Верхняя граница Чернова используется для оценки вероятности ошибки распознавания двух классов. Она основана на расстоянии Бхаттачария и имеет вид:

где B — расстояние Бхаттачария между классами.

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

При dm=0(когда математическое ожидание разности между классами равно нулю) граница Чернова не работает, так как она не может дать точную оценку вероятности ошибки. Точность границы Чернова увеличивается с ростом dm.

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

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

Функция правдоподобия p(x/ωi) описывает вероятность наблюдения вектора признаков xx при условии, что он принадлежит классу ωi​. Она используется для построения решающего правила, которое определяет, к какому классу следует отнести образ.

Наивный байесовский классификатор — это алгоритм, основанный на предположении о статистической независимости признаков. Это означает, что многомерная плотность распределения p(x/ωi​) представляется как произведение одномерных плотностей:

Решающее правило для двух классов выглядит следующим образом:

где l0 — пороговое значение, определяемое априорными вероятностями классов.

Гауссовская аппроксимация используется, потому что сумма большого числа независимых случайных величин (в данном случае логарифмов отношений правдоподобия) стремится к нормальному распределению согласно центральной предельной теореме. Это упрощает анализ и расчеты.

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

где mgk,iи Dgk,iD— математические ожидания и дисперсии для каждого признака kk в классе ωiωi​.

Вероятности ошибок первого (α) и второго (β) рода рассчитываются через функцию стандартного нормального распределения Φ:

Примером может быть показательное распределение:

где λi — параметр распределения для класса ωiωi​.

Основные допущения и ограничения:

1. Статистическая независимость признаков: Признаки предполагаются независимыми, что упрощает расчеты, но может быть неверным в реальных задачах.

2. Гауссовская аппроксимация: Логарифм отношения правдоподобия предполагается нормально распределенным, что справедливо при большом числе признаков.

Бинарные признаки — это признаки, которые могут принимать только два значения, например, 0 и 1. Они используются для описания объектов в задачах распознавания образов.

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

где pk​ — вероятность того, что k-й признак равен 1 для класса ωi​.

Логарифм отношения правдоподобия (ЛОП) — это величина, которая используется для принятия решений о принадлежности объекта к тому или иному классу. Она вычисляется как:

где pk​ и qk​ — вероятности получения единицы для k-го признака в первом и втором классе соответственно.

Разделяющая граница между классами определяется как линейная функция от компонент вектора признаков:

где

α0​ — константа, зависящая от априорных вероятностей классов.

Вероятности ошибок первого рода (αα) и второго рода (ββ) вычисляются с использованием биномиального распределения:

где L0​ — пороговое значение, ns​ — количество несовпадающих элементов, а pl​ — вероятность искажения элементов.

При увеличении вероятности искажения pl до 0.5 вероятности ошибок α и β монотонно возрастают. В точке pl​=0.5 ЛОП становится равным нулю, и решение принимается в пользу класса с большей априорной вероятностью.

вероятности ошибок начинают снижаться из-за эффекта "переинверсии". Качество распознавания улучшается, так как искажения начинают работать в пользу правильного распознавания.

Вероятностные характеристики бинарных признаков при наличии шума записываются как:

где sk(i)​ — значение k-го элемента исходного изображения, а pi— вероятность искажения.

"Переинверсия" — это эффект, возникающий при вероятности искажения pl​>0.5, когда искажения начинают работать в пользу правильного распознавания. Это приводит к снижению вероятностей ошибок и улучшению качества распознавания.

Схема Бернулли используется для описания nn независимых испытаний, где каждое испытание имеет два исхода (0 или 1). Вероятности ошибок αα и ββ могут быть вычислены с использованием биномиального распределения:

где p и q — вероятности получения единицы для первого и второго класса соответственно.