Основные определения курса «Распознавание Образов»

Скрибцов П.В., 13.03.2005
Цели науки распознавания образов:

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

2)      построение обучающихся систем, которые умеют принимать решения без указания четких правил, а именно, систем, которые умеют сами синтезировать правила принятия решений на основе некоторого конечного количества «продемонстрированных» системе примеров правильных решений. 
Множество объектов задачи распознавания – множество всех объектов, которые могут теоретически встретиться в конкретной задаче их распознавания.
Образ (также pattern, shape, объект) – любой объект, для которого можно измерить набор определенных числовых признаков. Пример образа: буква, изображение, кардиограмма, и т.п.
Числовой признак (или просто признак). Формула или иное описание способа сопоставления объекту некоторой числовой характеристики, которое действует в рамках конкретной задачи распознавания образов. Для каждого объекта может быть определено несколько различных признаков, то есть несколько числовых характеристик.
При этом считается, что если все числовые значения всех признаков двух объектов совпадают, то такие объекты считаются идентичными, несмотря на то, что по сути объекты могут различаться. Например, если в какой-то задаче распознавания образов для шаров определен один только признак – радиус, то при этом красный шар с радиусом 10 в данной постановке задачи будет считаться идентичным синему шару с радиусом 10, поскольку значения их единственного признака совпадают.
Пространство признаков. N-мерное пространство, определенное для данной задачи распознавание, где N – фиксированное число измеряемых признаков для любых объектов. Вектор из пространства признаков, соответствующий объекту задачи распознавания это  N-мерный вектор с компонентами (х1,х2, …, хN), которые являются значениями признаков данного объекта.
ОБЪЕКТ->N признаков->N-мерный вектор признаков
Класс.  Неформализируемое (как правило) представление о возможности отнесения произвольного объекта из множества объектов задачи распознавания к определенной группе объектов. Для объектов одного класса предполагается наличие «схожести».  Для задачи распознавания образов может быть определено произвольное количество классов, большее 1. Количество классов обозначается числом S.
Гипотеза о схожести: Если для объекта А, характеризуемого вектором признаков х1 и для объекта Б, характеризуемого вектором признаков х2 выполняется следующее:

|x1-x2| -> 0, то вероятность что объекты А и Б принадлежат одному и тому же классу тоже стремится к единице.

 

Обучающая выборка. Неформальное определение классов данной задачи распознавания при помощи  примеров объектов, отношение которых к тому или иному классу заранее определено (известно). Математически обучающая выборка – это две сущности:

-         последовательность N-мерных векторов x(k), где индекс k = 1..K пробегает по всем номерам примеров.

-         последовательность чисел D*(k), значения которых равны номеру класса для объекта, характеризуемого вектором х(k).
Обучающая выборка может быть представлена в виде таблицы вида

	k
I	1	2	…	K
i=1	x11	x21		xK1
i=2	x21	x22		xK2
..	x31	x23		xK3
i=N	xN1	xN3		xKN

D*(k)

D*(1)

D*(2)

…

D*(K)

т.е. по горизонтали идет итерирование по номеру объекта-примера, а по вертикали по признакам и значению номера класса.

Значения классов примеров D*(1)…D*(K) называют указаниями учителя.

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

ДАНО:

1. Определено множество объектов распознавания
2. Определено K классов
3. Сформулированы N признаков объектов
4. Имеется обучающая выборка из M примеров, т.е. M объектов для каждого из которых известны
1. значения N признаков
2. указана принадлежность к классу
5. Имеется объект, про который известны его N признаков (задан вектор х из N-мерного пространства признаков)

НАЙТИ: для объекта, характеризуемого вектором признаков х, определить номер класса, по возможности, наиболее соответствующему истинному.
Классификатор. Функция (алгоритм) вида Ф(x,w), которая возвращает предполагаемый номер класса объекта, характеризуемого вектором признаков x. Работа функции также зависит от набора параметров, задаваемых вектором состояния классификатора w.
Например, для персептрона данная функция может иметь вид Ф(x,w) = sign(x*w), где *-скалярное умножение векторов. Очевидно, что для персептрона в таком случае размерность вектора w должна совпадать с размерностью вектора признаков х. Для классификатора методом построения эталонов (для задачи с S классами) классификатор может быть задан функцией

Ф(x,w) = arg min [ |x-x1| , |x-x2| , …, |x-xS| ], где под вектором w подразумевается следующий составной вектор, состоящий из вертикально «склеенной» цепочки из векторов x1…xS.

приставка arg означает, что ищется не минимальное значение, а НОМЕР минимального аргумента функции min (соответствующий, очевидно, номеру класса).

Структуру вектора w можно описать следующей диаграммой:

