Основные определения курса Распознавание Образов (стр. 3 из 3)
Нейронная сеть. В данном документе не объясняется, так как это предмет отдельного курса. Однако понимание что это такое требуется. Нейронная сеть позволяет топологически разбить пространство признаков на области, соответствующие определенным классам, минуя шаг построения распределений. Каждый нейрон в таком случае реализует разделяющую поверхность в пространстве признаков.
Статистическая интерпретация метода к-ближайших соседей. Очень грубая оценка распределений дает:
Пусть V – гиперсфера заданного радиуса в пространстве признаков, с центром в точке соответствующей вектору (х) признаков распознаваемого объекта.
Пусть Nk – число объектов класса k, попавших в гиперсферу V
TOTALk – число объектов класса k, попавших в обучающую выборку
TOTAL – общее число объектов в обучающей выборке
ALL in V – общее число объектов обучающей выборки, попавших в V
p(x|Ck) ~ P(x in V | Ck) / V, V->0
P(x in V| Ck) ~ Nk (in V) / TOTALk если TOTALk ->inf
P(Ck) ~ TOTALk / TOTAL ~ Nk / ALL in V, V->inf
p(x) = P(x in V) / V, V->0 ~ [ALL in V / TOTAL] / V
P(Ck | x) = p(x | Ck) P(Ck) / p(x) ~
[Nk / (TOTALk*V)]*[TOTALk/TOTAL] * [V*TOTAL/[ALL in V]] = Nk/[ALL in V]
То есть P(Ck|x) = Nk/[ALL in V]
Заметим, что
P(C1|x)+P(C2|x)+… = N1/[ALL in V] + N2/[ALL in V] +… = [ALL in V]/[ALL in V] = 1
Получился метод к-ближайших соседей (к соседей заключенных в гиперкуб объемом V)
Т.е. апостерироная вероятность класса для вектора признаков х примерно равна отношению числа элементов данного класса в гиперсфере с центром в х к общему числу элементов обучающей последовательности в гиперсфере V.
Если [ALL in V] = 1, то получается метод ближайшего соседа.
Другие способы оценки распределений:
Параметрическая оценка нормального распределения: p(x|Ck) = Aexp(-(x-m)^2/g), где m – среднее для векторов признаков класса Ck, g – пропорциональна дисперсии, А – нормировочная константа (зависит от g).
Последовательная процедура распознавания – если измерение признаков дорого обходится, можно решать задачу последовательно для n измерений пространства признаков n = 1…n(max). На каждом шаге оценивать разрешаюшую способность
max P(Ck|x)
---------------------
max P(Cj|x) , j<>k
Если разрешающая способность превышает заданный порог (например 2 будет означать, что мы как минимум в 2 раза более уверены в одном из решений относительно любого другого), то принимается решение на этом шаге либо по максимальной вероятности либо исходя из матрицы потерь. В противном случае мы измеряем следующий признак до тех пор пока признаки не кончатся. Если разрешающий критерий не достигается при всех измеренных признаках необходимо принимать решение с теми вероятностями P(Ck|x), которые получились, либо вообще отказаться от принятия решения и выдать ответ «не могу решить задачу с требуемой точностью».
Распознавание при неизвестных априорных вероятностях. Самый простой способ – метод монте-карло. Подробности см. metogy.doc
Иерархические системы распознавания. Пример – распознавание слов. Вначале распознаются буквы, затем уже из букв слова. При этом решение на первом уровне распознавания не принимается, а лишь вычисляются вероятности. Затем вычисляются вероятности возможных образов получаемых на следующем шаге при всех возможных комбинациях распознавания первого уровня. Вероятности первого уровня и второго комбинируются и выбирается решение, учитывая обе вероятности (максимально правдоподобное решение с учетом вероятностей первого и второго уровня). Пример:
Допустим для следующего образа
система выдала следующие варианты на первом уровне распознавания:
| Ё-1 | ||
| Ж-0.2 | К-0.5 | С-0.3 |
| И-1 | ||
| К-0.3 | Х-0.7 |
Из этих вариантов можно составить следующие образы второго уровня (цифра внизу означает встречаемость данного слова)
| Е | Е | Е | Е | Е | Е |
| К | С | Ж | К | С | Ж |
| И | И | И | И | И | И |
| К | К | К | Х | Х | Х |
| 0 | 0 | 0.0009 | 0 | 0 | 0.0001 |
Для удобства напишем снизу все вероятностные составляющие решения первого уровня, и перемножим:
| Е | Е | Е | Е | Е | Е | |
| К | С | Ж | К | С | Ж | |
| И | И | И | И | И | И | |
| К | К | К | Х | Х | Х | |
| 0 | 0.0009 | 0 | 0 | 0.0001 | ||
| 0.5 | 0.3 | 0.2 | 0.5 | 0.3 | 0.2 | |
| 0.3 | 0.3 | 0.3 | 0.7 | 0.7 | 0.7 | |
| 0 | 0 | 0.000054 | 0 | 0 | 0.000014 | |
Отсюда видно, что система примет решение «ЕЖИК», не смотря на то, что максимальную вероятность на первом уровне распознавания получило бы несуществующее сочетание «ЕКИХ», и более того, даже если рассматривать существующие комбинации «ЕЖИХ» и «ЕЖИК», комбинация «ЕЖИХ» имеет большую суммарную вероятность на первом уровне, тем не менее за большего счет встречаемости слова «ЕЖИК», выиграла именно эта «интуитивно угадываемая» комбинация букв.
ЗАДАЧИ.
- Система распознает заглавные буквы латинского алфавита, предварительно выделяя из изображений символов 10 числовых признаков. Для обучения классификатора используется обучающая последовательность из 100 примеров каждой буквы. Найти количество параметров состояния классификатора (размерность вектора w) для методов
- построения эталона
- ближайшего соседа
- к-ближайших соседей для радиуса гиперсферы R = 10
- Предложите минимально достаточный набор признаков, для решения задачи распознавания овощей – картофель, свекла, огурец, помидор. Напишите примеры (эталоны) векторов признаков для всех классов. Для каждого признака и каждого класса постройте грубо график одномерного распределения p(x|Ck) с указанием масштаба. Для оценки распределения можно считать, что оно нормальное.
- При решении задачи распознавания объекта с вектором признаков х методом к-ближайших соседей (радиус гиперсферы = 24, число признаков 2, количество элементов обучающей последовательности 170), классификатор выдал для всех классов одинаковую оценку P(Ck|x). При этом в гиперсфере с центром в точке х всего содержится 17 элементов обучающей последовательности. Определить количество элементов алфавита.
- Две машины были распознаны роботом по совпадающим признакам – форма колес, радиатора, бампера, а также форме и цвету всех остальных деталей кузова и салона и отнесены к одному классу машин. Однако человек счел один объект пригодной машиной, а другой абсолютно нет. Какой дополнительный признак анализировал человек и не анализировал робот? Дайте математическое объяснение обоим случаям, применяя гипотезу о схожести.
- Человек, ведя машину, с высокой вероятностью распознаёт, попадает ли правое или левое переднее колесо его автомобиля в ямку на дороге или нет. Разумеется человек никогда с линейкой не меряет ширину свого автомобиля или ширину дороги, равно как и не может зрительно точно оценить абсолютные расстояния. Поставьте задачу распознавания (алфавит, признаки, обучающая последовательность).
- Может ли персептрон безошибочно решать задачу распознавания поступления или не поступления студента в вуз по признакам балл по математике и балл по физике, если для них заданы «проходные значения»? Почему? Нарисуйте пространство признаков, разметьте на нем области классов, покажите на рисунке разделяющую поверхность персептрона, которая всегда правильно «поступала» хороших студентов, но при этом принимала бы иногда и непроходных. Покажите разделяющую поверхность персептрона, которая точно «отправляла» бы всех непроходных студентов, но при этом страдала бы и часть «проходных».
- Для задачи 6 укажите два способа , которыми можно было бы регулировать настройку классификатора чтобы склонить его к большей или меньшей лояльности к студентам. Подсказка: см. априорная вероятность, риск.
- Выведите формулу Байеса, приведите знаменатель к форме, содержащий только выражения p(x|Ck) и P(Ck), покажите вывод формулы Байеса для непрерывных распределений в одномерном случае.
- Выведите статистическую интерпретацию метода к-ближайших соседей и ближайшего соседа.
- Алфавит состоит из 2х классов А и Б. В обучающую выборку входит 5 элементов класса А. При этом для априорных вероятностей классов известно, что P(А) = 0.5 P(Б). Если соотношение объектов А и Б в обучающей выборке соответствует наблюдаемому в «жизни», то какого примерно количество элементов класса Б в обучающей последовательности.