2015 Экзаменационные вопросы и Теормин (с ответами) по курсу ММО (1185246), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Байесовский классификатор.

Относит объект в тот класс, для которого условная вероятность P(класс i | x) максимальна. (при решении как правило нужно считать по формуле Байеса).

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

1. Метод k-ближайших соседей.

Алгоритм классификации объектов. Оценка условных вероятностей P(K _i | x) ведётся по ближайшей окрестности точки x, содержащей k признаковых описаний объектов обучающей выборки (k соседних объектов). В качестве оценки выступает отношение k_i/k , где k_i - число признаковых описаний объектов обучающей выборки из класса K_i внутри рассматриваемой окрестности точки x (т.е. в итоге объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента). Окрестность задаётся с помощью функции расстояния ρ(x, x) заданной на декартовом произведении X×X , где X - область допустимых значений признаковых описаний. В качестве функции расстояния может быть использована стандартная эвклидова метрика или метрика Хэмминга в случае с бинарными признаками. Единственным параметром для настройки является число соседей (k).

1. Комбинаторно-логические методы . Тупиковый тест. Представительный набор.

(Тут надо полагаться на покрытия и тесты, представлением элементов вектором признаков)

Принцип частичной прецедентности. При распознании диагностике важны некоторые комбинации (а именно конкретные наборы, а не целые классы)

Тест – это набор признаков, позволяющих разделить классы. (т.е. любые 2 объекта из любых 2-х классов отличаются хотя бы по одному признаку из теста)

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

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

Поиск теста – это задача о покрытии, NP-трудная.

Алгоритм типа Кора – когда ищется не только набор признаков, но набор признаков со своим описанием.

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

Из существования теста следует существование набора, но не наоборот.

1. Алгоритм вычисления оценок.

1. Выделяется множество подмножеств, которое называется «система опорных векторов ».

2. Функция близости сравнивает 2 объекта по некоторому опорному множеству. (например =1 если все признаки совпали, или =0 если нет (а может учитываться какой-то порог, …))

1. Модель нейрона. Перцептрон Розенблатта.

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

Сигналы, приходящие на вход перцептронов рецепторов интерпретируются как входные признаки.

3 типа нейронов:

1. нейроны-рецепторы (сенсоры)

2. внутренние нейроны - имеет множество входных связей от рецепторов или внутренних нейронов

3. реагирующие нейроны - имеет множество входных связей от рецепторов или внутренних нейронов

Все сигналы, входящие в нейрон обрабатываются: z = w₀ + ∑w_iu_i , после чего применяется активационная функция Ф(z) - и это значение становится результатом нейрона и выдаётся другим нейронам (один сигнал с выхода может передаваться многим другим на вход) (u_i - значения с других нейронов, w_i - веса внутри нейрона, w₀ - параметр сдвига)

Перцептрон Роззенблатта (1957) - нейросетевая модель с одним единственным нейроном

Используется для задачи распознавания с 2-мя классами, активационная функция Ф=1, если z>=0, Ф= -1, если z<0

Особенность перцептрона - простая и эффективная процедура обучения (вычисления w_i)

Настройка параметра происходит по обучающей выборке. (предварительно признаковое описание преобразуется в векторные сигналы, а затем вектора описаний из класса K₂ умножаются на -1, а из K₁ не меняются)

1. Многослойный перцептрон. Методы обучения.

Многослойный перцептрон - нейросетевые методы распознавания, задаваемые комбинациями связанных между собой нейронов.

Обладает существенно более высокой аппроксимирующей способностью

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

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

1. Допускаются связи между только между нейронами, находящимися в соседних слоях.

2. Связи между нейронами внутри одного слоя отсутствуют.

3. Активационные функции для всех внутренних нейронов идентичны

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

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

Процедура обучения перцептрона (одного):

1. Случайно выбирается нулевое приближение вектора весовых коэффициентов

2. Преобразованные описания обучающей выборки последовательно передаются на вход перцептрона

