МОТП, Билеты (2009)

Материал из eSyr's wiki.

Перейти к: навигация, поиск

Содержание

Часть 1 (Ветров)

Метод максимального правдоподобия. Его достоинства и недостатки.

Недостатки:

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

Решение несовместных СЛАУ.

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

Несовместная СЛАУ -- система линейных уравнений, не имеющая ни одного решения.

Совместная СЛАУ -- система линейных уравнений, имеющая хотя бы одно решение.

Ридж-регуляризация (ридж-регрессия, регуляризация Тихонова) матрицы ATA -- матрица ATA + λI, где λ -- коэффициент регуляризации. Всегда невырождена при λ > 0

Нормальное псевдорешение СЛАУ Ax = b -- вектор x = (ATA + λI) − 1ATb

  • всегда единственно
  • при небольших λ определяет псевдорешение с наименьшей нормой
  • любое псевдорешение имеет минимальную невязку

Задача восстановления линейной регрессии. Метод наименьших квадратов.

Задача регрессионного анализа (неформально): Предположим имеется зависимость между наблюдаемыми признаками (случайной выборкой) X и некоторой переменной (параметром) t. Задача регрессионного анализа -- определение наличия и характера (математического уравнения, описывающего зависимость) связи между переменными

Пример: простой пример на пальцах: Linear Regression Example

S(t, \hat{t}) -- функция потерь от ошибки. На пальцах: берем найденную путем регрессии функцию \hat{t}(x) и сравниваем её выдачу на тех же наборах x, что и заданные результаты эксперимента t(x).

  • S_1(t, \hat{t}) = (t - \hat{t})^2
  • S_2(t, \hat{t}) = |t - \hat{t}|^2
  • S_3(t, \hat{t}) = \delta^{-1}(t - \hat{t})

Основная задача -- минимизировать эту функцию, что значит минимизировать \mathbb{E} S(t, \hat{t}(x,w)) = \int\int S(t, \hat{t}(x,w)) p(x,t) dx dt \rightarrow \min_{w}


Метод наименьших квадратов -- минимизация функции потери ошибки S(t, \hat{t}) = (t - \hat{t})^2

Задача восстановления линейной регрессии. Вероятностная поставновка.

Логистическая регрессия. Вероятностная постановка.

ЕМ-алгоритм для задачи разделения гауссовской смеси.

Основные правила работы с вероятностями. Условная независимость случайных величин.

Графические модели. Основные задачи, возникающие в анализе графических моделей.

Байесовские сети. Примеры.

На википедии

Марковские сети. Примеры.

Скрытые марковские модели. Обучение СММ с учителем.

На википедии

Викибуки

Алгоритм динамического программирования и его применение в скрытых марковских моделях.

ЕМ-алгоритм и его применение в скрытых марковских моделях.

Условная независимость в скрытых марковских моделях. Алгоритм «вперед-назад».

Метод релевантных векторов в задаче восстановления регрессии.

Метод релевантных векторов в задаче классификации.

Метод главных компонент.

Вероятностная формулировка метода главных компонент.

ЕМ-алгоритм в методе главных компонент. Его преимущества.

Метод главных компонент. Схема автоматического выбора числа главных компонент.

Недостатки метода главных компонент. Метод независимых компонент.

Нелинейные методы уменьшения размерности. Локальное линейное погружение.

Нелинейные методы уменьшения размерности. Ассоциативные нейронные сети и GTM.

Часть 2 (Рудаков)

Объекты, признаки, логические признаки, простейшие логические решающие правила.

Признаки объектов:

  • детерминированные;
  • вероятностные;
  • логические;
  • структурные.

Детерминированные признаки – это признаки, принимающие конкретные числовые значения, которые могут быть рассмотрены как координаты точки, соответствующей данному объекту, в n-мерном пространстве признаков.

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

Логические признаки распознаваемых объектов можно рассматривать как элементарные высказывания, принимающие два значения истинности (истина – ложь) с полной определенностью. К логическим признакам относятся прежде всего признаки, не имеющие количественного выражения. Эти признаки представляют собой суждения качественного характера типа наличия или отсутствия некоторых свойств или некоторых элементов у распознаваемых объектов или явлений. В качестве логических признаков можно рассматривать, например, такие симптомы в медицинской диагностике, как боль в горле, кашель и т.д. К логическим можно отнести также признаки, у которых важна не величина признака у распознаваемого объекта, а лишь факт попадания или непопадания ее в заданный интервал. В пределах этих интервалов появление различных значений признаков у распознаваемых объектов предполагается равновероятным. На практике логические признаки подобного рода имеют место в таких ситуациях, когда либо ошибками измерений можно пренебречь, либо интервалы значений признаков выбраны таким образом, что ошибки измерений практически не оказывают влияния на достоверность принимаемых решений относительно попадания измеряемой величины в заданный интервал.

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

Методы голосования по конъюнкциям. Алгоритмы типа "Кора".

Тесты, представительные наборы, проблемы перебора.

Пространства объектов для АВО. Обучающие и контрольные объекты. Метрические описания объектов в АВО.

Опорные множества в АВО. Функции близости. Веса объектов и признаков.

Формулы вычисления оценок. Эвристические обоснования.

Задачи оптимизации АВО. Совместные подсистемы систем неравенств.

Функционалы качества. Сложность моделей алгоритмов и проблема переобучения.

Общие пространства начальных и финальных информаций. Задачи синтеза корректных алгоритмов.

Разрешимость и регулярность задач распознавания. Регулярность по Ю.И. Журавлёву

Операции над алгоритмами. Расширение моделей.

Пространства оценок. Алгоритмы как суперпозиции.

Понятие полноты моделей алгоритмов и семейств корректирующих операций.

Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации.

Задачи с непересекающимися классами.

Класс поэлементных операций и отображений. Условия регулярности и полноты.

Полнота моделей АВО.

Полнота полиномиальных семейств корректирующих операций.

Логарифмическая граница степени корректирующих полиномов.

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

Личные инструменты
Разделы