w =	x1	x1[1]	w1
		x1[2]	w2
		…	…
		x1[N]
	x2	x2[1]
		x2[2]
		…
		x2[N]
	…	…
	xS	xS[1]
		xS[2]
		…
		xS[N]	wS*N

Соответственно, количество параметров классификатора (размерность вектора w) для метода построения эталона = S*N.
Для метода ближайшего соседа:

Ф(x,w) = D*(arg min [ |x-x1| , |x-x2|, …, |x-xK| ]), где K – количество примеров в обучающей последовательности. x1…xK – вектора признаков примеров, D*(1)…D*(K) – указания учителя.  Очевидно структура вектора w состояния классификатора аналогична для случая метода построения эталонов и размерность вектора w равна N*K+K (К параметров прибавляется за счет необходимости хранить К значений указаний учителя). То есть вектор w хранит ВСЮ обучающую последовательность, которая может оказаться очень большой.
Среднеквадратичная ошибка обучения. Функция вида

E(w) =

[Ф(x1,w)-D*(1)]^2 +

[Ф(х2,w)-D*(2)]^2 +

…

[Ф(хK,w)-D*(K)]^2,
где  x1…xK, D*(1)…D*(K) – обучающая последовательность.
Задача обучения классфикатора.

Дано: постановка задачи распознавания.

Найти: arg min E(w), т.е. такое значение вектора w, при котором значение ошибки будет минимальным.
Способ обучения классификатора. Определенный математически, метод (алгоритм) решения задачи обучения классфикатора.
Применение обученного (настроенного) классификатора. Описание работы формулы Ф(x,w).
Неитеративные методы обучения. Методы для которых можно определить формулу

w = F(x1..xK,D*(1)…D*(K)),

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

w(n+1) = F(w(n)), которая служит поиску минимума функции ошибки.
Обобщающее свойство классификатора. Способность классификатора выдавать истинные значения классов для объектов, не входивших в обучающую выборку.
Типовые достоинства методов: простота, хорошие обобщающие свойства, низкие требования к памяти (маленький размер вектора состояния w), потребность в короткой обучающей последовательности, устойчивость к ошибкам в указаниях учителя.
Типовые недостатки методов: сложность, большая потребность в памяти для хранения вектора w, большая потребность в памяти для хранения промежуточных переменных, большое количество вычислений, необходимость в длинной обучающей последовательности, неустойчивость к ошибкам в указаниях учителя, невозможность применения для решения произвольных задач распознавания (а только для частных), для итеративных алгоритмов – плохая (медленная или нестабильная) сходимость алгоритма.
Кластеризация (Таксономия, самообучение, обучение без учителя). Процесс выделения в пространстве признаков областей, которые могли бы быть объединены в группы человеком либо согласно гипотезе о компактности. Кластеризация применяется для поиска закономерностей в данных, например, выделения неизвестных признаков, поиск объектов среди шумов.
Типовая постановка задачи кластеризации:

Дано: обучающая последовательность без указаний учителя x1…xK.

Найти: число кластеров М, построить Ф(x,w) разбивающую пространство признаков на М связанных областей, таких что:

-         в каждой области средняя плотность точек из обучающей последовательности максимальная

-         области разделены между собой промежутками с минимальной средней плотностью точек
Пример алгоритма кластеризации.

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

Алгоритм состоит из 3х этапов.
1ый этап. Составление М последовательных разбиений пространства на сферы радиусов R1…RM, где Ri +1 = Ri – dR, где dR = Rmax/G. G – параметр, запрашиваемый пользователем (например 20). R0=Rmax – это сфера в центре обучающей последовательности, с радиусом таким, чтобы все элементы обучающей последовательности в нее умещались. На псевдокоде алгоритм можно записать следующим образом:

1. Считать из файла обучающую последовательность в массив X[j], Y[j] j = 1..K (для случая если размерность пространства признаков = 2)
2. Зарезервировать массив меток точек обучающей последовательности T[j], j = 1..K
3. Запросить у пользователя G
4. Посчитать центр обучающей последовательности и Rmax
5. dR = Rmax/G
6. i = 0
7. R[i] = Rmax
8. Цикл А (разбиение на классы с заданным размером гиперсферы)
1. количество обнаруженных классов M = 0
2. обнулить отметки точек обучающей последовательности
3. Цикл Б (поиск всех кластеров с заданным размером гиперсфер)

                                                               i.      Выбор первой непомеченной точки из обучающей последовательности = х, если непомеченных точек не осталось, выход из цикла Б.

                                                             ii.      M = M + 1

                                                            iii.      Цикл В (поиск оптимального центра гиперсферы)

1.      r  = центр всех непомеченных точек, попавших в гиперсферу радиуса R[i], c центром х

2.      Померить расстояние между r и х = d,

3.      x = r