3. Если писание x^(k), поданное на k-м шаге классифицируется неправильно, то происходит коррекция w^(k+1) = w^(k) + x^(k), если классификация верна, то ничего не меняется.

4. Повторяем до тех пор, пока:

   1. достигается полное разделение объектов из классов K1 и K2

   2. повторение подряд заданного числа операций не приводит к улучшению разделения

   3. оказывается исчерпанный заранее заданный лимит итераций

Процедура обучения многослойного перцептрона - метод обратного распространения ошибки:

Потери классификации объекта будем считать как сумму квадрата разности между выходом реагирующего нейрона и тем, что он должен был выдать (т.е. 0, когда объект не принадлежит классу, и 1, иначе)

Качество аппроксимации на обучающей выборке - это сумма потерь для каждого объекта выборки. (веса фиксированны). Цель - подобрать такие веса, чтобы улучшить качество аппроксимации.

Основа обучения - метод градиентного спуска.

Метод градиентного спуска - оптимизирует произвольный функционал F(θ), θ^(k) = θ^(k-1) + n * grad(F(θ^(k-1)))

n - парамер, задающий размер каждого шага (learning rate)

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

1. Метод опорных векторов. Основные понятия. Возможность нелинейного разделения.

Основная идея метода — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве.

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

1. Методы решающих деревьев и решающих лесов.

Decision tree cредство поддержки принятия решений, использующееся в статистике и анализе данных для прогнозных моделей.

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

При анализе решений «дерево решений » используются как визуальный и аналитический инструмент поддержки принятия решений, где рассчитываются ожидаемые значения (или ожидаемая полезность) конкурирующих альтернатив.

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

1. Методы построения коллективных решений в распознавании.

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

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

Важно что ошибка взвешанного решения не больше, чем сумма взвешанных ошибок. Т.е. коллективное решение всегда даёт результат - не хуже.

На паре говорили, что бустниг (bootstrap aggregating) - это изменение обучающей выборки, путём замены случайных объектов.

А бэггинг - это идея повышения веса объектов, которые были неправильно распознаны.

1. Основы алгебраической коррекции.

Задача распознавания в алгебраической теории рассматривается как задача построения по начальной информации I о классах K1, . . . , KL для предъявленной для распознавания выборки

Sc = {s1 , . . . , sq } правильной информационной матрицы ∥αj ∥L×q .

/* or for dummies */

Вспомним, что классификация это ROC, т.е. R * C, где R – это оператор, ставящий каждому прецеденту некоторую характеристику – вероятность отнесения к каждому из классов. А С – это оператор, решающий по характеристикам к какому классу, будем принадлежать.

Журавлёв предложил ввести операции:

1. Почленное умножение матриц

2. Почленное сложение матриц

3. Почленное умножение на число

Тогда S (матрица, где столбец – прецендент из обучающей выборки) * R = Г для каждого классификатора нашего ансамбля можно рассматривать как набор. Для которого существует замыкание из множества всех матриц Г, которые получаются из 1-3 пункта. Тогда существует в этом наборе Г_corr - корректная матрица (матрица, для которой корректно работает стандартное решающее правило).

В итоге надо в замыкании найти корректную матрицу.

1. Задача анализа выживаемости (краткое определение)

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

Выбор метода для анализа выживаемости зависит от исходных данных:

• наличия зависимой и независимых переменных-предикторов;

• наличия или отсутствия цензурированных данных.

Из слайдов: Целью таких задач является восстановление вероятности того, что ожидаемое критическое событие с исследуемым объектом произойдёт не ранее произвольного момента времени. Таким критическим событием может быть отказ изделия в технике, гибель испытуемого организма в биологии или смерть пациента в медицине. Таким образом целью анализа является вычисление функции (кривой) выживаемости S(t) = P{T > t} , где через T обозначено время наступления критического события, P {T > t} обозначает вероятность того, что критическое событие произойдёт позже момента t.

Характеристики

Список файлов ответов (шпаргалок)