компьютерное распознавание и машинное обучение

машинное обучение

компьютерной обработки информации»
Принципы построения систем компьютерной обработки информации
Методы компьютерного

представления информации
Численные методы решения задач. Отыскание оптимальных решений
Раздел 2. «Методы обработки сигналов и изображений»
Случайности, шумы, искажения. Оценивание, фильтрация
Цифровые преобразования сигналов и изображений
Сравнение данных. Поиск данных
Сегментация и описание данных. Описание формы изображений
Анализ динамически меняющихся данных
Раздел 3. «Методы интеллектуального анализа данных»
Компьютерное моделирование человеческих рассуждений
Компьютерное распознавание образов и машинное обучение

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

Статистические методы. Линейные разделители. Максимизация правдоподобия и апостериорной вероятности. Байесовское обучение. Автоматическое распознавание. Ошибки первого и второго рода.
Обучение без учителя. Кластерный анализ. Иерархическая группировка. Методы, основанные на теории графов.
Биометрия. Критерии качества биометрической верификации и идентификации. Дактилоскопия. Обнаружение и распознавания лиц.

…,cl}, разбиение объектов по классам: сA(a): a∈A |→ с∈С, пространство описаний (признаков)

X, описание объектов признаками: xA(a): a∈A |→ x∈X. выборка объектов A⊆A, ||A||<+∞, выборка описаний X⊆X, ||X||<+∞. обучающая выборка: сX(x): xA(a)∈X |→ сA(a)∈С. распознающий алгоритм или классификатор fX(x): x∈X |→ с∈С.
Требуется: по информации о сX построить такой fX(x), который обеспечивает в некотором смысле наилучшее разбиение X на классы из C.

A

X

X

С

сA

fX

сX

описание

обучение

объекты

выборка

классификатор

классы

с′Y(x): x∈Y |→ с∈С, Y⊆X, Y∩ X=∅,

||Y||<+∞,
Критерий эмпирического риска на выборке Y:
JY(fX) = dH(fY, с′Y) / || Y ||,
dH(fY, с′Y) = ∑ x∈Y 1(f(x) ≠ с′(x)) – число ошибок классификации на выборке Y.
|| Y || = ∑ x∈Y 1 – объем выборки Y.

X

X

fX

сX

обучение

выборка X

классификатор

Y

сY

выборка Y

тестирование

ошибки

fX

с′Y(x): x∈Y |→ с∈С, Y⊆X, Y∩ X=∅,

||Y||<+∞,
Критерий эмпирического риска на выборке Y:
JY(fX) = dH(fY, с′Y) / || Y ||,
dH(fY, с′Y) = ∑ x∈Y 1(f(x) ≠ с′(x)) – число ошибок классификации на выборке Y.
|| Y || = ∑ x∈Y 1 – объем выборки Y.
Критерий среднего ожидаемого риска
JX(fX) = EY⊆X {JY(fX)},
где EY⊆X {.} – математическое ожидание по всем возможным выборкам Y⊆X.
Требуется: Определить оператор оптимального синтеза θ, доставляющий минимум критерию JX(fX):
θ: сX∈ΩX |→ fX∈ΩX,
θ = arg minθ′ {JX(θ′сX)}, (1)
где ΩX и ΩX – множества всех возможных разбиений выборки X и пространства X по классам из C.

θ, доставляющий минимум критерию JX(fX):
θ: сX∈ΩX

|→ fX∈ΩX,
θ = arg minθ′ {JX(θ′сX)}, (1)
где ΩX и ΩX – множества всех возможных разбиений выборки X и пространства X по классам из C.

Проблемы:
. Невозможно оценить матожидание, поскольку нельзя перебрать все подвыборки Y⊆X.
. Невозможно оптимизировать критерий ожидаемого риска, поскольку в момент обучения тестовые выборки нам неизвестны.
. Невозможно оптимизировать критерий ожидаемого риска на ΩX, поскольку невозможно перебрать все разбиения пространства признаков.
. Невозможно оптимизировать критерий ожидаемого риска по θ′, поскольку невозможно перебрать все операторы синтеза классификаторов (стратегии обучения).