4.      если d меньше установленного порога (например, 0.1) – конец цикла B

                                                           iv.      Записать в файл i,х,R[i], M

                                                             v.      Пометить все точки, которые попали в гиперсферу с центром в х и радиусом R[i]

4. Конец Цикла Б
5. i = i+1
6. R[i] = R[i-1] – dR
8. Если R[i] < 0 конец цикла А

2й этап. Построение графика количества найденных классов от размера гиперсферы и поиск участка, где изменение радиуса «долго» не приводило к изменению количества классов.

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

Ё-1
Ж-0.2	К-0.5	С-0.3
И-1
К-0.3	Х-0.7

Е	Е	Е	Е	Е	Е
К	С	Ж	К	С	Ж
И	И	И	И	И	И
К	К	К	Х	Х	Х
0	0	0.0009	0	0	0.0001

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




Отсюда видно, что система примет решение «ЕЖИК», не смотря на то, что максимальную вероятность на первом уровне распознавания получило бы несуществующее сочетание «ЕКИХ», и более того, даже если рассматривать существующие комбинации «ЕЖИХ» и «ЕЖИК», комбинация «ЕЖИХ» имеет большую суммарную вероятность на первом уровне, тем не менее за большего счет встречаемости слова «ЕЖИК», выиграла именно эта «интуитивно угадываемая» комбинация букв.


ЗАДАЧИ.

1. Система распознает заглавные буквы латинского алфавита, предварительно выделяя из изображений символов 10 числовых признаков. Для обучения классификатора используется обучающая последовательность из 100 примеров каждой буквы. Найти количество параметров состояния классификатора (размерность вектора w) для методов
1. построения эталона
2. ближайшего соседа
3. к-ближайших соседей для радиуса гиперсферы R = 10
   
   
2. Предложите минимально достаточный набор признаков, для решения задачи распознавания овощей – картофель, свекла, огурец, помидор. Напишите примеры (эталоны) векторов признаков для всех классов. Для каждого признака и каждого класса постройте грубо график одномерного распределения p(x|Ck) с указанием масштаба. Для оценки распределения можно считать, что оно нормальное.
   
   
3. При решении задачи распознавания объекта с вектором признаков х методом к-ближайших соседей (радиус гиперсферы = 24, число признаков 2, количество элементов обучающей последовательности 170), классификатор выдал для всех классов одинаковую оценку P(Ck|x). При этом в гиперсфере с центром в точке х всего содержится 17 элементов обучающей последовательности. Определить количество элементов алфавита.
   
   
4. Две машины были распознаны роботом по совпадающим признакам – форма колес, радиатора, бампера, а также форме и цвету всех остальных деталей кузова и салона и отнесены к одному классу машин. Однако человек счел один объект пригодной машиной, а другой абсолютно нет. Какой дополнительный признак анализировал человек и не анализировал робот? Дайте математическое объяснение обоим случаям, применяя гипотезу о схожести.
   
   
5. Человек, ведя машину, с высокой вероятностью распознаёт, попадает ли правое или левое переднее колесо его автомобиля в ямку на дороге или нет. Разумеется человек никогда с линейкой не меряет ширину свого автомобиля или ширину дороги, равно как и не может зрительно точно оценить абсолютные расстояния. Поставьте задачу распознавания (алфавит, признаки, обучающая последовательность).
   
   
6. Может ли персептрон безошибочно решать задачу распознавания поступления или не поступления студента в вуз по признакам балл по математике и балл по физике, если для них заданы «проходные значения»? Почему? Нарисуйте пространство признаков, разметьте на нем области классов, покажите на рисунке разделяющую поверхность персептрона, которая всегда правильно «поступала» хороших студентов, но при этом принимала бы иногда и непроходных. Покажите разделяющую поверхность персептрона, которая точно «отправляла» бы всех непроходных студентов, но при этом страдала бы и часть «проходных».
   
   
7. Для задачи 6 укажите два способа , которыми можно было бы регулировать настройку классификатора чтобы склонить его к большей или меньшей лояльности к студентам. Подсказка: см. априорная вероятность, риск.
   
   
8. Выведите формулу Байеса, приведите знаменатель к форме, содержащий только выражения p(x|Ck) и P(Ck), покажите вывод формулы Байеса для непрерывных распределений в одномерном случае.
   
   
9. Выведите статистическую интерпретацию метода к-ближайших соседей и ближайшего соседа.
   
   
10. Алфавит состоит из 2х классов А и Б. В обучающую выборку входит 5 элементов класса А. При этом для априорных вероятностей классов известно, что P(А) = 0.5 P(Б). Если соотношение объектов А и Б в обучающей выборке соответствует наблюдаемому в «жизни», то какого примерно количество элементов класса Б в обучающей последовательности.