57 Правило ближайшего соседа как пример непараметрического метода

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

Правило БС = w_БС (x)=w’ : x’  w’ :

Вероятность ошибки классификации БС - правила не более чем вдвое больше минимальной вероятности ошибки классификации, обеспечиваемой байесовским решающим правилом:

,

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

58. Основы мгуа.

МГУА позволяет:

-не заботиться о выборе сложности полинома

-не предусматривает ограничений на размерность вектора x

-позволяет ограничить время определения коэффициентов разумными пределами

-может работать при обучающих выборках малого объема.

Рассмотрим общую схему МГУА.

Вся выборка делится на обучающую и проверочную: . Входной вектор имеет размерность N .

1-ый ряд - на основе обучающей последовательности строятся частные описания от всех попарных комбинаций исходных аргументов, приближающие по МНК выходную переменную :

Из этих моделей выбирается некоторое число лучших по критерию селекции (используя проверочную последовательность).

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

Под опорной функцией будем понимать вид полинома ч/з. кот. будут выражаться переменные k уровня ч/з переменные k-1 уровня.

Виды опорных функций:

А) .

В) .

С) .

D) .

Есть несколько способов отбора лучших кандидатов частичных описаний передаваемых на определенном слое. Рассмотрим критерий регулярности (точности)

Критерий остановки алгоритма МГУА определяется для каждого уровня значение критерия для всего уровня: либо среднее значение, либо лучшее значение критерия. Пусть значение критерия 1-го уровня -E1 а 2-го –E2, Если E2 «лучше» в смысле заданного критерия (регулярности или несмещенности), то переходим к следующему уровню. Если же нет, то конец работы алгоритма.

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

59. Применение мгуа для решения задачи ро

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

Пусть инвариантным свойством образов класса будет некоторая функция f(X). Инвариантность означает, что функция остается почти одинаковой для всей совокупности образов одного класса, т. е. для класса ; для класса и т. д. Функцию f(X) можно представить как поверхность в многомерном пространстве, построенную так, что образам разных классов соответствуют несвязные отрезки на оси f.

Решающее правило, основанное на построенной функции, в случае двух классов записывается так:

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

Если же классов больше двух, то решающее правило принимает вид , где .

Лингвистический подход к РО

61. Постановка задачи распознавания лингвистических образов.

Пусть изобр-ие предст. собой цепочки в нек-м алфавите V. Любое подмножество есть формальный язык над алфавитом , то каждый класс представляет некоторый язык. Задача классификации в определении принадлежности каждой цепочки к одному из языков.

62. Три способа решения задачи распознавания лингвистических образов.

1. Принцип сравнения с эталоном

, D(z_i,x) - мера близости.

2. Классификация на основании применения наборов синтаксических правил

xw_i если х не противоречит набору правил S_i (грамматика)

3. Решение задачи распознования на основе вывода в формальной грамматике. Х относится к языку той грамматики вывод в которой оказался успешным.

63. Зад. восст. грамматики по обучающей выборке

A: S_t  |A| G_t

S_t={x₁,…,x_t}

A – Алгоритм восстанавливающий грамматику

Задачу восстановления грамматики по выборке будем называть разрешимой, если существует такой алгоритм А, который строит грамматику за конечное число шагов.

64. Информаторное представление задачи восстановления грамматики.

Будем говорить, что задача восстановления грамматики G* дана в информативном представлении, если выполн. следующие условия.

1) t

2) xL(G*) м. найти t’:t>t’, xS_t⁺

3) yV_t*\L(G*) м. найти t’’:t>t’’, yS_t ^-

65. Текстуальное представление задачи восстановления грамматики.

Будем говорить, что зададача восст. грамматики G* дана в текстуальном представлении, если выполняется:

1) t

2) xL(G*) м. найти t’:t>t’, xS_t

66. Теорема о разрешимости для информаторного представления.

Th.: Пусть Г - это класс разрешимых грамматик. Тогда при информаторном представлении задача восст. грамматики разрешима G*Г

67. Теорема о неразрешимости для текстуального представления

Th.: Г={грамматики, порожд. все конечные языки}U { порожд.  язык}

Тогда задача восст. грамматики при текстуальном представлении для произвольной грамматики из Г неразрешима.

68. Два класса алгоритмов восстановления грамматики.

Существует 2 класса таких алгоритмов

1) восстановление перечислением

2) восстановление индукцией (напр. алгоритм Фельдмана)

69. Алгоритм Фельдмана.

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

Алгоритм можно разделить на 3 части:

1) формирование не рекурсивной грамматики

2) преобразование в рекурсивную

3) упрощение грамматики.