классификаторов FX
Класс алгоритмов обучения Θ для классификаторов из FX на

выборках X⊆X.
Оператор обучения:
θ∈Θ: сX∈ΩX |→ fX∈FX ⊆ΩX,
θ = arg minθ′∈Θ {JY(θ′сX)}, (2)

X

сX

X

сX

FX

fX

классификаторов FX
Класс алгоритмов обучения Θ для классификаторов из FX на

выборках X⊆X.
Оператор обучения:
θ∈Θ: сX∈ΩX |→ fX∈FX ⊆ΩX,
θ = arg minθ′∈Θ {JY(θ′сX)}, (2)

X

сX

X

сX

GX

gX

минимум в точке fX ≡ сX, заведомо непригодный для неизвестной

тестовой выборки Y.
Решение: теория оценки и контроля переобучения
Эмпирический риск оценивается по обучающей выборке, но сложность решающего правила искусственно ограничивается.
Дополнительные компоненты задачи обучения:
Сложность класса классификаторов Q(FX).

…

VC-размерность класса классификаторов

Требуется: минимизировать наблюдаемый риск с регуляризацией по сложности класса обучаемого

классификатора:
θ∈Θ: сX∈ΩX |→ fX∈FX ⊆ΩX,
θ = arg minθ′∈Θ {JX(θ′сX) + αQ(FX)} , (3)
где α≥0 – параметр регуляризации, определяющий компромисс между точностью на X и сложностью классификатора, от которой зависит поведение fX на тестовой выборке Y.

Решение: Метод структурной минимизации риска
Пусть даны: суперкласс FX и последовательность вложенных классов классификаторов нарастающей сложности:
F0X ⊆ F1X ⊆ … ⊆ FjX ⊆ … ⊆ FX ⊆ ΩX :
Q(F0X) ≤ Q(F1X) ≤ … ≤ Q(FjX) ≤ … (4)
Задача (3) последовательно решается для FjX, j=0,1,2,…, пока значения критерия не перестанут улучшаться.
Значение α подбирается методом кросс-валидации с валидационной выборкой Z⊆X, Z∩ X=∅, ||Z||<+∞.

объектах обучающей выборки.
Вапник В. Н. Восстановление зависимостей по эмпирическим

данным. - М.: Наука, 1979.
Воронцов К.В. Комбинаторная теория надёжности обучения по прецедентам. Диссертация на соискание ученой степени доктора физико-математических наук. ВЦ им. А. А. Дородницына РАН. Москва, 2010.

X

gX

gX

X

fX

FX

fX

вероятностью принадлежать к одному классу.
Айзерман М. А., Браверман Э.

М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. 320 pp.
Хачай М. Ю. Топологический подход к выводу условий равномерной по классу событий сходимости частот к вероятностям. // Интеллектуализация обработки информации: 8-я международная конференция (ИОИ-8), Кипр, г.Пафос, 2010 г.: Сборник докладов. – М.: МАКС Пресс, 2010, с.91-94.

Неразличимость + Компактность ⇒ мы можем рассматривать задачу синтеза классификатора как задачу наилучшей разметки (optimal labeling) или «раскрашивания» точек обучающей выборки, связанных отношениями соседства. Таким образом, из области распознавания образов или машинного обучения мы переходим в область анализа изображений и можем применять методы машинного зрения и машинной графики.

компактный класс

локально компактные классы

некомпактные классы

О

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

Источники основных идей

Размеры: 36 37 38 39 40 41 42 43 44 45 46

A

описания

объекты

X

Обувь:

Пол: Ж Ж М Ж Ж Ж М М М М М

(С) Учитель

О

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

Источники основных идей

Размеры: 36 37 38 39 40 41 42 43 44 45 46

описания

X

Выборка: Ж Ж М Ж Ж Ж М М М М М

(С) Учитель

R1

p(x/0)>p(x/1)

Возможность 01

Возможность 10

p(x/1)>p(x/0)

Вероятнее: Ж Ж Ж Ж М М М М М М М

Истина где-то здесь!

Здесь искаженная информация

классов на выборке

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

поскольку хоть какое-то значение случайная величина принимает с вероятностью 1.

риск при принятии решения:

риск при принятии решения:

различные по признакам

метриках Минковского:

одна из наиболее известных итеративных процедур кластерного анализа

Начиная всего с двух нейронов, алгоритм последовательно изменяет (по большей

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

векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных

ошибок; соединить узлы связью, установив ее возраст равным 0.
. Подать на вход нейросети вектор x.
. Найти два нейрона s и t, ближайших к x, т.е. узлы с векторами весов ws и wt, такими, что  ||ws - x||2 минимальное, а ||wt - x||2 второе минимальное значение расстояния среди всех узлов.
. Обновить локальную ошибку нейрона-победителя s путем добавления к ней квадрата расстояния между векторами ws и x: Es←Es+||ws - x||2
. Сместить нейрон-победитель s и всех его топологических соседей (т.е. все нейроны, имеющие соединение с победителем) в сторону входного вектора x на расстояния, равные долям εw и εn от полного. ws←ws+εw·(ws-x) wn←wn+εn·(wn-x)
. Увеличить на 1 возраст всех соединений, исходящих от победителя s.

t соединены, обнулить возраст их связи. В противном случае создать связь

между ними.
Удалить все соединения, возраст которых превышает agemax. Если после этого имеются нейроны, не имеющие связей с другими узлами, удалить эти нейроны.
Если номер текущей итерации кратен λ, и предельный размер сети не достигнут, создать новый нейрон r по следующим правилам:
Найти нейрон u с наибольшей локальной ошибкой.
Среди соседей u найти нейрон v с максимальной ошибкой.
Создать узел r "посредине" между u и v: wr=(wu+wv) / 2
Заменить связь между u и v на связи u и r, v и r.
Уменьшить ошибки нейронов u и v, установить значение ошибки нейрона r.
Eu←Eu·α
Ev←Ev·α
Er←Eu
Уменьшить ошибки всех нейронов j на долю β.
Ej←Ej – Ej· β
Если критерий останова не выполнен, перейти к шагу 2.

исходя из топологии и распределения самих данных
Пример сравнения кластеризации

(64 кластера)

сегментации изображения
Цветовое пространство: CIE Lab
Количество кластеров: 32


Параметры:

совокупность биометрических характеристик, основанных на биологических особенностях человеческого тела. В

качестве таких биометрических характеристик могут выступать: голос, почерк, отпечатки пальцев, геометрия кисти руки, рисунок сетчатки или радужной оболочки глаза, лицо и ДНК.
Традиционные методы защиты не исключают возможности потери или кражи информации, вследствие чего она становится доступной незаконным пользователям. Уникальный биометрический идентификатор, каковым является, например, отпечаток пальца или изображение лица, служит ключом, который невозможно потерять. Биометрическая система безопасности позволяет отказаться от парольной защиты либо служит для ее усиления. Одной из основных причин, которые существенно повысили значимость биометрического распознавания, явилось повышение требований к функциональным возможностям автоматических систем безопасности, расположенных в общественных местах (вокзалы, аэропорты, супермаркеты и т.п.), связанные с необходимостью в реальном времени выполнять необходимые действия по установлению личности присутствующих на контролируемой территории людей, причем, зачастую, скрытно, то есть не только бесконтактно (дистанционно), но и без специального сотрудничества (специального предъявления биометрических признаков) со стороны идентифицируемых персон.

Rate) – вероятность принятия “чужого” за “своего”



FRR(False Reject

Rate) – вероятность принятия “своего” за “чужого”



где fgen(λ), и fimp(λ) ПВ своих и чужих сравнений

Эталон

Приложение: Биометрия

FAR

FRR

FAR = FRR

вероятность попадания в первые n кандидатов
Биометрия