Основные методы, применяемые для распознавания рукописного текста

А.Б.Мерков

начальная версия: 24 апреля 2002
текущая версия: 13 декабря 2005
исправление ошибок: 10 октября 2008 1

59

Contents

1   Распознавание отдельного объекта
    1.1   Обучающиеся системы распознавания
    1.2   Искусственные нейронные сети (ANN, Artificial Neural Networks)
        1.2.1   Многослойный перцептрон (MLP, Multi-Layer Perceptron)
        1.2.2   Сети с радиальными базисными функциями (RBF, Radial Basis Function)
    1.3   Обучающееся векторное квантование (LVQ, Learning Vector Quantization)
    1.4   Метод опорных векторов (SVM, Support Vector Machine)
        1.4.1   Линейно разделимый случай: опорные вектора (support vectors)
        1.4.2   Линейно неразделимый случай: ядра (kernel functions)
        1.4.3   Обобщения базовой модели SVM
2   Распознавание (частично) упорядоченных наборов объектов
    2.1   Скрытая марковская модель (HMM, Hidden Markov Model)
        2.1.1   Скрытая марковская модель с дискретным временем, конечным пространством состояний и конечным пространством наблюдаемых
        2.1.2   Более общие скрытые марковские модели и объединение их с нейронными сетями и другими распознавателями
    2.2   Распознавание графов
        2.2.1   Распознавание слов с распознавателем букв
        2.2.2   Распознавание слов без распознавателя букв
Не всякий браузер хорошо показывает эту страницу (Netscape 4.* почти годится, с точностью до знака прямого произведения , IE5 - чуть хуже, еще и схлопывает двухэтажные индексы). Если есть проблемы или хочется распечатать, попробуйте постскриптовскую версию, упакованную или распакованную.

1  Распознавание отдельного объекта

1.1  Обучающиеся системы распознавания

Задача распознавания (точнее, классификации) объекта ставится следующим образом. Имеется некоторый способ кодирования объектов (например, рукописных букв), принадлежащих заранее известному конечному множеству классов C={C1 ,...,Cq}, и некоторое конечное множество объектов (обучающее множество), про каждый из которых известно, какому классу он принадлежит. Нужно построить алгоритм, который по любому входному объекту, не обязательно принадлежащему обучающему множеству, решает, какому классу этот объект принадлежит, и делает это достаточно хорошо. Качество распознавания оценивается как вероятность (т.е.частота) ошибки классификации на другом конечном множестве объектов с заранее известными ответами (тестовом множестве).
Сразу несколько уточнений. При распознавании вообще, в отличие от классификации, бывает нужно оценивать и численные характеристики объектов (например, объем нефтяного месторождения по сейсмограмме). Обучающее и тестовое множество могут не быть даны заранее, а пополняться в процессе работы распознающего алгоритма. На вход распознавания почти всегда попадают объекты, никаким боком не укладывающиеся в классификацию (в примере с рукописными буквами - кляксы, слипшиеся буквы, картинки и т.п.). Качество распознавания можно оценивать не вероятностью ошибки, а какой-либо другой функцией от ошибки, поскольку разные ошибки по-разному стоят. Кроме того желательны гарантии (конечно, статистические) того, что на любом другом тестовом множестве частота ошибки распознавания будет почти такой же.
Чтобы не писать по абзацу уточнений на каждый абзац текста, предупреждение. Ниже безо всяких оговорок рассматриваются только простые частные случаи, к тому же специально подобранные для удобства рассмотрения, а общие случаи даже не упоминаются. Читайте литературу .
Типичная система распознавания состоит из трех частей: извлечение признаков, собственно распознавание и принятие решения.
Извлечение признаков - это преобразование входных объектов к единообразному, компактному и удобному виду с потерей подавляющей части содержащейся в объекте информации, слабо влияющей на классификацию. Удобным оказывается представление объекта точкой стандартного евклидова пространства Rd, принадлежащей некоторому фиксированному компакту (кубу, шару, сфере, ...). Размерность d должна быть достаточно большой для успешного (в смысле качества) распознавания и достаточно малой для успешного (в смысле скорости) распознавания - реально это порядка нескольких десятков. Способ извлечения признаков зависит от природы и исходной кодировки объектов и подбирается вручную. Например, траекторию мыши или пера, исходно закодированную последовательностью произвольной длины (порядка сотни), состоящей из пар координат точки, удобно кодировать последовательностью фиксированной длины пар коэффициентов аппроксимирующих траекторию полиномов небольшой степени (порядка десятка), да еще и свободные члены можно отбросить, как не влияющие на классификацию. Весьма изощренный способ извлечения признаков из растровой картинки реализован в компьютере Newton [5] .
Оставшаяся часть распознавания - это, казалось бы, алгоритм, разбивающий пространство признаков на части, соответствующие заданным классам C1,...,Cq. Но все не так просто. Во первых, изрядная часть пространства признаков не соответствует никакому классу. Во-вторых, наоборот, некоторые точки могут изображать объекты нескольких классов, и даже не потому, что пространство признаков построено плохо. Что это за строчные латинские буквы: char_ad.gif, char_el.gif, char_nu.gif? Вы уверены? А насколько? Удобнее строить распознающий алгоритм, вычисляющий для каждой точки пространства признаков вероятности (в смысле: степень уверенности) того, что эта точка принадлежит каждому из классов, т.е. реализующий отображение F из пространства признаков Rd в единичный куб в пространстве Rq. Желаемые значения F в точках пространства признаков, соответствующих обучающему множеству, известны, так что остается только построить в некотором смысле аппроксимирующее отображение. Качество аппроксимации будет проверяться не на всей области определения, а только на тестовом множестве.
Интерпретацией вычисленных вероятностей занимается отдельная от распознавания процедура принятия решений, которая строится вручную и не зависит ни от природы входных объектов, ни от пространства признаков, ни от обучающих данных. Она зависит только от того, для чего эта система распознавания предназначена. Например, если она используется как безответственная гадалка, то она просто выдает номер наиболее вероятного класса. Если она используется как ответственная гадалка, то она выдает номер наиболее вероятного класса, если его вероятность существенно больше вероятностей других классов, и отвечает "не знаю" в противном случае. Если она используется для генерации гипотез, то она выдает номера нескольких (например, пяти) наиболее вероятных классов и их вероятности.
В дальнейшем обсуждается только обучаемая часть системы распознавания, т.е. отображение F.
Как правило отображение F ищут в каком-либо фиксированном, но достаточно большом классе отображений, параметризованных некоторым параметром, т.е. распознающий алгоритм - это вектор-функция двух векторных переменных Y=F(W,X), где X - d-мерный вектор признаков, Y - q-мерный вектор вероятностей, а W - параметр. Как правило параметр тоже является вектором в евклидовом пространстве, причем очень многомерном (порядка тысяч), а функция F - непрерывна и даже дифференцируема. Обучение распознающей системы - это (опять же, как правило, но не всегда) подбор хорошего значения параметра W. В каком смысле и в какой степени хорошего - предмет многочисленных научных работ и экспериментов с системами распознавания. Канонического универсального алгоритма обучения нет.
Пусть X1,...,XN - d-мерные вектора признаков объектов обучающего множества, Y1,...,YN - соответствующие им q-мерные вектора вероятностей (обычно эти вектора - базисные, т.е. все координаты каждого равны 0 кроме некоторой одной, равной 1). Вектора признаков можно считать независимыми одинаково распределенными случайными величинами. Распределение этих случайных величин заранее неизвестно, но оно существует и позволяет говорить о вероятностях. Хорошо бы, чтобы распознающая функция F(W,·) хорошо приближала "правильное распознавание" X ® Y по вероятностной мере, т.е. чтобы вероятность большого отклонения - достаточно большого, чтобы получить неправильный ответ при распознавании, - F(W,·) от этого заданного на обучающем множестве отображения была мала. Но обучать хорошему приближению по неизвестной вероятностной мере довольно трудно, поэтому чаще идут следующим более простым путем.
Пусть E - некоторая функция ошибки, т.е. неотрицательная функция пары q-мерных векторов, равная нулю на парах равных векторов (например, какое-либо расстояние между векторами или какая-то степень этого расстояния). Тогда обучение распознающей системы - это поиск значения Wm параметра W, минимизирующего среднюю ошибку на обучающем множестве
 1
N
 N
е
i=1 
 E(F(W,Xi),Yi)  .
Естественно, хочется найти точку глобального минимума, но в нетривиальных случаях обучение гарантирует только близость к какому-либо локальному минимуму.
Вопрос, в каких случаях так обученная распознающая система способна к обобщению, т.е. может успешно распознавать вектора, на которых не обучалась, исследуется экспериментально или отдается на откуп статистической теории обучения. Для того, чтобы обученная распознающая система могла обобщать, размерность пространства ее параметров должна быть меньше, желательно намного меньше, размерности пространства обучающих последовательностей векторов, равной N(d+q). Эта неформальная оценка получается просто из соображений топологической размерности. Более точные оценки используют размерность Вапника-Червоненкиса [6] и могут гарантировать, что обученная на некоторой достаточно длинной последовательности распознающая система с большой вероятностью почти так же хорошо распознает и любую другую последовательность.
Такое обучение - в котором про обучающие вектора признаков известно, какому классу они принадлежат - называется обучением с учителем. Бывает еще обучение без учителя - когда имеется некоторое обучающее множество без знания о том, какой элемент принадлежит какому классу. Как ни странно (точнее, наоборот, совершенно естественно), такое обучение тоже бывает полезным, поскольку позволяет распознающей системе "понять", какие области в пространстве признаков существенны для распознавания, а про какие можно не заботиться, поскольку реальные вектора признаков в них почти никогда не попадают.
Далее рассматриваются некоторые методы построения и обучения распознающих систем, т.е. параметризованных функций F(W,X). Подробности того, что предшествует обучению, как можно его проводить, что за ним следует и как все это интерпретировать с теоретико-вероятностной точки зрения, хорошо описаны в книге [1]. Теоретические оценки ошибок распознавания подробно рассмотрены в книге [20]. Практически в любой толстой книге, содержащей в названии слова "statistical learning", (например, [31]) описаны разные распознающие системы, способы их обучения, примеры применения и оценки качества работы, хотя одни и те же вещи в разных книгах могут называться по-разному.

1.2  Искусственные нейронные сети (ANN, Artificial Neural Networks)

Теория нейронных сетей возникла в 40-60-х годах в результате совместных попыток физиологов и кибернетиков (так тогда назывались специалисты по computer science) понять и смоделировать работу мозга. Получилась следующая модель.
Мозг состоит из очень большого числа (порядка 1011) клеток (нейронов), каждая из которых имеет длинный хвост (аксон) и большое число (порядка 104) ответвлений (дендритов), касающихся аксонов других нейронов и/или входных рецепторов. Через эти зоны касания (синапсы) может передаваться информация (электрохимический потенциал, что бы это ни значило). Каждый нейрон является простеньким компьютером: потенциал нейрона (и его аксона, играющего роль выхода) является функцией от потенциалов синапсов его дендритов (входов), причем функцией вполне определенного вида. А именно, каждый нейрон имеет два устойчивых состояния (возбужденное и невозбужденное) и соответствующие им значения потенциала, одинаковые для всех нейронов. Каждый нейрон вычисляет линейную комбинацию потенциалов входных синапсов, сравнивает ее с пороговым значением и переходит в возбужденное (невозбужденное) состояние если эта линейная комбинация больше (соответственно, меньше) порогового значения2. В совокупности мозг вычисляет некоторую вектор-функцию: зависимость потенциалов нейронов (достаточно рассматривать не все нейроны, а только связанные своими аксонами с исполнителями) от потенциалов входных рецепторов. А вся нетривиальность работы мозга состоит в том, что пороговые значения (по одному на нейрон, итого порядка 1011) и коэффициенты линейных комбинаций (по одному на дендрит, итого порядка 1015), вообще говоря, различны и могут изменяться со временем. Это изменение коэффициентов называется обучением.
За последующие полвека модель мозга сильно эволюционировала, но в качестве мотивации искусственных нейронных сетей использовалась именно такая упрощенная устаревшая модель.
В искусственных нейронный сетях, применяемых для вычислений (в частности, для распознавания) обычно вводятся некоторые "нефизиологические" ограничения и снимаются некоторые "физиологические". Мы ограничимся рассмотрением сетей прямого распространения сигнала. А именно, Строго говоря, условие строгой послойной градуировки нейронных сетей абсолютно не нужно ни для их работы, ни для обучения, ни даже при формулировании теорем. Оно лишь упрощает формулировки теорем и реализацию сетей. Вполне можно в любом ориентированном ациклическом графе истоки назвать входами, остальные вершины - нейронами, уровень нейрона определить как максимальное число ребер на ориентированном пути от какого-либо входа до него, и в качестве выходных брать любые нейроны, хоть все.
Вектор W, составленный из всех чисел we и wv, является параметром сети и подлежит обучению, чтобы выходной вектор Y, являющийся функцией F(W,X) от параметра и входного вектора X, был похож на то, чему сеть пытаются научить. Наоборот, функции he и gv остаются неизменны. Более того, как правило они зависят не от ребер и вершин, а только от номера слоя, или вообще универсальны. Наиболее типичными являются следующие пары:
Заметим, что для устойчивой работы нейронной сети вполне достаточно было бы непрерывности функций he и gv. Их гладкость нужна только для удобства обучения сети. В качестве функции ошибки обычно используется квадрат евклидова расстояния E(F(W,X),Y)=|F(W,X)-Y|2. Впрочем, при применении нейронных сетей для классификации, когда выход j-го выходного нейрона Fj(W,X) интерпретируется как оценка вероятности принадлежности входа X классу Cj, правильнее в качестве функции ошибки использовать кросс-энтропию
E(F(W,X),Y) = - q
е
j=1 
 yj lnFj(W,X)
(см. [1]).
Количество слоев L в практически применяемых нейронных сетях на удивление мало: чаще всего встречаются трехслойные сети, иногда даже двухслойные. И наоборот, в одном и том же распознавании иногда участвуют несколько различных сетей, как-то соединенных друг с другом, но обучаемых раздельно.
При применении нейронной сети для распознавания (классификации) X - это вектор признаков, а Y - вектор вычисленных вероятностей принадлежности классам, то есть число входов равно размерности пространства признаков, а число нейронов последнего слоя равно числу классов. Оба этих числа обычно невелики (порядка десятков). Наоборот, число нейронов промежуточных слоев (они называются скрытыми нейронами) бывает весьма велико (десятки тысяч).
В искусственных нейронных сетях, как и в мозгу, все вычисления происходят параллельно, и тем самым, очень быстро. В реальности нейронные сети моделируются на обычных последовательных компьютерах и работают довольно медленно, поэтому на количестве вершин и ребер сети приходится экономить. В 80-е годы на волне повышенного интереса к параллельным вычислениям были созданы и вполне действующие аппаратные реализации нейронных сетей, но вся волна ушла в песок. Похоже, что надвигается следующая волна.

1.2.1  Многослойный перцептрон (MLP, Multi-Layer Perceptron)

Слово перцептрон ("восприниматель") появилось в работах Розенблатта 50-х годов [3] и относилось к распознающей системе, обучающаяся часть которой состояла из одного нейрона с линейной функцией проводимости и ступенчатой функцией активации. Теперь перцептроном называют любую нейронную сеть с линейной функцией проводимости и общей для всех скрытых нейронов сглаженной ступенькой g (например, гиперболическим тангенсом tanh или функцией
s(t)=(tanh(t/2)+1)/2=1/(1+e-t),
(2)
которую как только ни называют, например, "сигмоидальной" или "logistic function") в качестве функции активации. Функцию активации выходных нейронов обычно делают тождественной: g(t)=t. То есть каждый нейрон v вычисляет функцию
f(v) = g ж
и 		ж
и
е
ребрам e, входящим в v 
 wef(e) ц
ш 		-wv ц
ш 		.
(3)
Параметры ребер we называют их весами, а параметры вершин wv - смещениями.
Для упрощения формализма часто добавляют к нейронной сети один дополнительный вход (смещение) и по одному нейрону в каждом слое, значения потенциала на которых всегда равны -1 и соединяют каждый нейрон v с входом- или нейроном-смещением предыдущего слоя ребром с приписанным весом wv. Тогда смещение -wv попадают в общую сумму, и вычисляемая скрытым нейроном функция равна просто
f(v) = g ж
и
е
ребрам e, входящим в v 
 wef(e) ц
ш 		.
Вычислительные возможности и теорема Колмогорова.  
Много ли функций может вычислить перцептрон? Следующие предложения, настоятельно рекомендуемые в качестве упражнений, показывают, что вполне достаточно.
Предложение 1 Характеристическую функцию любого полупространства в пространстве признаков (если не обращать внимания на значение функции на границе этого полупространства) можно вычислить однослойным перцептроном с разрывной ступенчатой функцией активации g(t)=q(t)=(sign(t)+1)/2 и одним нейроном.
Предложение 2 Характеристическую функцию любого полупространства в пространстве признаков можно приблизить в любом разумном слабом смысле (по мере, в L2loc и т.п.) однослойным перцептроном с непрерывной функцией активации g(t)=(tanh(t/2)+1)/2 и одним нейроном.
Те же оговорки в скобках подразумеваются и в последующих предложениях.
Предложение 3 Характеристическую функцию любого выпуклого многогранника в пространстве признаков можно вычислить двухслойным перцептроном с ступенчатой функцией активации. Для параллелепипеда достаточно 2d скрытых нейронов и одного выходного.
Предложение 4 Характеристическую функцию любого выпуклого многогранника в пространстве признаков можно приблизить двухслойным перцептроном с непрерывной функцией активации. Для параллелепипеда достаточно 2d скрытых нейронов и одного выходного.
Предложение 5 Любую конечную линейную комбинацию характеристических функций параллелепипедов в пространстве признаков можно вычислить трехслойным перцептроном с ступенчатой функцией активации.
Предложение 6 Любую непрерывную функцию на любом компакте в пространстве признаков можно равномерно приблизить трехслойным перцептроном с непрерывной функцией активации.
То есть трехслойных перцептронов достаточно для решения задач аппроксимации функций, и в частности, задач распознавания. Но чем точнее требуется аппроксимация, тем больше нейронов должно быть в сети.
Для сравнения напомним замечательную теорему, казалось бы не имеющую никакого отношения к нейронным сетям.
Теорема 1 (А.Н.Колмогоров, 1957 [4]). Любую непрерывную функцию на d-мерном кубе можно представить в виде суперпозиции функций двух переменных.
На самом деле в доказательстве этой теоремы используются только функции одной переменной и сложение. Более подробный анализ доказательства позволил переформулировать теорему в следующем виде.
Теорема 2 Для любой непрерывной функции на d-мерном кубе существует вычисляющая ее трехслойная нейронная сеть с (d+1)(2d+1) скрытыми нейронами. (Цитируется по книге [1]; там есть ссылки, но нет доказательств)
То есть и вычисляется любая функция не приближенно, а точно, и нейронов нужно совсем немного. Но обещанная нейронная сеть не является перцептроном: ее функции активации у разных нейронов разные, зависящие от вычисляемой функции и обязательно недифференцируемые.
Предложение 6 можно усилить:
Предложение 7 Любую непрерывную функцию на любом компакте в пространстве признаков можно равномерно приблизить двухслойным перцептроном с непрерывной функцией активации.
Доказательство этого предложения является более сложным упражнением, чем предыдущие. Подсказка: предложение можно разбить на два утверждения, общеизвестное и простое. Общеизвестное утверждение: любую непрерывную функцию на компакте в евклидовом пространстве можно приблизить тригонометрическим многочленом. Простое утверждение: любую функцию одного переменного, например, синус или косинус, на любом компакте можно приблизить линейной комбинацией (сглаженных) ступенек - функций активации.
Получается, что теоретически третий слой в предложении 6 - лишний и можно всегда обойтись двухслойным перцептроном. На практике же двух слоев не хватает.
Топология перцептронов.  
В практических реализациях перцептронов скрытых нейронов очень много. Чем больше скрытых нейронов, тем точнее перцептрон может приблизить любую непрерывную функцию, но тем медленнее он работает и обучается. Чтобы ребер сети не было (очень много)2 (здесь 2 - это не сноска, а возведение в квадрат), каждый нейрон соединен ребрами далеко не со всеми нейронами предыдущего слоя.
Типичный распознающий перцептрон - трехслойный (в соответствии с предложением 6). Нейроны первого скрытого слоя разбиты на несколько групп: внутри каждой группы нейроны одинаковы и соединены не со всеми входами сети, а только с каким-то их подмножеством, своим для каждой группы. Это разбиение на группы производится вручную исходя из специфики задачи. Нейроны второго скрытого слоя более-менее одинаковы, но каждый нейрон соединен со случайным не слишком большим подмножеством нейронов первого слоя. Каждый нейрон третьего слоя (выходного) соединен со всеми нейронами второго слоя.
Вообще говоря, топология перцептрона может меняться в процессе его обучения. Но ниже рассматривается только обучение перцептронов при фиксированной топологии.
Обучение с учителем: метод обратного распространения ошибки ( back propagation).  
Обучение перцептрона, то есть поиск вектора весов W, минимизирующего среднюю квадратичную ошибку, чаще всего производится стандартным методом градиентного спуска со всеми его недостатками (медленностью, застреванием в локальном минимуме или в овраге). Для его применимости функция активации должна быть дифференцируемой и ее производная должна легко вычисляться. Поскольку функция активации строго возрастает, она удовлетворяет некоторому дифференциальному уравнению первого порядка, и нужно только это уравнение знать. Например, для гиперболического тангенса выполняется тождество tanhў=1-tanh2.
Замечательно то, что производную ошибки по параметру для нейронной сети можно вычислять красиво и быстро - с помощью другой (двойственной) нейронной сети, получающейся из исходной обращением направлений ребер. На этом основании градиентный спуск для нейронных сетей обычно называется не просто градиентным спуском, а методом обратного распространения ошибки. Хотя строго говоря, метод обратного распространения - это всего лишь способ вычисления градиента ошибки, и даже не обязательно ошибки, а любой функции от выхода нейронной сети. Будет ли этот вычисленный градиент применяться для градиентного спуска или для другого метода обучения - вопрос отдельный.
Конфигурация двойственной сети однозначно определена конфигурацией исходной сети, а веса и функции активации зависят от весов ребер исходной сети и набора значений {f(v)} потенциалов нейронов. А именно,
В реально используемых функциях активации страшное выражение gўv(gv-1(f(v))) оказывается очень простым. Например, если gv - гиперболический тангенс, то gўv(gv-1(f(v)))=1-(f(v))2, а если gv тождественна, то gўv(gv-1(f(v)))=1.
На каждый вход v*L,j двойственной сети подают частную производную функции ошибки по соответствующему выходу исходной сети, умноженную на gўv(gv-1(f(v))). Например, для квадратичной ошибки E(F(W,X),Y)=|F(W,X)-Y|2 и тождественной функции активации выходных нейронов эта производная домножается на 1 и равна
f*(v*L,j) =  E(F(W,X),Y)
f(vL,j)
 = 2 ( f(vL,j) - yj )  ,
а для кросс-энтропийной ошибки
E(F(W,X),Y)=- y logF(W,X) -(1-y)log(1-F(W,X)) ,
применяющейся для сети с единственным выходом, оценивающем вероятность чего-либо, и логистической функции активации единственного выходного нейрона
gvL(t)=  1
1+e-t
производная [(1-y)/(1-F(W,X))]-[ y/F(W,X)] домножается на F(W,X)(1-F(W,X)) и получается
f*(v*L) = (1-y)F(W,X)-y(1-F(W,X)) = F(W,X)-y = f(vL)-y ,
т.е. почти то же самое. Упражнение: проверьте вычисления.
После чего сеть запускают на счет. Нетривиально, что для дальнейшего понадобятся посчитанные потенциалы не только выходных, а всех нейронов и входов обеих сетей - и исходной, и двойственной.
Следующие два упражнения по осмыслению и вычислению частных производных сложных функций многих переменных настоятельно рекомендуется проделать самостоятельно. А именно, нужно всего лишь многократно применить правило дифференцирования композиции функций к уравнению (3).
Предложение 8 Для любого нейрона v
-  E(F(W,X),Y)
wv
 =  E(F(W,X),Y)
s(v)
 = f*(v*),
где v* - нейрон, двойственный к v. Напоминаем, что s(v) - это активирующая сумма, в общем виде определенная в формуле (1).
Предложение 9 Напомним, что потенциал ребра - это по определению потенциал его начала. Для любого ребра e исходной сети
 E(F(W,X),Y)
we
 = f(e)f*(e*)
где e* - ребро, двойственное к e.
То есть, при работе двойственной сети для каждого ребра нужно дополнительно вычислить и запомнить произведение потенциалов (исходного и двойственного) в его концах, и производные ошибки по всем весам посчитаны (производные по wv - с обратным знаком). Остается усреднить производные по всему обучающему множеству {X1,...,XN} и для минимизации средней ошибки можно применять метод градиентного спуска. Если интересны дальнейшие подробности, см. литературу . Они есть в любой книге по нейронным сетям.
Метод обратного распространения ошибки легко и естественно обобщается и на сети с нелинейными функциями проводимости ребер he и функциями активации gv, зависящими от многих параметров.
Обучение нейронных сетей методом обратного распространения ошибки было придумано относительно поздно - в 70-е годы - и стало господствующим после публикации статьи [7]. До того применялись разные эвристические методы, имитирующие физиологическое обучение, т.е. поощряющие или наказывающие функции проводимости ребер за прохождение по ним сигнала, приводящего к правильному или, соответственно, неправильному ответу. Для однослойных перцептронов, точнее, для персепронов с только одним обучаемым слоем, они работали довольно успешно и подтолкнули развитие той части распознавательной науки, которая впоследствии превратилась в метод опорных векторов (см. раздел 1.4). Но для обучения всех слоев многослойных сетей они были непригодны.
Существуют и принципиально другие методы обучения нейронных сетей, тоже с красивыми названиями: термодинамический, генетический.... Но, как правило, они работают еще медленнее градиентного спуска и применяются только для выталкивания сети из локальных минимумов.
Специфические проблемы, возникающие при обучении перцептрона градиентным методом.  
У аргумента нелинейной функции активации типа сглаженной ступеньки (например, g(t)=tanh(t)) есть "хороший" диапазон изменения, в котором производная функции достаточно велика (например, отрезок [-1,1]), и два "плохих" диапазона, в которых производная функции очень мала (например, лучи (-Ґ,-10) и (10,Ґ)). Соответственно, у потенциала нейрона (значения функции активации) есть "хороший" диапазон, когда он по модулю заметно меньше 1, и "плохие", когда он по модулю очень близок к 1. Если для почти всех обучающих векторов потенциал нейрона попадает в "плохой" диапазон, то веса этого нейрона и его входных ребер будут обучаться крайне медленно (предложения 8 и 9). А если они попадают в один и тот же "плохой" диапазон, то этот нейрон не только плохо обучаем, но еще и бесполезен для классификации, поскольку его ответ (потенциал) почти не зависит от входных данных. Из этих соображений следуют следующие рекомендации по обучению нейронной сети.
Начальные значения параметров (весов входящих ребер и смещений) нейронов нужно брать такими, чтобы при любом возможном входном векторе потенциал любого нелинейного нейрона попал в "хороший" диапазон. Кроме того, чтобы топологически неразличимые нейроны одного слоя не дублировали друг друга, их начальные параметры должны отличаться. Например, в качестве начальных значений весов и смещений можно брать случайные величины, как-то распределенные на отрезке [-[ 1/(Ne(v)+1)],[ 1/(Ne(v)+1)]], где Ne(v) - число входных ребер нейрона v.
Если в процессе обучения какой-то нейрон v0 застрял в "плохом" диапазоне, т.е. при почти всех обучающих входных векторах выдает почти одинаковый потенциал, близкий к f0 (либо 1, либо -1), то этот нейрон нужно либо удалять. либо принудительно переучивать. Но делать это нужно так, чтобы минимально менять функцию, вычисляемую сетью, - ведь на ее обучение уже затрачены какие-то усилия. В обоих случаях нужно из смещения wv каждого нейрона v, в который из нейрона v0 идет ребро e, вычесть wef0. После этого нейрон v0 можно удалить (вместе со всеми входящими и выходящими ребрами), а можно просто приравнять нулю веса его входных ребер и смещение и дать ему возможность обучаться с нуля. Несколько эффективнее не совсем обнулять веса, а только поделить их на достаточно большое число и подобрать смещение так, чтобы при любых допустимых значениях потенциалов на входе ребер потенциал v0 попадал в достаточно малую окрестность нуля (и тем самым, в "хороший" диапазон).
Реализация перцептрона и градиентного обучения его: что почем.  
Нейронные сети очень хорошо реализовывать на специализированных параллельных компьютерах. Но за недоступностью таковых оценим требуемую память и время работы перцептрона при реализации на типичном однопроцессорном компьютере,
Требуемая память оценивается некоторой линейной комбинацией количеств ребер Ne и вершин Nv перцептрона и нужно только оценить ее коэффициенты. Сначала рассмотрим менее экономную по памяти но более удобную для экспериментов с топологией сети реализацию ребер и вершин (нейронов) в виде отдельных объектов.
Для каждого нейрона v нужно помнить список или массив входящих в него ребер (или указателей на них, или их индексов в массиве всех ребер), список или массив выходящих ребер, смещение wv, текущие значения потенциала f(v) и двойственного потенциала f*(v*). Кроме того при каждом ребре нужно иметь одну ячейку памяти для накапливания суммы частных производных ошибки по wv на разных обучающих векторах и последующего ее усреднения. Полезно также иметь пару ячеек для сбора статистики во время обучения, например, для обнаружения "залипания" нейрона. Кроме того, возможно, где-то хранится ссылка на этот нейрон. Итого два заголовка списков или массивов и 4-6 плавающих чисел и, может быть, один указатель - итого порядка 24-40 байт - плюс указатели на входящие и выходящие ребра, которые мы посчитаем при оценке размера ребра.
Для каждого ребра e нужно помнить его начало, конец, вес we и иметь одну ячейку памяти для накапливания суммы частных производных ошибки по we. А кроме того на каждое ребро где-то есть ссылка как на очередное входящее ребро какого-то нейрона и ссылка как на очередное выходящее ребро. Итого четыре указателя (или индекса в массивах всех вершин или ребер) и два плавающих числа - порядка 24 байт.
Поскольку ребер в многослойных перцептронах намного (по крайней мере на два порядка) больше, чем вершин, экономить память имеет смысл только на ребрах. Реализовав входящие ребра каждого нейрона в виде отдельного массива, можно сэкономить по две ссылки на ребро, т.е. в полтора раза. Еще чуть-чуть можно сэкономить на длине ссылок на вершины и точности хранения веса ребра, но это уже извращение. Остается 12-16 байт на ребро. Суммарный объем памяти, требующейся для перцептрона, имеет порядок 20Ne + 40Nv и более чем вдвое не уменьшается.
Количество операций при работе перцептрона также является линейной комбинацией количеств его ребер и вершин. А именно, по одному умножению и одному сложению на ребро (вычисление активирующих сумм) и одному вычислению функции активации на вершину (собственно вычисление ее потенциала). Поскольку функция активации одна и та же для всех нейронов и непрерывна, ее можно табулировать и интерполировать кусочно-линейной функцией: тогда ее вычисление - это порядка десяти команд. Значит поскольку ребер намного больше, чем вершин, основное время уходит на умножение и сложение. Итого, приняв за единицу времени команду умножения и предположив, что команда сложения не медленнее ее, а остальные команды - быстрее, получаем, что обсчет одного входного вектора перцептроном требует порядка 2Ne + 10Nv команд (умножения) и более чем вдвое не уменьшается.
Количественный пример: в 128Mb оперативной памяти 100Mflop-ного компьютера можно поместить перцептрон с  107 ребрами и 104 - 105 нейронами (в 108 раз меньше человеческого мозга) и работать он будет порядка 0.2 секунды (естественно, для каждого входного вектора). Но если вся сеть в оперативную память не поместится, работа замедлится катастрофически.
С временем обучения сети дела обстоят намного хуже. Вычисление градиента методом обратного распространения ошибки требует почти столько же операций, как и работа сети: по одному сложению и два умножения на ребро плюс по вычислению линейной функции активации на вершину. Но это нужно проделать для каждого из 104 - 105 обучающих входных векторов, после чего можно произвести один шаг градиентного спуска. А этих шагов понадобится хорошо, если сотня. То есть обучение перцептрона градиентным методом по крайней мере в миллион раз медленнее его работы. И действительно, реальные большие перцептроны обучают неделями. Впрочем, людей обучают годами...
Для сравнения оценим скорость работы гипотетических специализированных нейрокомпьютеров. Предположим, что на вычисление функции активации нейрона и ее производной обратной функции нужно K команд (умножения), K порядка 10. Схема первая: каждый нейрон - это отдельный процессор, а ребро - всего лишь объект в памяти. Тогда время одного вычисления не превосходит
L
е
l=1 
 ж
и 		3
max
k 
 Ne(vl,k) + K ц
ш 		Ј 2Nv +KL
команд (умножения), где L - число слоев, а Ne(vl,k) - количество ребер, входящих в k-й нейрон l-го слоя. То есть по сравнению с последовательной реализацией выигрыш по скорости по крайней мере в [(Ne)/(Nv)] раз.
Схема вторая: на каждое ребро нейронной сети также выделен отдельный процессор. Тогда при грамотной организации суммирования по входным ребрам каждого нейрона время работы сети не превосходит времени
L
е
l=1 
 ж
и 		log2(3
max
k 
 Ne(vl,k)) + K ц
ш 		< (log2Nv +K+2)L < 200
умножений при любом разумном количестве нейронов и слоев (обычно L=3). Разработчикам аппаратуры есть к чему стремиться...

1.2.2  Сети с радиальными базисными функциями (RBF, Radial Basis Function)

RBF-сети возникли не в нейрофизиологии, а в теории приближений. Простейшие RBF-сети - это формализация приближения экспериментальной функции, заданной таблицей замеренных значений, линейной комбинацией базисных функций (basis functions) заранее определенного класса, к тому же зависящих только от радиус-вектора (т.е. radial) от аргумента до "базовой точки" в пространстве-прообразе (т.е. на более современном языке, от их разности).
Простейшая RBF-сеть состоит из двух слоев, причем каждый нейрон соединен с каждым нейроном предыдущего слоя (или входом), а нейроны разных слоев устроены по-разному. Каждый нейрон v первого (скрытого) слоя вычисляет функцию
f(v) = g ж
и 		sv,
е
ребрам e, входящим в v 
 (f(e)-we)2 ц
ш 		,
где функция g равна g(s,t)=e-t/2s. Каждый нейрон v второго (выходного) слоя вычисляет функцию
f(v) = ж
и
е
ребрам e, входящим в v 
 wef(e) ц
ш 		- wv.
т.е. это обычный линейный нейрон с тождественной функцией активации.
Нейроны первого слоя и вычисляемые ими функции можно интерпретировать следующим образом. Входы каждого нейрона - это в точности входы x1 ,...,xd. всей сети, т.е. d-мерный вектор признаков X. Веса входных ребер каждого такого нейрона v также образуют d-мерный вектор Wv, называемый центром нейрона (в пространстве признаков), а нейрон вычисляет функцию
f(v)=e-[(|X-Wv|2)/(2sv)].
С точностью до коэффициента (2psv)-[ d/2] она равна значению в X плотности сферического гауссова распределения с центром Wv и дисперсией sv. А вся двухслойная RBF-сеть вычисляет набор линейных комбинаций гауссианов, причем это верно независимо от наличия коэффициента (2psv)-[ d/2].
Появление гауссианов там, где есть большое количество независимых одинаково распределенных случайных величин (а именно, векторов признаков из обучающего множества) вполне привычно. Несколько вариантов более-менее строгого обоснования, почему гауссиан, есть в книге [1]. А то, что все гауссианы - сферические, - это всего лишь модельный пример.
В практически применяемых сетях RBF каждый нейрон первого слоя v вычисляет свой гауссиан общего вида
f(v)=((2p)d|Av|)-[ 1/2]e-(Av-1(X-Wv),X-Wv),
(4)
где Av - приписанная нейрону симметрическая положительно определенная матрица (матрица ковариации), |Av| - ее определитель, а (Av-1·,·) - билинейная форма с обратной матрицей Av-1. То есть для каждого нейрона нужно хранить и настраивать не только d координат вектора Wv, но еще и [(d(d+1))/2] различных коэффициентов матрицы Av. Такая сеть не укладывается в общую схему раздела 1.2, поскольку в производимом нейроном вычислении нельзя выделить суммирование по входам (1). В частности, производные функционала ошибки по параметрам нейронов уже не вычисляются двойственной нейронной сетью. Формулы для их вычисления можно выписать явно, но они довольно неудобоваримые.
Замечание. Поскольку любая положительно определенная квадратичная форма аффинной заменой координат переводится в сумму квадратов, RBF-сеть с гауссианами вида (4) можно заменить на эквивалентную ей трехслойную сеть в смысле раздела 1.2, в которой первый слой состоит из линейных нейронов, вычисляющих эти аффинные преобразования, второй слой (бывший первый) состоит из необучающихся нейронов, вычисляющих один и тот же стандартный сферический гауссиан f(v)=e-|X|2, а третий слой (бывший второй) - опять линеен. Но такое представление неэффективно, поскольку теряется информация о симметричности матриц Av и, соответственно, почти удваивается число обучаемых параметров.
Далее мы рассматривает сети с нейронами, вычисляющими простейший сферический гауссиан, но все сказанное верно и для гауссианов общего вида.
Вычислительные возможности.  
В качестве упражнения рекомендуется доказать следующее предложение.
Предложение 10 Любую непрерывную функцию на любом компакте M в пространстве признаков можно равномерно приблизить функциями, вычисляемыми RBF-сетями.
То есть даже с помощью простейших RBF-сетей можно с любой точностью что угодно вычислить. Плохо только то, что при убывании погрешности приближения e дисперсия s убывает как e2, а количество скрытых нейронов растет как e-dim(M), в частности как e-d, если M - куб или шар. Причем оно экспоненциально растет даже если функция не зависит от почти всех признаков (крайний пример - зависящая только от одного признака функция
f(x1,...,xd)=e-[((x1-w1)2)/2s],
которая при одномерном пространстве признаков точно вычисляется одним нейроном). Напомним, что в задачах распознавания d бывает порядка десятков или сотен. Применение несферических и разных для разных нейронов гауссианов позволяет уменьшить требуемое число нейронов, но все равно их требуется очень много.
Обучение без учителя: метод максимизации ожидания ( expectation maximization).  
RBF-сеть можно обучать методом обратного распространения ошибки и градиентного спуска, как и перцептрон. Но их можно обучать и другим способом, причем очень быстро по сравнению с градиентным спуском. При этом слои сети обучаются раздельно: сначала первый, потом второй, и вообще говоря, на разных обучающих множествах. Поскольку второй слой линеен, то его обучение, т.е. минимизация средней квадратичной ошибки, сводится к однократному решению системы линейных уравнений (правда, весьма изрядного размера). Или ее можно минимизировать тем же методом градиентного спуска, который в случае квадратичного функционала всегда сходится к глобальному минимуму. А обучение первого слоя мы сейчас рассмотрим на простом примере, когда каждый нейрон первого слоя вычисляет сферический гауссиан со своей дисперсией. То есть обучение сводится к обучению центров Wv и дисперсий sv,
Будем считать обучающие вектора признаков значениями независимых одинаково распределенных случайных величин (векторных), плотность распределения которых является линейной комбинацией
K
е
j=1 
 Pjpj(X) = K
е
j=1 
 Pj  1
(2psj)[ d/2]
 e-[(|X-Wj|2)/(2sj)]
(5)
нескольких (K) гауссианов pj(X) с положительными коэффициентами Pj (естественно, еj=1K Pj=1). Целью обучения первого слоя будет найти распределение такого вида с максимальной вероятностью появления имеющегося обучающего входного набора X =X1,...,XN, точнее, с максимальной плотностью вероятности.
Такое обучение, хотя оно и не учит непосредственно распознаванию, удобно и полезно вот почему. Для обучающих векторов не нужно знать, какому классу они принадлежат (обучение без учителя), т.е. обучающие примеры можно накапливать автоматически, без участия человека. И такая вероятностная модель адекватна следующей, вполне реальной, ситуации. Каждый классифицируемый объект (например, буква) получается из некоторого эталонного способа написания, которому учат или не учат в школе, добавлением многих мелких независимых ошибок или, что то же самое, случайной нормально распределенной ошибки. Количество эталонов K намного превышает количество классов q (например, угловатую "рукопечатную" букву E, состоящую из четырех отрезков, можно писать 4!*24=384 топологически разными способами, хотя большинство из них крайне маловероятны). Обучение первого слоя сети - это поиск таких эталонов Wj и их вероятностей Pj. Поэтому в отличие от MLP-сети, в которой каждый нейрон учится неизвестно чему, за обучением RBF-сети вполне можно следить и понимать, какой нейрон чему учится.
Поиск параметров модели P =(P1,W1,s1,...,PK,WK,sK), обеспечивающих максимум правдоподобия
p(X,P)= N
Х
i=1 
 K
е
j=1 
 Pjpj(Xi)
обучающего набора X традиционно формулируют как поиск точки минимума "функции ошибки"
E(X,P) = -ln p(X,P) = - N
е
i=1 
 ln K
е
j=1 
 Pjpj(Xi)
поскольку сумму легче дифференцировать, чем произведение. Точек минимума, даже глобального, может быть много: в общем случае их не меньше числа перенумераций множества K нейронов, т.е. K!, н при этом заведомо будут и другие критические точки. Точки минимума можно искать и стандартным градиентным методом. На практике для RBF-сетей чаще применяется другой итеративный метод минимизации E(X,P), который, как и градиентный спуск, почти всегда сходится к точке локального минимума E и довольно быстро. На каждом шагу итерации функция ошибки мажорируется функцией более простого вида, минимум которой единственен и находится явно.
Удобно пользоваться вероятностными мотивировками и обозначениями: P{j}=P j - вероятность выбора j-го эталона, p(X|j)=pj(X) - условная плотность вероятности, тогда p(X)=еj=1K P{j}p(X|j) - полная плотность вероятности, и по формуле Байеса условная вероятность выбора j-го эталона при наблюдении вектора X
P{j|X} =  p({j}& X)
p(X)
 =

P{j}p(X|j)
K
е
j=1 
 P{j}p(X|j)
 =

Pjpj(X)
K
е
j=1 
 Pjpj(X)
 .
Впрочем, можно просто считать P{j|X} удобным обозначением и не забывать, что P{j|X} неотрицательна и еj=1K P{j|X}=1. Более того, в рассматриваемой нами модели плотность вероятности pj(X) всюду положительна, вероятность Pj можно считать положительной (иначе j-й эталон можно выбросить), а значит и условная вероятность P{j|X} положительна.
Зафиксируем любое допустимое (т.е. Pj > 0, еj=1K Pj=1, sj > 0) значение набора параметров (P0) и соответствующие ему вероятности и плотности вероятностей будем также обозначать с верхним индексом 0. Тогда
E(X,P)-E(X,P0)
=
- N
е
i=1 
 ln  p(Xi)
p0(Xi)
=
- N
е
i=1 
 ln ж
и 		K
е
j=1 
  Pjpj(Xi)
p0(Xi)
 ц
ш
=
- N
е
i=1 
 ln ж
и 		K
е
j=1 
 P0{j|Xi}  Pjpj(Xi)
P0jp0j(Xi)
 ц
ш
Ј
- N
е
i=1 
 K
е
j=1 
 ж
и 		P0{j|Xi} ln  Pjpj(Xi)
P0jp0j(Xi)
 ц
ш
=
- N
е
i=1 
 K
е
j=1 
 P0{j|Xi} ln( Pjpj(Xi) ) + N
е
i=1 
 K
е
j=1 
 P0{j|Xi} ln( P0jp0j(Xi) ).
Неравенство в этой цепочке преобразований следует из выпуклости функции -ln(·):
- ln ж
и 		K
е
j=1 
 cjxj ц
ш 		Ј - K
е
j=1 
 cj ln(xj),
если все cj неотрицательны и еj=1K cj=1.
Обозначим
Q(X,P0,P) = - N
е
i=1 
 K
е
j=1 
 P0{j|Xi} ln(Pjpj(Xi)) .
Тогда полученное неравенство означает, что
E(X,P) Ј Q(X,P0,P) - Q(X,P0,P0) + E(X,P0),
т.е. правая часть мажорирует E(X,P) и совпадает с ней в точке P0. Значит если удастся найти точку P глобального минимума правой части или, что то же самое, точку глобального минимума Q(X,P0,·) по всей области определения, то E(X,P) Ј E(X,P0). Прямые вычисления производных Q(X,P0,P) по параметрам P (дифференцировать сумму логарифмов намного приятнее, чем логарифм суммы), показывают, что критическая точка Q(X,P0,P) единственна, и является точкой минимума.
А именно, пишем лагранжиан
L(P,l) = - N
е
i=1 
 K
е
j=1 
 P0{j|Xi} ln(Pjpj(Xi))+l ж
и 		K
е
j=1 
 Pj-1 ц
ш 		,
систему уравнений
0
=
 L
l
 = K
е
j=1 
 Pj-1
0
=
 L
Pj
 =l-  1
Pj
 N
е
i=1 
 P0{j|Xi}
0
=
 L
Wj
 = N
е
i=1 
 P0{j|Xi}  Wj-Xi
sj
0
=
 L
sj
 = N
е
i=1 
 P0{j|Xi} ж
и 		 d
2sj
 -  |Xi-Wj|2
2sj2
 ц
ш
и решаем ее. Из первых двух строк, т.е. K+1 уравнений, совершенно независимо от конкретного вида плотностей вероятности pj(·) получается, что
l = K
е
j=1 
 Pjl = K
е
j=1 
 N
е
i=1 
 P0{j|Xi} = N
е
i=1 
 K
е
j=1 
 P0{j|Xi}= N
е
i=1 
 1=N
Дальнейшее решение системы совсем элементарно. Получается
Pj
=
 1
N
 N
е
i=1 
 P0{j|Xi}
(6)
Wj
=
N
е
i=1 
 P0{j|Xi} Xi
N
е
i=1 
 P0{j|Xi}
 =
N
е
i=1 
 P0{j|Xi} Xi
N Pj
(7)
sj
=
 1
d
N
е
i=1 
 P0{j|Xi} |Xi-Wj|2
N
е
i=1 
 P0{j|Xi}
 =
N
е
i=1 
 P0{j|Xi} |Xi-Wj|2
d N Pj
 ,
(8)
где Wj в третью строку нужно подставить из второй.
Упражнение. Проверьте, что найденное решение попадает в область определения функции Q(X,P0,·) и является точкой ее минимума (из единственности решения следует, что глобального).
Шаг обучения первого слоя RBF-сети завершен. Для почти всех обучающих наборов X и допустимых начальных значений параметров модели ее обучение быстро сходится к локальному минимуму "функции ошибки" E, который, в отличие от минимума функции Q, совершенно не обязан быть глобальным. Начальные значения P можно брать случайными. При недостаточном количестве различных входных векторов дисперсии sj могут стремиться к нулю.
Напоминаем, что в рассматриваемом модельном примере все распределения pj - сферические гауссовы. Для остальных параметров гауссианов общего вида (а именно, для коэффициентов матриц ковариации Aj) ответ тоже единственен, элементарно вычислим и даже легко угадывается.
Упражнение. Обобщите обучение вышеописанным методом максимизации ожидания на случай гауссианов общего вида
pj(X)=((2p)d|Aj|)-[ 1/2]e-(Aj-1(X-Wj),X-Wj).
(9)
Ведь на практике только они и применяются.
Ответ. Формулы (6) и (7) остаются без изменений, а вместо каждой формулы (8) получается [(d(d+1))/2] формул
Ajlm =
N
е
i=1 
 P0{j|Xi} (Xil-Wjl)(Xim-Wjm)
N
е
i=1 
 P0{j|Xi}
 ,     1 Ј l Ј m Ј d,
где отличные от 0 верхние индексы относятся к координатам в пространстве признаков.
И под занавес кусочек практики. Количество нейронов первого слоя в процессе обучения обычно меняется. Кроме того после вышеописанного раздельного "экспресс-обучения" слоев сети ее обычно еще доучивают как целое каким-либо методом обучения с учителем.

1.3  Обучающееся векторное квантование (LVQ, Learning Vector Quantization)

Метод обучающегося векторного квантования (и более общая теория самоорганизующихся отображений, SOM) появился в бесчисленных работах Т.Коонена [9] 80-х годов. Он состоит в приближении экспериментально заданных функций ступенчатыми и в своем простейшем варианте напоминает предельный случай обучающейся нейронной RBF-сети со сферически симметричными быстро убывающими базисными функциями. В отличие от нейронных сетей, распараллеливание вычислений при векторном квантовании не предусмотрено, зато суммарный объем вычислений заметно меньше. Векторное квантование гораздо чаще применяют для сжатия данных, чем для распознавания.
Идея векторного квантования состоит в том, чтобы разбить все пространство признаков на такие непересекающиеся области (кластеры) S1,...,SK, что все точки кластера можно было считать неразличимыми для решаемой задачи (например, необратимого сжатия данных или, что нам интереснее, классификации). В отличие от осужденной выше попытки сразу разбить пространство признаков на классы , кластеров может быть гораздо больше, чем классов (классов - десятки, а кластеров - тысячи). После того, как кластера построены, каждой паре (Si,Cj) вида (кластер,класс) приписывается вероятность Pij того, что вектор из этого кластера принадлежит этому классу, равная доле объектов обучающего множества, принадлежащих Si и Cj одновременно среди объектов, принадлежащих Si (т.е. оценка условной вероятности P{Cj|Si} или, что то же самое, точка минимума среднеквадратичной ошибки классифицирующей функции на этом кластере). А вот кластеризация пространства признаков требует длительного обучения. Обычно это обучение происходит без учителя, т.е. без знания о том, каким классам принадлежат обучающие объекты.
В простейшем случае, когда пространство признаков - евклидово, а количество кластеров K фиксировано, существует элементарный алгоритм кластеризации, называемый k-means (k средних). В этом названии "k" обозначает количество кластеров K, а "mean" - среднее арифметическое обучающих точек, попавших в кластер.
Обучение без учителя: алгоритм k-means.  
Рассмотрим конечное множество точек W ={W1,...,WK} в метрическом пространстве. Клеткой Вороного Vj называется множество точек пространства, расстояние от которых до Wj не превосходит расстояния до любой другой точки Wk. Точка Wj называется центром клетки Vj. Если пространство - евклидово, то при любом наборе центров клетки Вороного являются многогранниками (возможно, неограниченными) и действительно образуют клеточное разбиение пространства в топологическом смысле.
Для фиксированного набора пронумерованных центров W и любой точки X обозначим через r(X,W) расстояние от X до W, т.е. до ближайшего к X центра Wj, а через j(X) - наименьший (если таковых несколько) индекс ближайшего к X центра. Теоретико-множественной клеткой Вороного Zj назовем множество {X:j(X)=j}, т.е. настоящую клетку Вороного, возможно без части ее границы. Такие клетки уже не пересекаются. Именно они и будут искомыми кластерами.
Обучение состоит в итеративном пересчете набора центров W. Для обучения используется обучающее множество {X1,...,XN}, где N і K (желательно N >> K). На первом шаге в качестве центров берутся любые K различных точек пространства, например, случайные или первые K точек обучающего множества. На каждом последующем шаге для каждой клетки Zj вычисляется центр тяжести (среднее арифметическое) Wўj точек обучающего множества, попавших в клетку Zj. После чего набор из K вычисленных центров тяжести берется в качестве новых центров. Проблема, чему равен центр тяжести пустого множества, решается произвольным образом.
Предложение 11 Алгоритм k-means сходится за конечное число шагов.
Действительно, если на каком-то шагу центры сдвигаются, то значение функции
E(W)= N
е
i=1 
 (r(Xi,W))2 і 0
(10)
уменьшается. А если не сдвигаются, то разбиение на клетки уже никогда не изменится. Разбиений обучающего множества - конечное число.
К сожалению это число разбиений очень велико, больше [(NK)/K!], так что на практике при N >> K >> 1 сколько-нибудь разумная скорость сходимости алгоритма k-means из доказательства не следует. И действительно, k-means иногда сходится неприемлемо медленно.
Никакой гарантии того, что кластеризация получится хорошей, нету. Например, если пространство признаков - двумерная плоскость, кластеризуемые точки лежат в двух маленьких кругах, находящихся далеко друг от друга, K=2 (т.е. клетки Вороного - это полуплоскости), N=4, причем две обучающие точки лежат в одном круге, две - в другом, и при этом они почти являются вершинами прямоугольника, то алгоритм k-means может научиться "правильной" кластеризации, а может и "неправильной", в зависимости от того, какие точки взяты за исходные центры. Однако на практике таких проблем не возникает. Практическая проблема состоит в определении подходящего числа кластеров K и во времени обучения.
После того, как центры обучены и распределение вероятностей посчитано, работа распознающей системы состоит в том, чтобы по входной точке найти ближайший к ней центр и выдать приписанный этому центру ответ (альтернативный вариант - найти несколько ближайших, например, 5, и устроить голосование). Но количество центров K весьма велико и находятся они в многомерном пространстве. На прямой, ближайшая из K заранее известных точек легко находится за O(ln(K)) операций. Известно много разных эвристических алгоритмов быстрого (быстрее O(K)) поиска ближайшего соседа в многомерном пространстве, но хотя они успешно применяются на практике, их скорость не гарантирована.
Иерархическое векторное квантование.  
Существуют многочисленные алгоритмы векторного квантования, похожие на алгоритм k-means, а обучающиеся быстрее за счет того, что не все центры обучаются одновременно. Сначала обучается небольшая часть центров, потом они фиксируются и обучается еще сколько-то центров и т.д. При этом общее количество центров даже не обязательно фиксировать заранее. В отличие от алгоритма k-means, который медленно, но верно обучается минимизировать известно какую функцию ошибки при известно каких условиях, эти методы обучаются неизвестно чему, зато быстро. Кроме того при распознавании вместо честного, но медленного поиска ближайшего центра можно искать нечестно, зато быстро. Вот модельный пример таких методов обучения и поиска.
Сначала общая схема. Фиксируем обучающее множество векторов {X1,...,XN}. На первом шаге берем очень небольшое число k центров, обучаем их с помощью алгоритма k-means и получаем разбиение пространства входных векторов на клетки Вороного V1,...,Vk, а обученные центры W1,...,Wk фиксируем. Эти клетки и центры назовем клетками (кластерами) и центрами первого уровня. Далее по индукции: если n-1 уровней клеток и центров построены, то на n-ом шаге мы в каждой клетке Vj1,...,jn-1 n-1-го уровня берем несколько (kj1,...,jn-1) новых центров и обучаем их с помощью алгоритма k-means на обучающих векторах, попавших в Vj1,...,jn-1. Причем если в Vj1,...,jn-1 попадает достаточно мало обучающих векторов (и/или количество клеток уже достаточно велико и/или на обучение потрачено уже слишком много времени), то берем kj1,...,jn-1=1, т.е. ничего не делаем. Получаем разбиение клеток уровня n-1 на клетки уровня n и их центры. Процесс обучения останавливается, когда в каждой клетке очередного уровня обучающих точек становится мало или еще раньше. Заметьте, что клетки (правильнее, кластеры) уровня более 1 не являются настоящими клетками Вороного, построенными по своим центрам.
После того, как обучение закончилось на каком-то уровне n можно взять центры уровня n, забыть все остальное, и использовать их для стандартного векторного квантования (можно даже доучить их по алгоритму k-means). А можно наоборот, помнить все "генеалогическое дерево" центров и для каждого входного вектора искать не ближайший центр уровня n, а содержащую его клетку уровня n. Этот поиск намного быстрее любого честного поиска ближайшего соседа.
Теперь подробности пары возможных реализаций. k=1, т.е. V1 - это все пространство входных векторов, а W1 - центр тяжести всего обучающего множества. Далее на каждом шаге каждая клетка либо не делится вообще, либо делится ровно на две, Решение о том, делить или не делить, а также куда поместить два новых центра, можно принимать учитывая или не учитывая знание о том, каким классам принадлежат обучающие вектора. В первом случае (обучение с учителем) клетку нужно делить, если она недостаточно хороша для распознавания, т.е. в нее попадает много векторов по крайней мере двух классов, а за первые приближения для новых центров можно брать центры тяжести векторов двух самых частых классов. Во втором случае (обучение без учителя) клетку нужно делить, если она слишком велика, т.е. в нее попадает очень много векторов, а первые приближения для новых центров получаются расщеплением центра клетки в направлении наибольшего собственного вектора матрицы ковариации попавших в клетку обучающих векторов (или просто в случайном направлении).
Квантование в неевклидовых пространствах.  
Выбор евклидовой метрики в пространстве признаков как правило является вопиющим произволом, ничем кроме стремления к простоте не обусловленным. Но эта теоретическая простота не гарантирует быстрого и качественного распознавания. Например, можно в том же пространстве признаков ввести l1-метрику r(x,y)=еj=1d|xj-yj| и модифицировать алгоритм k-means, чтобы вместо функции (10) он минимизировал функцию
E(W)= N
е
i=1 
 r(Xi,W).
Упражнение. Что нужно делать на каждом шагу модифицированного таким образом алгоритма k-means?
Как влияет такое изменение метрики на качество распознавания - проблема экспериментальная, а вот скорость распознавания сразу возрастает в константу раз. Ведь при каждом вычислении квадрата расстояния раньше требовалось 2d-1 сложений/вычитаний и d умножений, а теперь - только 2d-1 сложений/вычитаний и d убиваний знака. В зависимости от архитектуры компьютера эта константа может оказаться довольно существенной.
Векторное квантование чувствительно к размерности d пространства признаков. Погружение пространства признаков в большее пространство, т.е. добавление зависимых признаков, работу векторного квантования не ухудшает, а вот при добавлении независимых признаков требуемое количество центров K растет с размерностью, вообще говоря, экспоненциально. Поэтому если удается избавиться от признака, статистически независимого от остальных, но мало влияющего на классификацию, векторное квантование начинает распознавать быстрее и лучше (в отличие от естественных систем распознавания и перцептронов, которые сами легко обучаются игнорировать избыточные признаки). Например, распознавание букв не должно зависеть от наклона почерка.
Ради избавления от лишних признаков идут и на то, чтобы пространство признаков не было евклидовым. Например, вычисляют расстояние не между точками, а между их орбитами относительно преобразований, заведомо не влияющих на классификацию. В случае распознавания букв это не только сдвиги и растяжения плоскости "бумаги", по которым легко просто профакторизовать, но и все гладкие (или хотя бы только линейные) преобразования, близкие к тождественным.
Пространство орбит обычно не является векторным (и даже аффинным), так что понятие центра тяжести, использующееся при обучении по алгоритму k-means и его модификациям, в нем отсутствует. В самых простых случаях оно является компактным многообразием, а значит его можно вложить в евклидово пространство, приблизить полиэдром и внутри каждой грани квантовать отдельно. Или просто покрыть конечным числом карт и квантовать отдельно в каждой карте. В общем случае пространство орбит устроено совершенно непонятно как. Практические реализации не используют высокой науки, даже слова "многообразие", но содержат любопытные алгоритмы, например [12].
Обучающееся векторное квантование.  
Еще одно важное направление развития теории векторного квантования - это доучивание системы в процессе работы. Алгоритм k-means требует, чтобы ему задали число кластеров K (заранее никому не известное, но, как показывает практика, десятки тысяч) и предоставили N >> K обучающих точек, которые он будет многократно пережевывать. Другие вышеописанные алгоритмы не требуют задания числа кластеров, но тоже многократно пережевывают большое обучающее множество. Предпочтительнее был бы алгоритм, обучающий центры и их количество по мере поступления новых, неповторяющихся обучающих данных. Такие алгоритмы есть, и много. В отличие от k-means, они обычно работают с учителем.
Сначала опишем то, что делается просто и однозначно, а именно, доучивание распределения вероятностей Pij=P{Cj|Si}. Достаточно про каждый кластер Si (при обучении алгоритмом k-means это клетка Вороного, но в общем случае, не обязательно) помнить не только вероятности Pij, но и число Ni обучающих векторов, попавших в этот кластер. Тогда если очередной входной вектор X попадает в кластер Si и про него известно, что он принадлежит классу Cl, то распределения вероятностей и количества векторов для остальных кластеров сохраняются, а для i-го пересчитываются по естественным формулам
Pil
:=
 NiPil+1
Ni+1
Pij
:=
 NiPij
Ni+1
     при j № l
Ni
:=
Ni+1 .
Аналогично можно доучивать и центры кластеров:
Wi:=  NiWi+X
Ni+1
 = Wi+  X-Wi
Ni+1
 ,
что в случае, когда кластера являются клетками Вороного, является пересчетом центра тяжести обучающих векторов из i-й клетки. В более общем случае i-й центр доучивается по формуле
Wi:=Wi+a(i,X)(X-Wi),
где коэффициент a(i,X) зависит не только от стадии обучения, но и от вероятности Pil (напоминаем, что вектор X принадлежит классу Cl). Причем a(i,X) может быть как положительна, так и отрицательна. Например, при
a(i,X) =  2Pil-1
Ni+1
центр Wi притягивается к новому обучающему вектору X, если большинство попадавших в i-й кластер обучающих векторов принадлежали тому же l-му классу, что и X, и отталкивается, если таких векторов - меньшинство. В еще более общем случае на каждом очередном обучающем векторе доучиваются центры не только одного, а нескольких ближайших кластеров. Рецептов обучения в LVQ много, про них доказываются теоремы о статистической сходимости, но не о качестве получающегося распознавателя.
Литература по LVQ и SOM весьма обильна [11], а что порекомендовать - непонятно. Ну разве что талмуд основоположника [10].

1.4  Метод опорных векторов (SVM, Support Vector Machine)

SVM - это оформившийся к 90-м годам результат работ В.Вапника & Co ([14] для линейно разделимого случая и [15] для общего), начатых в 70-е годы. В исходном виде SVM представляет собой алгоритм, обучающийся ровно одной задаче: различению объектов двух классов. И этому SVM обучается очень быстро по сравнению, например, с нейронными сетями, поскольку вместо сложной нелинейной минимизации SVM решает задачу минимизации всего лишь квадратичного функционала, правда при огромном количестве линейных ограничений. И классифицирует обученная SVM быстро. Но при попытке применить SVM к многоклассовой задаче качество и скорость работы падают.
Основная идея SVM такова. SVM учится только с учителем. Возьмем обучающее множество X =X1,...,XN векторов признаков в евклидовом пространстве Rd, разбитое на два класса, скажем, крестики и нолики. Попробуем разделить все пространство гиперплоскостью так, чтобы крестики попали в одно открытое полупространство, а нолики - в другое. Предположим, что такая гиперплоскость существует. Тогда она не единственна, так как множество разделяющих гиперплоскостей открыто. Попробуем найти в каком-то смысле самую лучшую гиперплоскость. И если мы ее нашли, то постановим все вектора признаков (уже не только из обучающего множества), попадающие в полупространство с крестиками, считать крестиками, а остальные - ноликами. А вероятность неправильной классификации оценивается как некоторая непрерывная убывающая функция от расстояния до разделяющей плоскости, равная 1/2 в нуле и стремящаяся к 0 на бесконечности.
А что делать, если такой разделяющей плоскости нет? Ответ: вложить пространство признаков Rd в пространство большей размерности, причем достаточно кривым образом (т.е. нелинейно), и пытаться разделить гиперплоскостью в большом пространстве. Например, можно вкладывать полиномиально. Тогда разделение гиперплоскостью в большом пространстве - это разделение полиномиальной поверхностью в исходном Rd. Конечно же, любые два конечных непересекающихся множества полиномиально разделимы.
В качестве упражнения докажите следующие утверждения.
Предложение 12 Существует полиномиальное вложение d-мерного евклидова пространства в (dd+N)-мерное, при котором образы любых N точек линейно разделяются на любые два класса.
Предложение 13 Для почти любого вложения d-мерного евклидова пространства в (N-1)-мерное образы почти любых N точек линейно разделяются на любые два класса.
Размерности пространств вложения оказываются удручающе большими. Реально в SVM применяются вложения аж в бесконечномерное гильбертовы пространства, но такие, что все нужные вычисления легко производятся в терминах d-мерных прообразов.
Теперь более конкретно.

1.4.1  Линейно разделимый случай: опорные вектора (support vectors)

Для каждого обучающего d-мерного вектора признаков Xi определим число yi, равное 1, если Xi принадлежит одному классу ("положительному" или крестиков), и -1, если другому ("отрицательному" или ноликов). Разделить крестики и нолики гиперплоскостью равносильно тому, чтобы найти линейную функцию f на Rd, положительную на каждом крестике и отрицательную на каждом нолике, т.е. такую, что yif(Xi) > 0 для любого i. Тогда и впоследствии для классификации любого вектора признаков X достаточно будет вычислить знак f(X).
Упражнение по линейной алгебре:
Предложение 14 (Обучающие вектора не разделимы никакой гиперплоскостью) Ы
(выпуклые оболочки крестиков и ноликов пересекаются) Ы
(выпуклая оболочка векторов yiXi содержит начало координат) Ю
(обучающие вектора линейно зависимы).
Умножив функцию f на положительную константу мы можем добиться того, что yif(Xi) і 1 для любого i. Поскольку пространство евклидово, линейная функция f представима в виде суммы
f(·)=(w,·)+b
(11)
скалярного произведения с некоторым вектором W и константы b, и условие разделения классов переписывается в виде
yi((W,Xi)+b) і 1,    i=1,...,N ,
а уравнение разделяющей плоскости -
(W,X)+b = 0 .
Заметим, что любая плоскость вида (W,X)+bў = 0 при b-1 < bў < b+1 также разделяет крестики и нолики. Толщина заметаемой этими плоскостями полосы равна [ 2/(|W|)]. Граница разделяющей полосы состоит из плоскостей (W,X)+b-1=0 и (W,X)+b+1=0, которые могут содержать обучающие вектора-крестики и -нолики, соответственно. Эти вектора называются опорными.
Для надежного разделения классов хочется, чтобы разделяющая полоса была как можно толще, т.е. вектор W как можно короче3. То есть нужно минимизировать квадратичную функцию [ 1/2](W,W) в выпуклом многограннике в пространстве пар (W,b), заданном линейными неравенствами. Заметим, что прямая W=0 с этим многогранником не пересекается, так что минимум будет строго положителен. Минимизация половины квадрата длины вместо самой длины - это обычная техническая уловка для удобства дифференцирования. Такая задача стандартным образом сводится к решению систем линейных уравнений и, так как минимизируемая функция строго выпукла, имеет единственное решение, если система неравенств совместна, и ни одного, если она несовместна. Но количество этих систем уравнений равно 2N, что неприемлемо много, поэтому эту задачу решают по-другому. Поскольку нам небезразличен вид решения, приступаем к счету.
Задача минимизации функции с ограничениями-неравенствами
 1
2
 (W,W) ®
min
W,b 
(12)
yi((W,Xi)+b) і 1,    i=1,...,N 
равносильна поиску критических точек (уже не точек минимума, а седловых точек) его лагранжиана
L(W,b,L) =  1
2
 (W,W) - N
е
i=1 
 li(yi((W,Xi)+b)-1)
в ортанте по множителям Лагранжа:
li і 0,    i=1,...,N 
причем для решения выполнены соотношения Куна-Такера
li(yi((W,Xi)+b)-1)=0,    i=1,...,N 
Из необходимых условий критичности точки
0=  L(W,b,L)
W
=
W - N
е
i=1 
 liyiXi
0=  L(W,b,L)
b
=
N
е
i=1 
 liyi
(первое уравнение - N-мерное векторное) сразу получается, что
W = N
е
i=1 
 liyiXi
Значит W является линейной комбинацией обучающих векторов, причем в эту сумму с ненулевыми коэффициентами li входят только те вектора, для которых (yi((W,Xi)+b)-1)=0, т.е. опорные. А b=yr-1-(W,Xr) для любого опорного вектора Xr.
Упражнение. Докажите, что опорные вектора существуют. По крайней мере два.
Таким образом параметры W и b разделяющей плоскости выражены через обучающие вектора и множители Лагранжа li. Теперь перейдем к вычислению множителей Лагранжа. Подставляя значение W и равенство еi=1N liyi=0 в лагранжиан L(W,b,L), сводим задачу к поиску критических точек функции
L(W,b,L)
=
 1
2
 (W,W) - N
е
i=1 
 li(yi((W,Xi)+b)-1)
=
 1
2
 (W,W) - ((W,W) - N
е
i=1 
 li) = N
е
i=1 
 li -  1
2
 (W,W)
=
N
е
i=1 
 li -  1
2
 N
е
i,j=1 
 liljyiyj(Xi,Xj),
не зависящей от W и b, при ограничениях
0
Ј
(yj(( N
е
i=1 
 liyiXi,Xj)+b)-1) = yj((W,Xj)+b)-1
=
 L(W,b,L)
lj
     i=1,...,N
0
=
lj(yj(( N
е
i=1 
 liyiXi,Xj)+b)-1) = lj(yj((W,Xj)+b)-1)
=
lj  L(W,b,L)
lj
     i=1,...,N
0
=
N
е
i=1 
 liyi
0
Ј
li    i=1,...,N .
Легко проверить, что это равносильно максимизации
N
е
i=1 
 li -  1
2
 N
е
i,j=1 
 liljyiyj(Xi,Xj)®
max
L 
(13)
N
е
i=1 
 liyi = 0
li і 0,    i=1,...,N
отрицательно определенной квадратичной функции от L в пересечении положительного ортанта с гиперплоскостью. Достаточно догадаться обозначить через b множитель Лагранжа в ее лагранжиане
L*(L) = N
е
i=1 
 li -  1
2
 N
е
i,j=1 
 liljyiyj(Xi,Xj)+ b N
е
i=1 
 liyi .
Параметрами задачи являются коэффициенты классовой принадлежности yi и попарные скалярные произведения (Xi,Xj) обучающих векторов. Известен хороший алгоритм решения этой квадратичной экстремальной задачи, см. [16] и, например, [17].
Заметим, что для классификации любого вектора признаков X, нужно вычислить
f(X) = (W,X)+b = N
е
i=1 
 liyi(Xi,X)+ yr-1 - N
е
i=1 
 liyi(Xi,Xr),
(14)
где числа li зависят только от коэффициентов yj и попарных скалярных произведений (Xi,Xj) обучающих векторов. То есть для обучения и работы SVM ничего, кроме классовой принадлежности и попарных скалярных произведений векторов признаков, знать не нужно. Кроме того при классификации суммирование можно производить не по всем обучающим векторам, а только по опорным, которых может оказаться, существенно меньше, чем N.
Историко-научное отступление.  
В таком виде задача построения оптимальной разделяющей плоскости была решена уже в начале 70-х годов (например, с точностью до некоторого линейно-алгебраического косноязычия, в книге [13]). Причем идеи, что чем толще разделяющая полоса, тем лучше, и чем меньше опорных векторов, тем лучше, вытекали из общей теории статистического обучения. А именно, через отношение толщины разделяющей полосы к диаметру множества допустимых векторов признаков, количествo опорных векторов и количество всех обучающих векторов можно оценить сверху вероятность ошибки полученного классификатора на любом тестовом наборе векторов. Однако практическая применимость такого метода обучения распознавателей была весьма ограничена. Последующие 20 лет ушли не столько на ускорение алгоритмов решения квадратичных экстремальных задач, известных с времен Гаусса, сколько на понимание того, как разделить широкой полосой с малым количеством опорных векторов два множества, которые и плоскостью-то разделить нельзя.

1.4.2  Линейно неразделимый случай: ядра (kernel functions)

Пусть f - произвольное, не обязательно линейное, не обязательно даже непрерывное отображение (не обязательно вложение) пространства признаков F (не обязательно даже евклидова пространства Rd) в евклидово или гильбертово пространство H. Единственное условие на f состоит в том, что образы обучающих векторов f(Xi) в пространстве H линейно разделимы. Тогда, повторив все рассуждения раздела 1.4.1 с подстановкой f(Xi) вместо Xi, мы получим классифицирующий алгоритм SVM. Причем для его настройки и применения нужно знать даже не само отображение f, а только функцию K:F×F®R, вычисляющую скалярное произведение в H образов пары векторов признаков:
K(X1,X2)=(f(X1),f(X2)).
(15)
Такая функция K называется ядром, поскольку при наличии на пространстве признаков F меры, в частности при F =Rd, она является ядром интегрального оператора
f ®
^
K
 
 (f)=
у
х
F 
 K(·,Y)f(Y)dY ,
(16)
имеющего-таки отношение к делу. И вместо поиска отображений f, обеспечивающих линейную разделимость, достаточно изучать ядра.
Ядром может быть не любая функция двух (векторных) переменных. Простое упражнение:
Предложение 15
Любое ядро K симметрично (K(X1,X2)=K(X2,X1) для любых X1 и X2) и неотрицательно определено (матрица Kij=K(Xi,Xj) неотрицательно определена для любого конечного набора векторов X1,...,XN).
Оказывается, ничего больше от ядра не требуется. Но прежде, чем доказывать это в общем виде и довольно неконструктивно, в качестве упражнений рассмотрим полезные частные случаи.
Предложение 16 Для конечного пространства признаков F любая симметричная и неотрицательно определенная функция K:F×F® R является ядром.
Предложение 17 Любая непрерывная, симметричная и неотрицательно определенная функция K:Id×Id ® R на квадрате d-мерного куба Id является ядром.
Доказать последнее предложение в лоб довольно трудно, но его легко свести к следующей теореме из теории интегральных операторов:
Теорема 3 (Mercer, 1909 [18]). Если функция K О L2(Rn×Rn) симметрична и неотрицательно определена, т.е. для любой функции f О L2(Rn)
у
х

X,Y О Rn 
 K(X,Y)f(X)f(Y)dXdY і 0  ,
то функция K представима в виде суммы сходящегося в L2 ряда
K(X,Y) = Ґ
е
i=1 
 lifi(X)fi(Y),    li і 0,     fi О L2(Rn)
с ортонормированной системой функцмй {fi} и последовательностью коэффициентов l О \l2.
Заметим, что это всего лишь обобщение на гильбертово пространство L2 следующего общеизвестного конечномерного факта: неотрицательно определенный симметрический оператор ортогонально диагонализируем и все его собственные значения неотрицательны.
Теперь все-таки докажем полноценное обращение предложения 15.
Теорема 4 Для любого пространства признаков F и любой симметричной неотрицательно определенной функции K:F×F®R существует отображение f пространства F в гильбертово пространство H, удовлетворяющее условию (15).
Замечания.
Доказательство. Рассмотрим в линейном пространстве всех функций F® R линейное подпространство H0, порожденное функциями вида f(X):Y® K(X,Y). Определим на нем билинейную форму (·,·), продолжив отображение (f(X),f(Y)) ® (f(X))(Y)=K(X,Y)=(f(Y))(X). При этом автоматически получится, что (h,f(Y))=h(Y) для любой функции h О H0. Поскольку функции вида f(X) могут оказаться линейно зависимыми, необходимо проверить корректность такого определения и это оставляется в качестве тривиального упражнения. Из симметричности и неотрицательной определенности функции K сразу следует, что полученная билинейная форма тоже симметрична и неотрицательно определена (упражнение: осознайте!). Более того, она определена строго положительно. Действительно, для симметричной неотрицательно определенной формы справедливо неравенство Шварца-Коши (h,g)2 Ј (h,h)(g,g). Значит если (h,h)=0, то (h,g)=0 для любой функции g О H0, в частности, (h,f(X))=h(X)=0 для любого X О F, то есть h=0. А раз форма (·,·) положительно определена, то пространство H0 можно пополнить по определяемой ею норме. Получится гильбертово пространство H, обещанное в теореме.
Доказательство теоремы 4 уже закончено, но чтобы не было ощущения обмана, покажем еще, что построенное гильбертово пространство H естественно вкладывается в пространство функций F® R. Действительно, для любых X О F и h О H0
|h(X)|=|(h,f(X))| Ј
Ц
 
(h,h)(f(X),f(X))
 
 =||h||
Ц
 
K(X,X)
 
(опять то же самое неравенство Шварца-Коши), а значит для любой фундаментальной последовательности функций из H0 последовательность ее значений в любой точке X О F тоже фундаментальна и последовательность сходится поточечно к некоторой функции.
Тривиальными примерами ядер являются скалярное произведение в Rd, соответствующее тождественному отображению f, произведение вещественнозначных функций K(X,Y)=f(X)f(Y), соответствующее отображению в пространство H =R, в частности, неотрицательные константы (отображение в точку) или характеристические функции декартова квадрата подмножества Rd (отображение в пару точек {0,1}).
В качестве упражнения докажите еще пару предложений.
Ядра можно строить следующими способами:
Предложение 18
Следовательно ядрами являются многочлены с положительными коэффициентами и экспоненты от ядер (например, от скалярного произведения). И еще несколько конкретных ядер над R1, естественно обобщающихся на многомерные.
Предложение 19
Следовательно и сферический гауссиан общего вида
K(X,Y)=ce-[(|X-Y|2)/2s],     c > 0, s > 0,
(17)
и самый общий гауссиан (9) также являются ядрами.
Этих ядер уже вполне достаточно, чтобы гарантировать линейную разделимость любого обучающего набора. Действительно, полиномиальное ядро K(X,Y)=((X,Y)+1)N реализуется полиномиальным отображением f, переводящим вектор X в набор всех мономов степени Ј N от координат X с некоторыми коэффициентами (проверьте и посчитайте коэффициенты!), то есть сводит разделимость к полиномиальной и гарантирует разделение любых Ј N+1 векторов. А с гауссианом дела обстоят еще лучше: гауссово ядро разделяет любые конечные наборы векторов. Докажите следующие утверждения самостоятельно.
Предложение 20
Из линейной независимости следует линейная разделимость на любые два класса.
Для сверточных ядер. т.е. ядер, определенных на Rd (или, вообще говоря, на любой коммутативной группе) и зависящих только от разности аргументов, как, например, ядра из предложений 19 и 20, есть дополнительные способы построения. Название "сверточное ядро" связано с тем, что при K(X,Y)=k(X-Y) интегральный оператор я ядром K (формула (16)) превращается в оператор свертки с функцией k:
f ® k*f=
у
х
F 
 k(·-Y)f(Y)dY ,
(18)
А свертка, как известно (а если неизвестно, легко проверить) коммутативна, ассоциативна, хорошо ведет себя при вычислении скалярного произведения в L2, а при преобразовании Фурье переходит в умножение.
Осознание мелких подробностей, опущенных в следующих двух предложениях и их доказательствах, является очередным упражнением (по стандартному курсу функционального анализа).
Предложение 21 Если функция k четна, то сверточное ядро, заданное функцией k*k симметрично и неотрицательно определено. И наоборот, любое симметричное и неотрицательно определеное сверточное ядро представимо в виде сверточного квадрата.
Действительно, симметричность непосредственно следует из четности k, а неотрицательная определенность доказывается простым вычислением: для любой пробной функции f
(k*k*f,f)=(k*f,k*f) і 0  ,
в котором также использована четность функции k. Обратное утверждение следует из предложения 22.
В частности, К(x,y)=k(x-y)=max(1-|x-y|,0) является ядром на R1, поскольку функция k является сверточным квадратом индикаторной функции c[-[ 1/2],[ 1/2]] отрезка [-[ 1/2],[ 1/2]].
Предложение 22 Если функция k четна, то определяемое ею сверточное ядро неотрицательно определено тогда и только тогда, когда ее преобразование Фурье [k\tilde] всюду неотрицательно.
Действительно, если [k\tilde] і 0, то из нее можно извлечь квадратный корень, применить к нему обратное преобразование Фурье и получить "сверточный квадратный корень" из функции k (см. предложение 21). Если же неравенство [k\tilde] і 0 неверно в (окрестности) какой-то точки, то найдется такая положительная пробная функция f (например, сферический гауссиан с центром в этой точке и малой дисперсией), что ([k\tilde]f,f) < 0. Применяя к участвующим в этом неравенстве функциям обратное преобразование Фурье, получаем, что (k*[^(f)],[^(f)]) < 0, т.е. ядро k(x-y) не является неотрицательно определенным, Предложение доказано с точностью до подробностей, связанных с тем, что извлечение квадратного корня и преобразование Фурье могут превратить регулярную функцию из L2 в обобщенную.
Приведем примеры ядер и неядер, получаемых с помощью предложений 21 и 22.
SVM с ядром обучается и работает точно так же, как SVM в линейно разделимом случае, только вместо скалярных произведений векторов признаков в задаче (13) и при ее решении нужно всюду писать ядро. В частности, обученная SVM на тестовом векторе X вычисляет функцию
f(X) = N
е
i=1 
 liyiK(Xi,X) + b = N
е
i=1 
 liyiK(Xi,X)+ yr-1 - N
е
i=1 
 liyiK(Xi,Xr)
(19)
(ср. с формулой (14), обозначения те же) и классифицирует вектор X в зависимости от знака f(X).
Заметим, что в отличие от двойственной задачи (13) эквивалентная ей исходная задача (12) плохо обобщается на случай ядер. Вектор W теперь живет в отличном от пространства признаков пространстве H, скалярное произведение в H вычислять очень трудоемко, вместо скалярного произведения (W,X) нужно писать скалярное произведение (W,f(X)), а отображение f, вообще говоря, неизвестно, В двойственной же задаче эти проблемы не возникают.
SVM с ядром легко обучается безошибочно классифицировать любой набор векторов, но после этого довольно плохо классифицирует любой другой набор. Такой эффект называется переобучением или неспособностью распознающего алгоритма к обобщению. Чтобы избежать его приходится, как ни странно, разрешить SVM ошибаться на обучающем наборе.

1.4.3  Обобщения базовой модели SVM

Вектора-аутсайдеры.  
Oт требования разделимости обучающих векторов можно и, как правило, полезно просто отказаться. Это соответствует следующим реалиям: При таком подходе может существенно сократиться число опорных векторов, а значит возрастет скорость работы SVM и главное, улучшатся теоретические оценки вероятности ее ошибок.
Реализовать это можно в соответствии со стандартной идеологией: вместо системы запретов ввести систему штрафов за их нарушение, То есть вместо максимизации толщины разделяющей полосы можно решать, например, следующую задачу:
 1
2
 (W,W) + C N
е
i=1 
 p(ei) ®
min
W,b,E 
(20)
yi((W,f(Xi))+b) і 1-ei,   ei і 0,    i=1,...,N,
где f - отображение из пространства признаков в классифицирующее евклидово или гильбертово пространство, p - неотрицательная, монотонно неубывающая и равная нулю в нуле функция штрафа, а C > 0 - эмпирически подобранный коэффициент. Идеальный штраф
p(e)=q(e-1)= м
н
о
0 при e Ј 1
1 при e > 1
 ,
превращающий второе слагаемое минимизируемой функции в формуле (20) в частоту неправильной классификации (умноженную на C) оказывается неудобен для вычислений из-за своей разрывности. На практике применяется непрерывный штраф за залезание в разделяющую полосу, иногда квадратичный, а чаще - линейный. То есть решается либо задача
 1
2
 (W,W) + C N
е
i=1 
 ei2 ®
min
W,b,E 
yi((W,f(Xi))+b) і 1-ei,    i=1,...,N
(в точке минимума автоматически ei і 0), либо чаще
 1
2
 (W,W) + C N
е
i=1 
 ei ®
min
W,b,E 
(21)
yi((W,f(Xi))+b) і 1-ei,   ei і 0,    i=1,...,N .
Вместо этой задачи удобнее решать эквивалентную ей двойственную задачу, которая получается аналогично уравнению (13) и выглядит очень похоже:
N
е
i=1 
 li -  1
2
 N
е
i,j=1 
 liljyiyjK(Xi,Xj)®
max
L 
(22)
N
е
i=1 
 liyi = 0
0 Ј li Ј C,    i=1,...,N,
где K - определяемое отображением f ядро. Решение задачи (21) выражается через решение двойственной задачи (22) по формуле (19), только теперь вектора Xi, входящие в формулу (19) с ненулевыми коэффициентами li, - это не только настоящие опорные вектора разделяющей полосы, но и вектора-аутсайдеры, попадающие внутрь полосы или даже на другую ее сторону (в качестве Xr нужно брать настоящий опорный вектор). Зато все остальные вектора обучающего набора правильно классифицируются функцией (19).
Коэффициент штрафа C подбирают так, чтобы и количество векторов-аутсайдеров было поменьше, и общее количество опорных векторов (включая вектора-аутсайдеры) было невелико, поскольку чем меньше слагаемых с ненулевыми коэффициентами в формуле (19), тем быстрее работает классификатор. Подбирать коэффициент вручную неприятно, поскольку при неравноценности ошибок для векторов разных классов имеет смысл штрафовать вектора-аутсайдеры разных классов с разными коэффициентами C1 и C-1, и подбирать придется оба коэффициента. Впрочем, в отличие от ядра, которое приходится-таки подбирать вручную, подбор коэффициентов можно частично автоматизировать.
Упражнение. Пусть (Wў,bў,Eў,rў) - решение задачи
 1
2
 (W,W) + N
е
i=1 
 (ei - nr)®
min
W,b,E,r 
(23)
yi((W,f(Xi))+b) і r-ei,   r і 0,   ei і 0,    i=1,...,N 
при некотором n: 0 Ј n Ј 1. Тогда если rў > 0, то ([(Wў)/(rў)],[(bў)/(rў)],[(Eў)/(rў)]) является решением задачи (21) при C=[ 1/(rў)], и для этого решения доля векторов-аутсайдеров среди всех обучающих векторов не превосходит n, а доля всех опорных векторов не меньше n. А если решения с rў > 0 нет, то при любом C і 0 доля опорных векторов в решении задачи (21) больше n.
Задача (23) решается аналогично задаче (21).
Упражнение. Обобщите задачу (23) на случай разных штрафов за разные ошибки.
Условно-неотрицательные ядра.  
Заметим, что в двойственной задаче (22) билинейная форма, коэффициентами которой являются значения ядра K, вычисляется не на любых парах векторов, а только на векторах вида Z=(z1,...,zN) с zi=liyi, лежащих в гиперплоскости {Z|еi=1N zi = 0}. И неотрицательная определенность такой билинейной формы, гарантировавшая сходимость итеративных методов решения двойственной задачи, на самом деле необходима не во всем пространстве, а только в этой гиперплоскости.
Симметричная функция K(·,·), такая, что при любом натуральном N, любых X1,...,XN и любых вещественных z1,...,zN, таких что еi=1N zi = 0 выполнено неравенство
N
е
i,j=1 
 zizjK(Xi,Xj) і 0
называется условно-неотрицательным ядром. Условно-неотрицательных ядер больше, чем ядер описанных выше (недостаток коротких обозначений: по-честному все ранее встречавшиеся ядра нужно было бы величать "неотрицательно определенными ядрами"), и они замечательно применимы для SVM, но способы их построения менее изучены.
Уверенность классификации.  
Если смотреть не только на знак классифицирующей функции (19), но и на ее значение, то можно оценить уверенность SVM в собственном ответе, т.е. вероятность ошибки. Причем кроме стандартного эмпирического метода оценки вероятности ошибки - распознать с помощью SVM большое количество тестовых векторов признаков, отличных от обучающих, для каждого действительного числа t посчитать долю ошибочно распознанных среди тех, на которых классифицирующая функция принимает значения между 0 и t и понадеяться, что для любого другого набора тестовых векторов получится примерно столько же - есть еще и специфические для SVM теоретические оценки (см. [20] или [13]).
SVM и нейронные сети.  
Заметим, что если ядро K инвариантно относительно сдвигов (K(X+Z,Y+Z)=K(X,Y) при любых векторах X, Y и Z), то вычисление формулы (19) можно представлять себе как работу нейронной RBF-сети с единственным нейроном второго слоя, Аналогия особенно наглядна для сферического гауссова ядра (17), очень часто применяемого и в SVM, и в RBF, Получается, что SVM - это еще один способ обучения RBF-сетей с одним выходным нейроном. По сравнению с более традиционными методами обучения RBF-сетей SVM обладает тем достоинством, что автоматически подбирает разумное число нейронов в зависимости от предоставленного обучающего материала, и тем недостатком, что гауссианы во всех нейронах обязаны быть одинаковыми с точностью до сдвига.
Многоклассовая классификация с помощью SVM.  
Для того, чтобы классифицировать не на два, а на большее число классов, можно идти разными путями: можно пытаться обобщить конструкцию SVM, а можно пытаться свести решение задачи многоклассовой классификации к решению нескольких задач двухклассовой классификации. Рассмотрим сначала несколько вариантов второго подхода. Во всех этих вариантах удобно считать, что зафиксирован общий набор обучающих векторов всех q классов, хотя на самом деле это не обязательно.
Двоичное кодирование.
Будем записывать номер класса в виде k-значного (k=йlog2qщ) двоичного числа. Обучим k SVM, каждая из которых распознает один из k разрядов номера класса. По результатам распознавания входного вектора этими k SVM однозначно восстанавливается номер класса, к которому он принадлежит. На самом деле все не так радостно, поскольку любая ошибка любой из этих SVM приводит к неправильному ответу, а обучить SVM надежно разделять произвольные наборы классов довольно трудно, да и получаются они медленными (т.е. с большим количеством опорных векторов). Немного уменьшить ошибку распознавания можно применяя для номера класса двоичные коды с коррекцией ошибок и обучая разные SVM на разных наборах обучающих векторов. Но чаще идут совсем другим путем, и вместо очень малого количества очень сложных SVM обучают и применяют большое количество более простых.
Каждый против всех.
Для каждого класса Cl обучим SVM, считающую вектора этого класса положительными, а всех остальных классов - отрицательными. Пусть fl - классифицирующая функция (19) l-й SVM. Для каждого распознаваемого вектора X вычислим все q значений f1(X),...,fq(X) и выберем из них наибольшее. Соответствующий класс, для которого получена максимальная оценка, и будет ответом распознавателя. Или, продолжая аналогию с нейронной сетью, перенормируем ответы всех SVM на отрезок [0,1], например, применив к ним функцию (2), и будем интерпретировать их в соответствии с общей теорией . Кстати, получившийся набор SVM является-таки RBF-сетью, но откровенно неэффективной: результат вычислений каждого нейрона первого слоя используется только одним нейроном второго слоя, и при этом нейроны первого слоя могут дублироваться.
Каждый против каждого.
Вместо q "больших" SVM, отличающих каждый класс от всех остальных, обучим [(q(q-1))/2] "маленьких" SVM, различающих пары классов. Каждая из них, естественно, обучается только на векторах, принадлежащих двум интересующим ее классам, поэтому время обучения и количество опорных векторов получаются-таки меньше, чем у SVM типа "каждый против всех". Для каждого распознаваемого вектора X вычислим все [(q(q-1))/2] значений fij(X)=-fji(X) классифицирующих функций, отделяющих i-й класс ("положительный") от j-го ("отрицательного"), затем вычислим q сумм fi(f,X)=еj № if(fij(X)), где f - некоторая монотонно неубывающая функция, например, (2) или sign, и выберем из них наибольшую. Соответствующий класс, для которого получена максимальная оценка, и будет ответом распознавателя.
Турнир на выбывание.
[(q(q-1))/2] "маленьких" SVM из предыдущего пункта можно использовать более экономным способом. Для каждого распознаваемого вектора X устроим среди q классов турнир за право обладания этим вектором. Игра между двумя классами состоит в применении к вектору X различающей эти классы SVM и победитель естественно определяется знаком классифицирующей функции. Проигравший класс выбывает, а победитель играет дальше. После q-1 игр, т.е. работы q-1 "маленьких" SVM, все классы, кроме "чемпиона" выбывают, и именно к нему приписывается вектор X.
Дихотомия.
Разобьем множество всех q классов на два подмножества - "надкласса" - и обучим SVM, определяющую принадлежность обучающего вектора надклассу. Повторим процедуру для каждого надкласса. И т.д. В конце концов получим двоичное дерево, q-1 нетерминальным вершинам которого соответствуют SVM, а q терминальным - классы. Каждый распознаваемый вектор X сперва подадим на классификацию SVM верхнего уровня, затем, в зависимости от ее ответа, одной из не более двух SVM следующего уровня и т.д. После не более q-1 шагов (а для сбалансированного дерева - всего лишь йlog2qщ шагов) получим ответ.
Поскольку время работы каждой SVM пропорционально количеству опорных векторов (очевидно), а время обучения растет быстрее квадрата числа обучающих векторов (не очевидно, но для общеизвестных методов обучения верно), непосредственно из конструкции видно, что турнирный и дихотомический методы должны обучаться и работать быстрее, чем метод "каждый против всех", а дихотомический со сбалансированным деревом - еще и быстрее двоичного кодирования. На практике так оно и получается, даже если модифицировать их так, чтобы они выдавали в качестве ответа не только номер класса-победителя, но и классы, занявшие несколько следующих мест, и их количественные оценки. Эксперименты показывают неочевидный факт, что иногда у турнирного метода еще и ошибок меньше, чем у методов "каждый против всех" и "каждый против каждого". А вот у дихотомического метода при неудачном делении на надклассы ошибок может быть неприемлемо много.
Теперь опишем идею конструкции многоклассовой SVM. Для простоты забудем про вектора-аутсайдеры и про ядра. Тогда минимизационную задачу
(W,W) ®
min
W,b 
yi((W,Xi)+b) і 1,    i=1,...,N 
можно переписать в следующем странном виде:
(W-1,W-1)+(W1,W1) ®
min
W-1,b-1,W1,b1 
((Wyi,Xi)+byi)-((Wm,Xi)+bm) і 2,     m О {-1,1}, m № yi,  i=1,...,N
W-1+W1=0,    b-1+b1=0.
Действительно, решение одной задачи получается из решения другой при W1=W и b1=b. А такую задачу уже понятно, как обобщить на много классов. Пусть yi теперь равно не ±1, а номеру класса, которому принадлежит обучающий вектор Xi.
q
е
m=1 
 (Wm,Wm) ®
min
Wm,bm,1 Ј m Ј q 
(24)
((Wyi,Xi)+byi)-((Wm,Xi)+bm) і 2,     1 Ј m Ј q, m № yi,  i=1,...,N
q
е
m=1 
 Wm=0,    q
е
m=1 
 bm=0.
На практике решают не в точности такую задачу, а какое-либо ее обобщение, допускающее, но штрафующее обучающие вектора-аутсайдеры, а также использующее ядра. В результате обучения получается набор из q функций fl(·)=(Wl,·)+bl, таких что их попарные разности более-менее разделяют пары классов. Для каждого распознаваемого вектора X значения f1(X),·,fq(X), как и при распознавании методом "каждый против всех", оценивают правдоподобность принадлежности вектора X каждому классу. Теоретически многоклассовая SVM должна работать быстрее и лучше метода "каждый против всех", поскольку если из каждой построенной в этом методе классифицирующей функции fl вычесть среднее арифметическое всех q этих функций, получится допустимый, но вообще говоря, неоптимальный, набор функций, удовлетворяющих ограничениям обобщенной задачи (24). Однако обучается она еще медленнее.
Одноклассовая SVM.  
Для того, чтобы научиться хорошо узнавать рукописную букву "A" ребенку нужно увидеть много разных вариантов написания буквы "A", но совершенно не нужно видеть, как пишется буква "U" (а вы когда-нибудь видели? это заглавная греческая буква ипсилон). Эту идею можно применить и к обучению SVM, в частности для ускорения обучения многоклассовому распознаванию.
Ограничимся самым распространенным случаем гауссова ядра. Соответствущее ему отображение f:Rd® H=L2(Rd) (предложение 20) переводит все пространство-прообраз в небольшой колпачок, высеченный на сфере с центром в 0 О H (т.е. в функции, тождественно равной нулю) конусом всюду положительных функций. Возьмем в H образы обучающих векторов одного и того же класса ("положительного"), объявим 0 "отрицательным" классом и обучим SVM, различающую эти два класса, т.е. хорошо отделяющую некоторое конечное множество на сфере от центра сферы гиперповерхностью. Из предложения 20 следует, что отделить всегда можно. От двуклассовой SVM общего вида эта SVM отличается лишь небольшими техническими деталями. Во-первых, поскольку 0 не является образом никакого обучающего вектора, некоторые используемые в вычислениях скалярные произведения в H, а именно, произведения с 0, не представимы в виде значения ядра на паре векторов; зато все они благополучно равны нулю. И во-вторых, ошибку на векторе 0 лучше запретить, чтобы он заведомо был опорным.
Из таких одноклассовых SVM аналогично методу "каждый против всех" можно собрать очень быстрый - и по времени обучения, и по скорости работы -, хотя и не самый точный многоклассовый классификатор:
Каждый за себя.
Для каждого класса Cl обучим одноклассовую SVM. Пусть fl - классифицирующая функция (19) l-й SVM. Для каждого распознаваемого вектора X вычислим все q значений f1(X),...,fq(X) и выберем из них наибольшее. Соответствующий класс, для которого получена максимальная оценка, и будет ответом распознавателя.
Приближение функций (SVR, Support Vector Regression).  
Метод опорных векторов, как впрочем и нейронные сети (см. начало раздела 1.2.2), и даже векторное квантование, можно применять не только для классификации, но и для приближения функций, причем при этом развивается целая наука. Не пытаясь изложить всю науку (см. [20]), проиллюстрируем основные идеи и конструкции.
Рассмотрим простейшую задачу "наилучшего" приближения экспериментальной функции от d переменных, про которую известны только ее значения yi в N "обучающих векторах" Xi, линейной функцией (впоследствии это будет, конечно, не линейная функция от координат, а линейная комбинация некоторых базисных функций). Линейную функцию сразу будем записывать в традиционном виде (11). Тогда стандартный метод наименьших квадратов состоит в решении минимизационной задачи
N
е
i=1 
 e(f(Xi),yi) = N
е
i=1 
 ((W,Xi)+b-yi)2 ®
min
W,b 
 ,
где через e(z,y)=(z-y)2 обозначена квадратичная функция ошибки. Эта задача элементарно сводится к решению системы d+1 линейных уравнений (равенство нулю частных производных по W и b). Но оказывается, что самым замечательным образом приближая функцию на обучающих векторах, решение, полученное методом наименьших квадратов, не слишком хорошо приближает ее на других. Статистически лучшее приближение можно получить, решая подобную минимизационную задачу с добавленным небольшим штрафом за отклонение линейной аппроксимирующей функции от константы, например, с квадратичным штрафом E(W,b) пропорциональным ||W||2:
E(W,b) + N
е
i=1 
 e(f(Xi),yi) = d||W||2 + N
е
i=1 
 ((W,Xi)+b-yi)2 ®
min
W,b 
 ,
(25)
Этот метод называется регуляризацией и обсуждается, например, в книге [1]. К опорным векторам он пока отношения не имеет.
Опорные вектора появляются при замене удобного традиционного квадратичного штрафа e(z,y)=(z-y)2 за отклонение значения в точке на какой-либо сложный и неудобный штраф, равный 0 для достаточно малых отклонений, а затем начинающий резко расти. Чаще всего применяется кусочно-линейный штраф вида e(z,y)=max(0,|z-y|-e). Платить за такой странный штраф приходится тем, что аналог минимизационной задачи (25) становится трудно решать. Зато имеются и теоретические (см. [20]), и практические результаты, показывающие, что при таком штрафе вероятность большой (больше e) ошибки приближающей функции на тестовых (не обучающих!) векторах меньше, чем при квадратичном.
Продемонстрируем самое начало счета. Задачу (25), превратившуюся в
E(W,b) + N
е
i=1 
 e(f(Xi),yi) = d||W||2 + N
е
i=1 
 max
(0,|(W,Xi)+b-yi|-e) ®
min
W,b 
 ,
(26)
можно переписать в виде
 1
2
 (W,W) + C N
е
i=1 
 (ei-+ei+) ®
min
W,b,E 
(27)
(W,Xi)+b і yi-e-ei-,    ei- і 0,    i=1,...,N
(W,Xi)+b Ј yi+e+ei+,    ei+ і 0,    i=1,...,N
где через C обозначено число [ 1/(2d)], а через E - набор всех 2N чисел ei- и ei+. Эта задача уже совсем похожа на задачу (21), и решается аналогичным переходом к двойственной задаче. Обещанное выше обобщение с аппроксимации линейными функциями до аппроксимации линейными комбинациями базисных функций в терминах двойственной задачи легко и естественно выражается в терминах ядер. Заметим еще, что в отличие от подбираемого вручную коэффициента C, порог e можно оптимизировать автоматически, добавив в минимизируемую функцию линейный по e штраф.
Если не заниматься автоматическим обучением e, то задачи (26) и (27) можно свести к задаче (21) и непосредственно. А именно, для каждого из N обучающих векторов построим в (d+1)-мерном пространстве Rd×R два вектора [^X]i-=(Xi,yi-e) и [^X]i+=(Xi,yi+e), объявим их принадлежащими отрицательному и положительному классу, соответственно, и решим для полученных 2N обучающих векторов задачу (21), т.е. построим линейную SVM, более-менее отделяющую отрицательные вектора от положительных. Это сведение выдерживает и переход от линейной задаче к задаче с ядрами, только ядра в Rd×R должны иметь вид K((X1,y1),(X2,y2))=Kў(X1,X2)+y1y2.
Про SVM написано очень много, см., например, аннотированную библиографию [19]. Любопытно прочесть исторически первое описание SVM в его современном виде [15], хотя еще с другим названием. Семисотстраничный талмуд основоположника [20] по науке, из которой произошла идея SVM, может оказаться интересным, но читать его трудно (для разминки можно прочесть двенадцатистраничную авторскую выжимку [21] из него, в которой к тому же меньше опечаток в формулах). Начинать лучше с компактного введения [22]. Подобное компактное введение [23] есть и для SVR. Имеется и небольшой сравнительный обзор [24] различных методов многоклассового распознавания с помощью SVM.

2  Распознавание (частично) упорядоченных наборов объектов

Сначала - в нижеследующем введении и в разделе 2.1 - мы ограничимся рассмотрением линейно упорядоченных последовательностей. Затем в разделе 2.2 перейдем к более общему случаю частичного порядка.
Распознавание последовательности объектов (например, слов) существенно отличается от распознавания отдельных объектов (например, букв) тем, что разных длинных последовательностей настолько много, что для обучения узнаванию каждой последовательности в лицо требуется абсолютно неприемлемое время. Еще более наглядный пример - распознавание молекул ДНК, являющихся очень длинными словами в алфавите из четырех букв. Поэтому для распознавания последовательностей применяется следующая схема. Вот последний шаг распознавания и его взаимодействие с предыдущими и будет рассматриваться далее.
Тривиальный алгоритм распознавания - сегментировать, распознать каждый кусочек и в качестве общего ответа выдать последовательность наиболее вероятных ответов - работает плохо. Он не исправляет ошибок сегментации и адекватен только распознаванию случайной последовательности независимых хорошо разделенных объектов. Но во всех интересных задачах распознавания последовательности не случайны, а в случае рукописного текста - еще и плохо разделимы.

2.1  Скрытая марковская модель (HMM, Hidden Markov Model)

2.1.1  Скрытая марковская модель с дискретным временем, конечным пространством состояний и конечным пространством наблюдаемых

В этом разделе описываются простейшие примеры распознавания последовательностей - слишком простые, чтобы их можно было применить для реального распознавания рукописного текста, но являющиеся базовыми для многих систем распознавания и моделирования последовательностей чего угодно. К сожалению, рукописный текст - не самый удачный материал для демонстрации простых моделей.
Пример 1: моделирование и распознавание последовательности объектов.  
Пусть имеется классификатор одиночных рукописных символов (например, обученная система векторного квантования или модель из следующего примера), а хочется построить систему распознавания последовательностей рукописных символов, написанных на разграфленном бланке - по символу в клетке. Тогда можно сразу применить классификатор к содержимому каждой клетки и свести задачу к распознаванию последовательностей классификационных кодов. Вот такую систему распознавания мы и будем рассматривать. При этом нужно учитывать, что Сначала для простоты будем считать, что допустимы не любые ошибки, а только замены, т.е. каждому правильно или неправильно распознанному символу соответствует ровно один символ, который на этом месте должен быть написан, и наоборот. То есть нужно по последовательности X[1,T]=(x1,...,xT) из T наблюдаемых кодов восстановить "наиболее вероятную" последовательность Y[1,T]=(y1,...,yT) символов, которая должна была быть написана (или несколько таких "наиболее вероятных" последовательностей). 4 Нужно только придать смысл словам "наиболее вероятные", что удобнее всего сделать построив-таки честную вероятностную модель. А чтобы распознавание было хорошим, эта модель должна в какой-то степени знать не только алфавит языка, на котором пишут, но и его словарь, грамматику, частоты слов и букв и т.п.
Простейшая вероятностная модель писания на разграфленном бланке такова. Пусть C={C1 ,...,Cq} - множество возможных символов, а Q={Q1,...,QK} - множество кодов, выдаваемых классификатором. Человек, вписывающий символы в клеточки, - это автомат с q состояниями. Каждое i-e состояние соответствует намерению написать символ Ci. Но намерение, вообще говоря, осуществляется не идеально, и может оказаться написано что угодно, более-менее напоминающее один из многочисленных способов написания этого символа - как по ошибке, так и из-за нестабильного почерка или качнувшегося стола. Это что угодно классификатор классифицирует, добавляя еще и свои ошибки, и выдает код Qj с вероятностью bij(...), зависящей, вообще говоря, от погоды, от времени суток, от места символа в последовательности, от соседних символов, но в основном от почерка пишущего. В простейшей модели всеми этими зависимостями пренебрегают. Матрица B=(bij) называется матрицей эмиссии.
Теперь для того, чтобы иметь возможность вычислять вероятности тех или иных событий, нужно еще что-то сказать про вероятность намерений, т.е вероятность появления символа Cj в тексте или, что пока то же самое, пребывания пишущего автомата в j-м состоянии. Самое простое предположение, что она зависит только от j, достаточно для распознавания, но оно в точности соответствует распознаванию текста не как последовательности, а как неупорядоченной кучи случайных символов, и далее не рассматривается. Самое правильное предположение, что вероятность j-го состояния зависит от всего текста и от места в нем, неприемлемо сложно. Разумным приближением является предположение, что вероятность j-го состояния зависит от нескольких соседних - предшествующих и последующих - состояний. Оказывается достаточно рассмотреть довольно простой случай зависимости только от одного предшествующего состояния, а остальные случаи свести к нему изменением пространства состояний.
А именно, положим, что из i-го состояния пишущий автомат переходит в j-е состояние с вероятностью aij, ни от чего, кроме i и j не зависящее. Матрица A=(aij) называется матрицей перехода. И еще как-нибудь определим начальные вероятности состояний автомата. Этого уже достаточно для распознавания последовательностей символов как последовательностей (не то, чтобы для хорошего распознавания, но для придания смысла словам "наиболее вероятная последовательность"). А для улучшения распознавания проделаем следующий трюк. Добавим к q имеющимся состояниям автомата, соответствующим символам, еще некоторое, весьма немалое, количество состояний вида "слово и место в нем", т.е. пар вида (W[1,L],k), где W[1,L]=(W1,...,WL) - последовательность из L символов из алфавита C (например, словарное слово, слог или часто встречающаяся тройка последовательных букв, вроде "ющи"), и 1 Ј k Ј L. Состояние (W[1,L],k) соответствует намерению написать символ Wk и далее писать последовательность W[k+1,L] при том, что последовательность W[1,k-1] только что написана (возможно, с описками).
При таком увеличении числа состояний размеры матрицы эмиссии и особенно матрицы перехода возрастают. Но матрица эмиссии растет не зря: она теперь может моделировать зависимость вероятности того или иного написания символа от контекста. А матрица перехода оказывается довольно разреженной. Действительно, из состояния (W[1,L],k) при k < L можно перейти только в состояние (W[1,L],k+1) (и этот переход имеет вероятность 1), а из состояния (W[1,L],L) - только в состояния вида (Wў[1,Lў],k), для которых в случае k > 1 начальный отрезок Wў[1,k-1] совпадает с конечным отрезком W[L-k+2,L]. Или можно слегка пожертвовать разреженностью и разрешить из состояния (W[1,L],k) маловероятные переходы обратно в него же и в еще несколько состояний (W[1,L],k+1), (W[1,L],k+2), ... Такая модель соответствует возможности описок общего вида: не только замены буквы на букву, но и появления лишних букв или потери нужных.
Задание пространства состояний модели и допустимых переходов между ними, чтобы модель была не слишком сложной и могла достаточно хорошо распознавать последовательности символов, требует естественного интеллекта. А оптимизация численных параметров модели, т.е. коэффициентов матриц эмиссии и перехода, может производиться автоматизированными процедурами обучения, похожими на процедуры обучения нейронных сетей.
Пример 2: моделирование и распознавание объекта как последовательности неизвестно чего.  
В прошлом веке на уроках чистописания первоклассников сначала долго заставляли рисовать палочки, крючочки и кружочки, и только потом учили складывать из них буквы. В реальной жизни люди тоже пишут (и распознают!) буквы как последовательности небольших типовых элементов, но не столь единообразных, как в прописях. Например, две вертикальные палочки, перечеркнутые горизонтальной, - это, вероятно, буква `Н'. И если вертикальные палочки - не совсем палочки или не совсем вертикальные, то все равно `Н'. Но если они сверху сближаются, то больше похоже на `А', а если горизонтальная палочка находится высоко, то на `П'.
При машинном распознавании удобнее выделять не только и не столько палочки и крючочки, сколько способы их стыковки лруг с другом: направленные в разные стороны галочки, петельки, Т-образные ветвления и т.п. Предположим, что эта черновая работа проделана и изучаемый фрагмент рукописного текста закодирован в виде последовательности таких характеристических элементов, упорядоченных как-то слева направо сверху вниз. Вопрос: насколько эта последовательность похожа на букву `А'? Тот же вопрос для всех остальных распознаваемых символов.
Попробуем смоделировать построение одной буквы в виде последовательности элементов. Во-первых, буква может иметь несколько существенно различных написаний (например, `А' треугольное, `А' треугольное с завитушками, `А' круглое, ...) и их нужно моделировать отдельно. Во-вторых, даже одно написание одной буквы в зависимости от почерка порождает разные последовательности характеристических элементов. В-третьих, кроме правильных написаний бывают неправильные (рука дрогнула, клякса, ручка плохо пишет, ...). Всех возможностей не предусмотришь, поэтому будем моделировать только несколько наиболее часто встречающихся вариантов и то, что получается из них небольшими возмущениями.
Выписывание последовательности Qi1,...,QiL из L характеристических элементов поручим детерминированному конечному автомату с L+1 состояниями с1,...,сL+1, который в каждом l-м, l Ј L, состоянии Cl порождает элемент Qil и переходит в следующее состояние. А для порождения возможных "небольших возмущений" последовательности превратим автомат в стохастический: в i-м состоянии он может порождать любой элемент Qj с вероятностью bij (ср. с матрицей эмиссии ) и с вероятностью aij (ср. с матрицей перехода ) переходить в близкое к i+1-му j-е состояние. Как правило, aij > 0 только при i Ј j Ј i+2, т.е. кроме перехода в следующее состояние допускаются проскакивание его и задержка в текущем состоянии. Существенно, что aij=0 при i > j. Такие модели называются LR-моделями (left-right, слева направо). Вероятности bi,ij и ai,i+1 унаследованных от детерминированного автомата действий естественно полагать близкими к 1, а остальные положительные вероятности - близкими к 0, хотя это и не обязательно. Заметим, что каждое состояние детерминированного автомата имело точный смысл ("выписано столько-то элементов такой-то последовательности"), а у стохастического автомата этот точный смысл уже утерян.
Автоматы для нескольких вариантов написания символа объединяются в один автомат, моделирующий символ: к их несвязному объединению добавляется общее начальное состояние C0, которое не порождает никакого характеристического элемента и из которого возможны переходы в начальные и вторые состояния всех вариантов, а их конечные состояния склеиваются 5.
 charHMM.png
Figure 1: Пример графа допустимых переходов для марковской модели символа
Состояния и допустимые переходы в такой модели изображены на рис. 1.
Такая модель символа позволяет ответить на вопрос, насколько какая-то последовательность характеристических элементов похожа на этот символ: настолько, какова вероятность порождения ее моделью символа. Эти вероятности можно вычислить для всех символов и проанализировав их решить, на какой символ эта последовательность более всего похожа, т.е. классифицировать ее. Сразу предупреждаем, что это не обязательно тот символ, для которого вероятность максимальна.
Ниже описано, как вычислять эти вероятности быстро, и как оптимизировать (обучать) матрицы перехода и эмиссии, чтобы модель каждого символа хорошо "узнавала" всевозможные написания этого символа.
Формальное определение HMM.  
Скрытая марковская модель (HMM) с дискретным временем, конечным пространством состояний и конечным пространством наблюдаемых состоит из Тем самым, кроме количества скрытых состояний n и наблюдаемых состояний m, скрытая марковская модель определяется еще конечным набором действительных параметров: удовлетворяющих стандартным вероятностным нормировкам: все элементы матриц и вектора неотрицательны и сумма элементов каждой строки равна 1. Итого получается ((n-1)+n(n-1)+n(m-1))-мерное пространство параметров. Через P =(P,A,B) будем обозначать весь набор параметров.
В дальнейшем для краткости мы будем отождествлять и скрытые состояния, и наблюдаемые, с их номерами,
Проведем несколько простых, но полезных для дальнейшего, вычислений и оценим их трудоемкость. Вероятность того, что последовательность Y[1,T] скрытых состояний порождает последовательность X[1,T] наблюдений равна
P{X[1,T]|Y[1,T]} = T
Х
t=1 
 bytxt,
а вероятность появления самой последовательности Y[1,T] равна
P{Y[1,T]} = py1 T-1
Х
t=1 
 aytyt+1
(обе эти формулы следуют непосредственно из условий независимости в определении скрытой марковской модели). Значит вероятность наблюдения последовательности X[1,T], порожденной последовательностью Y[1,T], равна
P{X[1,T],Y[1,T]} = P{Y[1,T]} P{X[1,T]|Y[1,T]} = py1 T-1
Х
t=1 
 aytyt+1 T
Х
t=1 
 bytxt
(28)
и вычисляется за 2T-1 умножений, а вероятность наблюдения последовательности X[1,T] без каких-либо условий по определению равна
P{X[1,T]} =
е
Y[1,T] 
 P{X[1,T],Y[1,T]} =
е
y1,...,yT 
 ж
и 		py1 T-1
Х
t=1 
 aytyt+1 T
Х
t=1 
 bytxt ц
ш
(29)
но по этой формуле она вычисляется катастрофически медленно: за порядка 2TnT операций. То есть для модели с всего лишь 100 скрытыми состояниями нереально посчитать вероятность последовательности наблюдений длины 10.
К счастью эту вероятность можно считать быстрее. Определим
at(i,X) = P{X[1,t],yt=i} =
е
Y[1,t]|yt=i 
 P{X[1,t],Y[1,t]}.
(30)
Тогда эти вероятности можно вычислять рекурсивно по t:
a1(i,X)
=
P{x1,y1=i}
=
pi bix1
at+1(i,X)
=
n
е
j=1 
 P{X[1,t],yt=j}P{xt+1,yt+1=i|X[1,t],yt=j}
=
n
е
j=1 
 at(j,X) aji bixt    при 1 Ј t < T,
а
P{X[1,T]} = n
е
i=1 
 aT(i,X).
(31)
Таким способом P{X[1,T]}, а заодно и все at(i,X) при 1 Ј t Ј T и 1 Ј i Ј n можно посчитать за порядка 3Tn2 операций. Более того, множитель n2 - это количество элементов матрицы перехода. Если матрица перехода разреженная и в ней только nў элементов могут отличаться от нуля, то вероятность P{X[1,T]} можно посчитать за 3Tnў операций. На практике обычно строят модели с довольно большим числом n скрытых состояний, но не очень большим и фиксированным количеством mў возможных (т.е. вероятность которых может быть ненулевой) переходов из каждого состояния, т.е. nў=mўn. Странное обозначение mў намекает на то, что обычно mў=m (количество наблюдаемых состояний).
Вот еще несколько простых упражнений на осознание (т.е. проверку того, что написанные равенства следуют из определения марковской модели) и быстрое вычисление условных вероятностей в марковской модели, результаты которых понадобятся при ее обучении.
Упражнение. Для последовательности наблюдений X=X[1,T] все условные вероятности вида
bt(i,X) = P{X[t+1,T]|yt=i}
(32)
при 1 Ј t Ј T и 1 Ј i Ј n можно посчитать за порядка 3Tnў операций:
bT(i,X)
=
1
bt(i,X)
=
n
е
j=1 
 aij bjxt+1 bt+1(j,X)    при 1 Ј t < T,
Упражнение. При любом 1 Ј t Ј T
n
е
i=1 
 at(i,X)bt(i,X) = P{X[1,T]} .
Упражнение. Сколько нужно операций для вычисления всех условных вероятностей вида
gt(i,X) = P{yt=i|X[1,T]} =  at(i,X)bt(i,X)
P{X[1,T]}
 ?
(33)
Упражнение. Тот же вопрос для вероятностей вида
xt(i,j,X) = P{yt=i,yt+1=j|X[1,T]} =  at(i,X)aijbjxt+1bt+1(j,X)
P{X[1,T]}
 .
(34)
Упражнение. Посчитать вероятность P{yt+1=j|X[1,T],yt=i}.
Распознавание с помощью HMM.   Задача распознавания состоит в том, чтобы по имеющейся последовательности наблюдений X[1,T] восстановить последовательность скрытых состояний Y*[1,T], порождающую эти наблюдения с наибольшей вероятностью (пример 1 ) и/или найти саму эту вероятность (пример 2 ). Искать максимум перебором - неприемлемо долго (nT вычислений формулы (28)), но можно воспользоваться методом динамического программирования (см., например, [29]), который в данном случае называется алгоритмом Витерби [25]. Выигрыш в скорости получается такой же, как при использовании формулы (31) и непосредственно предшествующих ей вместо (29).
А именно, аналогично формуле (30), определим
dt(i,X) =
max
Y[1,t]|yt=i 
 P{X[1,t],Y[1,t]}
(35)
и будем вычислять dt(i,X) рекурсивно по t при всех i одновременно, запоминая для каждой пары (t,i) при t > 1 предпоследнее состояние y*t-1=ut(i,X) последовательности Y*, максимизирующей правую часть равенства (35). Вот эти вычисления:
d1(i,X)
=
P{x1,y1=i}
=
pi bix1
dt+1(i,X)
=

max
j|1 Ј j Ј n 
 P{X[1,t],yt=j}P{xt+1,yt+1=i|X[1,t],yt=j}
=
bixt
max
j|1 Ј j Ј n 
 dt(j,X) aji    при 1 Ј t < T
ut+1(i,X)
=
arg
max
j|1 Ј j Ј n 
 dt(j,X) aji    при 1 Ј t < T
P*T(X)
=

max
Y[1,T] 
 P{X[1,T],Y[1,T]}
=

max
j|1 Ј j Ј n 
 dT(j,X)
y*T(X)
=
arg
max
j|1 Ј j Ј n 
 dT(j,X).
Последние два уравнения определяют максимальную совместную вероятность P*T(X) последовательности наблюдений X[1,T] и порождающей ее последовательности скрытых состояний Y*[1,T] и последнее ее состояние, соответственно. Предшествующие состояния находятся последовательно по формуле
y*t(X) = ut+1(y*t+1(X),X)       t=T-1,...,1.
Как и при вычислении вероятности P{X[1,T]} последовательности наблюдений по формуле (31), для распознавания этой последовательности требуется порядка 3Tnў арифметических операций.
Как правило, распознавание последовательностей производится именно вышеописанным алгоритмом Витерби, только слегка подправленным, чтобы избежать возможной потери точности из-за того, что при больших t все dt(i,X) очень близки к нулю, см. ниже , Но при очень больших моделях с недостаточно разреженной матрицей перехода его скорость недостаточна. Ссылки на более быстрые методы распознавания приведены в [28].
Обучение HMM.   Задача обучения состоит в том, чтобы подобрать параметры P модели так, чтобы она распознавала правильно, или хотя бы уверенно, или хотя бы хорошо моделировала. То есть нужно взять обучающий набор X =X1,...,XN последовательностей наблюдений и, соответственно, сделать одно из трех: Первый способ обучения - это обучение с учителем, его можно проводить, например, методом градиентного спуска, и он всем хорош кроме своей трудоемкости. Остальные способы - это обучение без учителя, хотя во втором способе можно использовать и учителя: отбраковывать совсем неправильно распознанные последовательности и настраивать параметры только по более-менее правильно распознанным. Чаще всего применяется третий способ обучения (иногда с последующим доучиванием другими способами), поскольку для него известен быстрый алгоритм.
Этот алгоритм, в общей ситуации называемый EM (expectation maximization - максимизация ожидания) или, конкретно для скрытых марковских моделей, алгоритмом Баума-Велша (разработан в серии статей Баума с соавторами в 1967-1972 годах, окончательный вариант описан в [26]), является итеративным и сходится, вообще говоря, не к глобальному максимуму правдоподобия, а к локальному. С точностью до технических отличий он совпадает с вышеописанным методом обучения RBF-сетей .
Поскольку параметры модели теперь будут меняться, мы их будем явно указывать в формулах. Зафиксируем обучающий набор X из N последовательностей наблюдений Xi=Xi[1,Ti] длин Ti и начальный набор параметров модели P0 и будем пытаться увеличить правдоподобие P{X|P} или, что то же самое, уменьшить E{X|P}=-lnP{X|P}. Из формулы (29) следует, что
P{X|P}
=
N
Х
i=1 
 P{Xi|P} = N
Х
i=1 
е
Y[1,Ti] 
 P{Xi[1,Ti],Y[1,Ti]|P}
=
N
Х
i=1 
е
y1,...,yTi 
 ж
и 		py1 Ti-1
Х
t=1 
 aytyt+1 Ti
Х
t=1 
 bytxit ц
ш 		,
т.е. мы пытаемся максимизировать многочлен степени 2еi=1N Ti с неотрицательными коэффициентами от не более чем n+n2+mn переменных (их может быть меньше из-за разреженности матрицы перехода) в пересечении положительного ортанта с набором гиперплоскостей вида
n
е
j=1 
 pj=1 , n
е
j=1 
 aij=1 и m
е
j=1 
 bij=1.
(36)
Для этой задачи легко выписывается лагранжиан, но уравнения Лагранжа являются полиномиальными уравнениями высокой степени и аналитически не решаются. Поэтому как и при обучении RBF-сетей без учителя мы пойдем другим путем.

E(X,P)-E(X,P0)
=
- N
е
i=1 
 ln  P{Xi|P}
P{Xi|P0}
=
- N
е
i=1 
 ln ж
и
е
Y[1,Ti] 
  P{Xi,Y[1,Ti]|P}
P{Xi|P0}
 ц
ш
=
- N
е
i=1 
 ln ж
и
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}  P{Xi,Y[1,Ti]|P}
P{Y[1,Ti]|Xi,P0}P{Xi|P0}
 ц
ш
=
- N
е
i=1 
 ln ж
и
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}  P{Xi,Y[1,Ti]|P}
P{Xi,Y[1,Ti]|P0}
 ц
ш
Ј
- N
е
i=1 
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}ln ж
и 		 P{Xi,Y[1,Ti]|P}
P{Xi,Y[1,Ti]|P0}
 ц
ш
=
- N
е
i=1 
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}lnP{Xi,Y[1,Ti]|P}
+ N
е
i=1 
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}lnP{Xi,Y[1,Ti]|P0}
Неравенство в этой цепочке преобразований следует из выпуклости функции -ln(·) и того, что условные вероятности P{Y[1,Ti]|Xi,P0} являются вероятностями, т.е. неотрицательны и их сумма по всем возможным последовательностям Y длины Ti равна 1.
Обозначим
Q(X,P0,P) = - N
е
i=1 
е
Y[1,Ti] 
 P{Y[1,Ti]|Xi,P0}lnP{Xi,Y[1,Ti]|P} .
Тогда полученное неравенство означает, что
E(X,P) Ј Q(X,P0,P) - Q(X,P0,P0) + E(X,P0),
т.е. правая часть мажорирует E(X,P) и совпадает с ней в точке P0. Значит если удастся найти точку P глобального минимума правой части или, что то же самое, точку минимума Q(X,P0,·) по всей области определения, то E(X,P) Ј E(X,P0). Прямые вычисления производных Q(X,P0,P) по параметрам P (дифференцировать сумму логарифмов намного приятнее, чем логарифм суммы), показывают, что критическая точка Q(X,P0,P) почти всегда единственна, и является точкой минимума.
Заметьте, что предыдущий абзац скопирован из описания алгоритма обучения RBF-сетей почти дословно. Однако для марковских моделей вычисления более громоздки и мы их опустим, ограничившись предъявлением и обсуждением ответа. Это тоже довольно громоздко.
Предложение 23 Минимум функции Q(X,P0,·) достигается в точке P* с координатами
p*j
=
 1
N
 N
е
i=1 
 g1(j,Xi)
(37)
a*jk
=
N
е
i=1 
 Ti-1
е
t=1 
 xt(j,k,Xi)
N
е
i=1 
 Ti-1
е
t=1 
 gt(j,Xi)
(38)
b*jk
=
N
е
i=1 
е
t|xit=k 
 gt(j,Xi)
N
е
i=1 
 Ti
е
t=1 
 gt(j,Xi)
 .
(39)
Здесь gt(·,·) и xt(·,·,·) определены уравнениями (30), (32), (33) и (34) для параметров модели P0. Если при каком-то значении j знаменатель правой части уравнения (38) или (39) равен 0, то числитель тоже равен 0 и Q(X,P0,(P,A,B)) не зависит от j-й строки матрицы A (или, соответственно, B); при этом определим a*jk=a0jk (соответственно, b*jk=b0jk) при всех k.
Алгоритм обучения Баума-Велша состоит в итеративном пересчете параметров марковской модели c P0 на P* по формулам (37)-(39). Он замечателен во многих отношениях.
Упражнение.
Начальные значения параметров A и P модели можно задавать произвольно, уважая вероятностные нормировки и учитывая то, что нули в матрице перехода навеки останутся нулями. Наоборот, начальные значения матрицы эмиссии B нужно задавать осмысленно, поскольку при обучении без учителя именно от них зависит, какому наблюдаемому состоянию модель будет пытаться придать какой смысл (наиболее вероятные скрытые состояния, его порождающие). Алгоритм обучения всегда сходится и при этом почти всегда - к точке локального максимума правдоподобия P{X|P}. Однако остаются вопросы, на которые нет универсального ответа: с какой скоростью сходится обучение и всегда ли такое обучение обеспечивает хорошее распознавание. Кроме того, считать по формулам (37)-(39) и рекурсивным формулам для вычисления a(...) и b(...) буквально так, как они написаны, нельзя:
Масштабирование при вычислениях.   Во всех вышеописанных вычислениях перемножались вероятности, т.е. числа не превышающие 1 и имеющие типичные значения обратные количеству состояний (скрытых или наблюдаемых), в количестве, пропорциональном длине последовательности. Для длинных (длины порядка 100 и более) последовательностей эти произведения меньше минимальных аппаратно реализуемых чисел типичных компьютеров. То есть нужно либо программно реализовывать неограниченную точность вычислений, что медленно, либо как-то масштабировать все промежуточные результаты, чтобы они не стремились к нулю. Счастливым исключением является алгоритм Витерби, в котором вероятности только перемножаются, но никогда не складываются, и можно вместо перемножения вероятностей заниматься сложением их логарифмов. Но при обучении модели масштабирование необходимо и методы масштабирования, почти не замедляющие обучение, известны (см. [27]).

2.1.2  Более общие скрытые марковские модели и объединение их с нейронными сетями и другими распознавателями

Выше была описана самая простая скрытая марковская модель. Для распознавания и моделирования более сложных последовательностей более сложных объектов применяются более сложные модели более общего вида. Обобщения можно условно подразделить на "научные" и "инженерные". В первом случае-таки строится честная вероятностная модель нескольких взаимодействующих явных или скрытых случайных процессов в разных пространствах. Во втором случае базовая модель преобразуется каким-либо способом, вообще говоря нарушающим вероятностные мотивировки и нормировки, но сохраняющим возможность применения быстрых алгоритмов распознавания и обучения, похожие на алгоритмы Витерби и Баума-Велша, хотя бы и без теоретического обоснования их; целью же преобразования является уменьшение размеров модели и, следовательно, надежда на ускорение ее обучения.
Приведем примеры и мотивации возможных "научных" обобщений скрытой марковской модели.
Непрерывное время
Для распознавания процессов реального времени (например, речи), можно было бы строить модель, содержащую вместо марковской цепи марковский процесс. Реально, поскольку наблюдаемый акустический сигнал обычно доступен в виде последовательности замеров с дискретным шагом по времени, строят модель на базе марковской цепи, но с контролируемым временем пребывания в каждом состоянии. Действительно, в чисто марковской цепи вероятность длительного пребывания в i-м состоянии управляется только одним диагональным элементом aii матрицы перехода. Вероятность оставаться в этом состоянии ровно k моментов времени равна aiik(1-aii), т.е. экспоненциально убывает по k, что совершенно не соответствует акустическим реалиям, когда шаг дискретизации сигнала намного меньше длительности типичной фонемы.
Непрерывное пространство скрытых состояний
Ограничимся примером задачи: по речевому сигналу восстановить не смысл речи, а движения губ (а также гортани, голосовых связок и т.п.) говорящего.
Непрерывное пространство наблюдаемых состояний
Это обобщение необходимо почти во всех приложениях, например, в распознавании рукописного текста. Даже чтобы сформулировать модельную задачу распознавания последовательности раздельно написанных символов мы предположили, что символы уже как-то классифицированы независимой распознающей системой. Гораздо лучшего распознавания можно добиться, привязав по системе распознавания символов к каждому скрытому состоянию марковской модели и обучая их совместно с моделью. Чаще всего марковские модели интегрируют таким образом друг с другом или с нейронными сетями.
В чисто вероятностных терминах это можно сформулировать так. Наблюдаемые состояния модели - это последовательность X случайных векторов X1,...,XT в некотором пространстве (как правило, в евклидовом пространстве Rd) с плотностью распределения
p(Xt |X1,...,Xt-1,Xt+1,...,Si1,...,Sit...) = p(Xt | Sit) = bit(Xt),
не зависящей от t, i1,...,it-1,it+1,.... Эти плотности, обозначенные bi(X), принадлежат какому-то заранее выбранному m-мерному параметризованному семейству, т.е. bi задается вещественными параметрами bi1,...,bim. Матрица параметров B=(bij) играет роль матрицы эмиссии в случае дискретного пространства состояний.
Пример. Пусть bi - мультимодальное гауссово распределение (5)
bi(X) = K
е
j=1 
 Pijpij(X) = K
е
j=1 
 Pij  1
(2psij)[ d/2]
 e-[(|X-Wij|2)/(2sij)].
Тогда для распознавания применим алгоритм Витерби с заменой bixt на bi(Xt) при вычислении dt(i,X), а для обучения такой модели на наборе последовательностей X ={X1,...,XN} применим алгоритм EM (Баума-Велша) в следующем виде. В формулах, определяющих at(i,X) и bt(i,X) нужно заменить bixt на bi(Xt). Тогда вектор начального распределения P и матрица перехода A пересчитываются по формулам (37) и (38), соответственно, а параметры распределений bi - по формулам (ср. с формулами (6)-(8))
P*lj
=
N
е
i=1 
 Ti
е
t=1 
 Gt(l,j,Xi)
N
е
i=1 
 Ti
е
t=1 
 gt(j,Xi)
W*lj
=
N
е
i=1 
 Ti
е
t=1 
 Gt(l,j,Xi) Xit
N
е
i=1 
 Ti
е
t=1 
 Gt(l,j,Xi)
s*lj
=
 1
d
N
е
i=1 
 Ti
е
t=1 
 Gt(l,j,Xi) |Xit-W*lj|2
N
е
i=1 
 Ti
е
t=1 
 Gt(l,j,Xi)
 ,
где
Gt(i,j,X) = gt(i,X)  pij(X)
K
е
j=1 
 pij(X)
 .
Доказательство получается естественным объединением доказательства, приведенного для обучения RBF-сетей , и опущенного доказательства предложения 23. Естественно, алгоритм и доказательство переносятся со сферических гауссианов на общие (9). Заметим, что получившуюся систему распознавания можно представить себе как результат объединения многих двухслойных RBF-сетей и замены их независимых вторых слоев единой скрытой марковской моделью.
Нестационарность
Упрощающее предположение о стационарности скрытой марковской цепи ничем не плохо для моделирования и распознавания воспроизводимых последовательностей, вроде речи или письменного текста, и совершенно не годится для моделирования уникальных последовательностей, например, извержений вулканов, численности саранчи или котировок биржевых акций. В этих случаях в модель нужно включить зависимость и скрытых состояний, и наблюдаемых, от тоже случайных, но наблюдаемых внешних параметров - землетрясений, урожая зерновых и политических новостей, соответственно.
Часто применяемыми "инженерными" обобщениями являются, например, привязка эмиссии к переходам между скрытыми состояниями, а не к самим состояниям, или принудительное связывание параметров модели, чаще всего просто приравнивание друг другу разных элементов матриц эмиссии и перехода. И то и другое позволяет уменьшить размер модели. Кроме того сегментатор, т.е. алгоритм, превращающий наблюдаемое неизвестно что в последовательность наблюдаемых из некоторого фиксированного пространства, в той или иной степени встраивают в саму модель. Например, для распознавания слитной речи обычно строят и обучают модели словарных слов, состящих из последовательностей фонем или чего-то вроде них, а затем из них строят и дообучают модель речи, состоящей из последовательности слов. В этой большой модели речи маленькие модели слов служат для сегментации на слова и для распознавания слов одновременно. Причем эти маленькие модели уже обучены заранее, и доучивать нужно только параметры переходов между словами.
Литература по построению и применению марковских моделей весьма обширна и, как правило, перегружена техническими подробностями (увы, необходимыми). Для начала можно порекомендовать две вводных статьи [27] и [28], содержащие также многочисленные ссылки.

2.2  Распознавание графов

В этом разделе частично описывается возможная схема распознавания агрегатов, неоднозначно представимых в виде последовательностей простых объектов, являющаяся одним из "инженерных" обобщений HMM (раздел 2.1). Можно считать, что это распознавание рукописного текста в режиме on-line, т.е. задаваемого траекториями (например, последовательностью пар координат, сообщаемых мышью или пером). Однако несмотря на то, что точки траекторий линейно упорядочены по времени, для распознавания удобнее использовать частичный и неоднозначно восстанавливаемый порядок "слева направо".
Для простоты мы ограничимся распознаванием отдельного слова, хотя эта схема легко обобщается и до распознавателя сплошного текста. Сначала предположим, что система содержит в себе распознаватель отдельных букв, и нужно только добавить к нему способ разрешения неоднозначностей и ошибок сегментации. Подобный подход применялся в компьютере Newton [5]. Потом, в разделе 2.2.2 перейдем к более интересной системе без отдельного распознавателя букв.

2.2.1  Распознавание слов с распознавателем букв

Траектории предварительно обрабатываются (сегментируются) и на вход системы распознавания подается граф сегментации S - ориентированный ациклический граф с единственной начальной вершиной (истоком) BS и единственной конечной (стоком) ES, каждое ребро [u,v] которого помечено сегментом (частью) траектории S[u,v], так что на любом ориентированном пути в графе эти сегменты попарно не пересекаются. Каждый путь от истока к стоку Sj=(vj0=BS,vj1,...,vjNj=ES) соответствует представлению траектории в виде последовательности (Sj1,...,SjNj), 1 Ј i Ј Nj сегментов Sji=S[vji-1,vji]. Что представляют из себя сегменты - двумерные картинки, кривые, последовательность особых точек картинки или что-нибудь еще - несущественно. Предполагается, что сегмент соответствует изображению буквы, и разные пути в графе сегментации - это разные способы разбить траекторию на части, предположительно изображающие буквы.
Вот упрощенный пример того, как может выглядеть граф сегментации. Предположим, что на траектории найдена последовательность предполагаемых границ между буквами (например, отрывов пера от бумаги, точек возврата и т.п.), что переупорядочивать куски траектории мы не собираемся, а в качестве сегментов берем участки траектории от одной границы до другой, не обязательно соседней. Тогда вершинами графа сегментации являются начало траектории, ее конец, и все допустимые межбуквенные границы, и граф - полный. Более реальный пример - когда в качестве сегментов допустимы только достаточно короткие участки траектории. А в совсем реальных примерах допустимо еще и переупорядочение участков траектории, и вершин в графе сегментации становится больше. Получается нечто, похожее на рис. 1, только без петель.
Распознаватель букв должен быть обучен тому, что на его вход может подаваться не только изображение буквы, но и любой мусор (результат неудачной сегментации). Ответом распознавателя траекторий должно быть самое похожее на хоть какой-нибудь путь Sj в графе сегментации словарное слово, т.е. последовательность букв C=(c1,...,cT), принадлежащая фиксированному множеству таких последовательностей D (словарю), и (а также, для удобства отладки, найденный путь Sj, т.е. лучше всего распознанный способ сегментации). Реальные распознаватели выдают не один самый лучший ответ, а несколько.
Оценка (не)похожести последовательности сегментов на слово.  
Каждая последовательность сегментов (т.е. путь Sj в графе сегментации S) может быть распознана как слово C, вообще говоря, разными способами. Конкретный способ распознавания R:S® C задается следующими данными: Дополнения до CR и SR образуют последовательности CўR из K- нераспознанных букв и SўR из Kў отбракованных сегментов, соответственно. Способами распознавания графа сегментации назовем все способы распознавания путей от его начальной вершины до конечной.
Замечание по форме. Если писать аккуратно, то почти все, что входит в формулы предыдущего и нескольких последующих абзацев, следует индексировать способом распознавания R. Но мы этот индекс пишем только иногда.
Штраф при этом способе распознавания можно оценить через оценки вероятностей Pk=P(cik|Sjmk) именно такого распознавания, вычисляемые распознавателем букв, и наборы нераспознанных букв Cў и отбракованных сегментов Sў. Сделаем (временно, до раздела 2.2.2) следующие упрощающие предположения: Тогда штраф можно определить удобным аддитивным способом
E(R) = - K
е
k=1 
 lnPk + l0 Kў+ K-
е
k=1 
 lcўik ,
где l0 и l1,...,lq - положительные коэффициенты, а положительный индекс cўik - номер буквы в алфавите. Можно определить и мультипликативную оценку

P(R) = e-E(R) = K
Х
k=1 
 Pk w0Kў K-
Х
k=1 
 wcўik ,
где wi=e-li. Она похожа на вероятность, но ее стыдно называть вероятностью пока не гарантировано, что сумма вероятностей всех исходов распознавания равна 1. Более того, при таком определении она и не будет равна 1,
При так определенных штрафе и "вероятности" (ох...) способа распознавания "вероятность" P(C|S) распознавания графа сегментации S как слова C по формуле полной вероятности естественно положить равной сумме "вероятностей" P(R) по всем способам распознавания R:
P(C|S) =
е
R:S® C 
 P(R)
а штраф за распознавание S как C определить как минимум:
E(S,C) =
min
R:S® C 
 E(R) .
Эти определения обладают двумя существенными недостатками: "вероятность" может превышать 1 и наиболее "вероятный" ответ распознавания может отличаться от минимально оштрафованного.
Правильную нормировку "вероятностей" можно обеспечить введением дополнительных коэффициентов, а несовпадение точки минимума суммы с точкой минимума минимума неустранимо. Однако обе эти проблемы возникают только при наличии нескольких способов хорошо распознать последовательность сегментов как одно и то же слово. Если наличие нескольких примерно одинаково хороших способов распознавания маловероятно, а при хорошей сегментации и больших штрафах за пропуски это так, то описываемая далее техника с большой вероятностью работоспособна.
Задачи распознавания и обучения.  
Теперь рассмотрим три задачи:
    Для данной входной последовательности S и словаря D найти наиболее вероятный (точнее, минимально оштрафованный) способ распознавания R. Или, в общем случае, несколько самых вероятных способов распознавания.
  1. Распознать входную последовательности S по словарю D, т.е. найти наиболее вероятное слово C и его вероятность P(C|S). Или, в общем случае, несколько самых вероятных слов.

  2. Обучить систему распознавания последовательностей по словарю D, т.е. подобрать ее параметры li (или, что то же самое, wi), чтобы обеспечить как можно лучшее распознавание.

Первая задача сводится к поиску кратчайшего пути или нескольких кратчайших путей в некотором графе, хорошо изучена и эффективно решается методом динамического программирования. Вторая задача красиво и чисто не решается, но сводится к первой и небольшому дополнительному счету в предположении, что сегментация не слишком плохая. А именно, сегментация должна быть столь хороша, чтобы способов распознавания с заметно ненулевой вероятностью было мало (например, не более 10). Тогда достаточно найти 10 наилучших способов распознавания и посчитать вероятности не более 10 распознаваемых такими способами слов. Третья задача похожа на обучение нейронных сетей и не то, чтобы раз и навсегда решена, но хорошо изучена.
В следующих пунктах решение этих задач описано подробнее.
Поиск наилучшего способа распознавания: поиск кратчайшего пути, динамическое программирование и вычисления на графах.  
Словарь D удобно представить в виде ориентированного ациклического графа с одной вершиной-истоком BD (begin) и одной вершиной-стоком ED (end), так что каждому ребру приписана одна буква, а каждому слову соответствует путь из BD в ED, такой что последовательность букв на ребрах вдоль пути образует это слово. Остальные вершины графа никакого специального смысла не имеют. Такой граф можно получить, например, следующим образом:
Напомним не вполне общеизвестное определение. Прямым произведением графов X и Y называется граф X×Y, вершинами которого являются пары (x,y) вершин X и Y, а ребрами [(x1,y1),(x2,y2)] - пары ребер ([x1,x2],[y1,y2]), соответственно.
Теперь по графам D и S построим граф GS® D распознавания графа S по словарю D следующим образом:
Каждому ребру e графа распознавания припишем неотрицательное число l(e), называемое его длиной, ценой, штрафом и т.п. Это число будет зависеть от пометок прообразов этого ребра в D и S. А именно,
Очевидно (убедитесь!), что каждый путь в графе GS® D от истока BG к стоку EG - это способ распознавания, а длина пути - это ошибка (штраф) этого способа распознавания. Тем самым, наилучший способ распознавания - это кратчайший путь в графе.
Быстрый поиск кратчайшего пути в графе - это стандартный пример применения метода динамического программирования, описанного в любом учебнике по теории и практике алгоритмов.
Упражнение. Прочтите (например, в [29]), вспомните или придумайте сами метод динамического программирования, т.е. быстрый алгоритм поиска кратчайшего пути от истока к стоку ориентированного ациклического графа. Время его работы пропорционально числу ребер графа, а требуемая память - числу вершин.
Другой способ поиска кратчайшего пути в любом (не обязательно ориентированном ациклическом) графе G реализуется параллельным вычислителем, похожим на нейронную сеть. В каждой вершине v графа G помещается "нейрон", вычисляющий вещественнозначную функцию (расстояние от начала пути)
f(v) =
min
[vў,v] 
 (f(vў)+l([vў,v]))
и дискретную функцию (по какому ребру входить)
n(v) = arg
min
[vў,v] 
 (f(vў)+l([vў,v])) .
Через [vў,v] обозначены входящие в вершину v ребра, а через l([vў,v]) - их длины. Если присвоить начальной вершине v0 значение f(v0)=0, а остальным вершинам f(v)=Ґ и запустить вычислитель работать, то за конечное число шагов он для каждой вершины вычислит расстояние до нее от начальной и кратчайший путь в нее (докажите!).
Этот вычислитель производит намного больше вычислений, чем нужно для поиска кратчайшего пути между двумя конкретными точками, так что на последовательной машине его реализовывать невыгодно.
Те же и нейронная сеть.  
Тот же самый параллельный вычислитель на графе распознавания GS®D, переделанный на вычисление функции
f(v) =
е
[vў,v] 
 w([vў,v])f(vў)
при w([vў,v])=e-l([vў,v]), v0=BG и f(v0)=1, вычисляет в точке EG число
FS® D(W) =
е
T 
е
(v0,...,vT)|v0=BG,vT=EG 
 T
Х
t=1 
 w([vt-1,vt]) ,
(40)
напоминающее вероятность того, что картинка, представленная графом сегментации S, является словом из словаря D (через W обозначен набор всех коэффициентов w([vў,v])).
Вероятностная аналогия вызвана похожестью вычислений на вычисления вероятностей траекторий в (нестационарной) скрытой марковской модели, если словарь считать пространством скрытых состояний, последовательность сегментов - последовательностью наблюдаемых состояний, положительный коэффициент w([vў,v])=w([yў,y]×[xў,x]) интерпретировать как произведение PyўyP{S[xў,x]|[yў,y]} вероятности перехода из вершины словаря yў в вершину y на вероятность порождения при этом переходе сегмента S[xў,x] (ср. с формулой (28)). Но ни требующиеся в марковской модели предположения о независимости различных случайных величин, ни даже вероятностные нормировки еv w([vў,v])=1, вообще говоря, не выполнены.
Ответ FS® D(W) этого вычислителя сам по себе довольно бесполезен. Зато вычислитель является нейронной сетью, и значит его известно как обучать, нужно только понять, чему.
Обучение распознавателя: градиентный спуск.  
Обучение такой нейронной сети довольно специфично. Во-первых, эта сеть построена для распознавания конкретного графа сегментации S, который не очень-то воспроизводима. Так что одну сеть обучать не на чем, а нужно обучать семейство сетей с общими весами W=(w0,...,wq). Во-вторых, эти веса в каждой сети появляются сразу на многих ребрах. Тем не менее градиентный спуск и метод обратного распространения для вычисления градиента. легко можно приспособить и для этой задачи.
Действительно, для каждого обучающего графа сегментации S такая нейронная сеть на графе GS® D, зависящая от параметра W, вычисляет функцию FS® D(W). Правильный ответ Y - это путь в словаре D от истока к стоку, т.е. специального вида подграф. Вложению Y М D соответствует подграф GS® Y М GS® D. Тогда за функционал ошибки можно взять, например,
E(FS® D(W),Y) = - ln  FS® Y(W)
FS® D(W)
  .
т.е. минус логарифм доли суммы "вероятностей" правильных способов распознавания графа сегментации S в сумме "вероятностей" всех способов его распознавания (40). Для применения метода градиентного спуска для минимизации средней ошибки нужно только уметь вычислять производные [(E(F(W,S),Y))/(W)], и совершенно несущественно, что для разных входных последовательностей S их вычисляют разные сети.
Для каждой входной последовательности S и каждого ребра e графа GS® D методом обратного распространения ошибки можно вычислить производную ошибки E(F(W,S),Y) по весу we этого ребра. Тогда производная [(E(F(W,S),Y))/(wi)] равняется сумме производных [(E(F(W,S),Y))/(we)] по всем ребрам e, которым приписан вес wi (формула дифференцирования сложной функции).
Такое обучение учит распознающую систему не совсем тому, чему нужно. А именно, вместо того, чтобы максимизировать оценку правильного способа распознавания, максимизируется сумма оценок всех способов распознавания правильного ответа, в том числе и сумасшедших. Но при дополнительных предположениях , на практике обычно выполняющихся, это одно и то же.

2.2.2  Распознавание слов без распознавателя букв

Рассмотрим систему распознавания слов, в которой после сегментации каждому ребру графа сегментации может быть приписано значение только из некоторого конечного и достаточно обозримого множества {s1,...,sM}. Например, сегмент может кодироваться не более чем тремя особенностями траектории не более чем 10 фиксированных типов. Или сегменты могут быть приближены вектор-многочленами фиксированной степени, а приближающие многочлены - отнормированы и векторно проквантованы с, скажем, 256 центрами. Тогда, во-первых, пропуску каждого сегмента можно приписать индивидуальную "вероятность" w01,...,w0M, а не просто w0, как раньше. Во-вторых, вероятности, wij=P(ci|sj) вычисляемые распознавателем букв на сегментах, можно затабулировать. И все эти параметры вида wij, общие для всех словарей и всех входных последовательностей и появляющиеся в качестве весов ребер графов распознавания, можно доучивать уже без распознавателя букв точно так же, как параметры w1,...,wq. Кстати, для единообразия обозначим "вероятность" wi пропуска i-й буквы ci через wi0 и будем формально интерпретировать ее как "вероятность" распознавания пустого сегмента s0 как ci.
Более того, можно, и на практике так и делают, еще увеличить количество обучаемых параметров. А именно, каждому ребру графа распознавания GS® D вида Итого получается порядка MC0(D)+(M+1)C1(D) параметров для обучения (через C0(D) и C1(D) обозначены числа вершин и ребер словаря D, соответственно).
Напомним, что граф распознавания GS® D - это прямое произведение графа сегментации S на граф словаря D, в которое добавлены ребра, соответствующие пропускам букв или сегментов . Спроектируем это произведение на второй сомножитель и возьмем объединение проекций по всем обучающим графам сегментации S. Получим универсальный граф GD распознавания графов сегментации по словарю D. Его вершинами являются вершины графа словаря D, а ребрами - петли, не более M штук в каждой вершине, и ребра D, размноженные в не более чем M+1 экземплярах каждое. Каждому ребру [v,u] графа GD приписана пара (ci,sj) и начальное значение веса wijvu. Теперь эти веса нужно обучить.
Важное практическое замечание. Поскольку при такой схеме распознавания не требуется предварительно обученный распознаватель букв, буквами и, соответственно, словарем может быть, вообще говоря, что угодно. В частности, в качестве букв можно брать коды сегментов, а в качестве словаря - набор образцов способов написания букв (в старом, человеческом смысле) и коротких буквосочетаний, сегментированных на "буквы" в новом смысле тем же самым сегментатором. То есть множество кодов сегментов {s1,...,sM} совпадает с "алфавитом" и при всех i ci=si. За начальные значения весов wijvu берут 1 при i=j и небольшие положительные числа (например, 0.1) при i № j и начинают обучение. В результате обучения получается система, распознающая буквы посредством анализа возможных разбиений их на кусочки (сегменты) и сравнения полученных последовательностей кусочков с эталонными. Пожалуй, это и есть наиболее распространенное применение описываемого метода распознавания графов в распознавании рукописного текста. Тем более, что для полноценного кодирования сегментов, соответствующих настоящим рукописным буквам, требуется несколько тысяч кодов (на два порядка больше, чем распознаваемых букв), а современных вычислительных возможностей хватает только на обучение вышеописанных распознавателей с числом сегментов порядка сотни.
Обучение распознавателя: алгоритм Баума.  
Существует хороший способ обучения таких распознавателей, совершенно не похожий на градиентный метод. Он основан на идеологии максимизации ожидания (EM) и (обобщенном) алгоритме Баума [26] и уже был описан как для нейронных RBF-сетей , так и для скрытых марковских моделей . Однако сейчас мы его будем применять в невероятностной ситуации: обучаемые параметры wijv распознавателя - неотрицательные числа, но никаким вероятностным нормировкам удовлетворять не обязаны. Поэтому не поленимся в очередной раз подробно описать его.
Сначала идеология. Алгоритм Баума состоит в итеративном пересчете параметров при многократном прогоне через распознаватель некоторого обучающего набора последовательностей сегментов для максимизации некоторой функции от пары: (параметры распознавателя, обучающий набор). В вероятностных ситуациях эта функция была правдоподобием, т.е. вероятностью "увидеть то, что увидели". В общем случае это некоторое усреднение оценки (40), вычисленной распознавателем на обучающих последовательностях. Алгоритм работает без учителя и почти всегда сходится к максимуму функции оценки, но только к локальному. Чтобы он сошелся к чему-то разумному нужно небессмысленным образом - и уже с учителем - выбрать начальные значения параметров.
А именно, как было сказано выше, за начальные значения параметров wijvu при i,j > 0 можно взять вероятности, wij=P(ci|sj) (не зависящие от вершин v и u словаря) вычисляемые заранее обученным распознавателем букв (вот кто работает учителем!), а за начальные значения параметров w0jvv и wi0vu, оценивающие пропуск сегмента или буквы, соответственно, - либо параметры w0 и wi обученной системы распознавания последовательностей с распознавателем букв (раздел 2.2.1), либо просто небольшие положительные числа (не нашлось подходящего учителя...).
Для каждой вершины v словаря обозначим через lv сумму
lv=
е
u;i,j і 0|i+j > 0 
 wijvu
(41)
значений параметров на всех выходящих из v ребрах. Возьмем некоторый обучающий набор (S1,...,SN) графов сегментации и будем пытаться максимизировать произведение оценок (40) при сохранении всех сумм (41). Заметим, что оценка (40) является многочленом с положительными (и даже целочисленными) коэффициентами от весов ребер графа GS® D, а значит и от весов ребер графа GD. То же верно и для произведения таких оценок. То есть мы хотим максимизировать некоторый многочлен большой степени с неотрицательными коэффициентами от большого числа неотрицательных переменных wijvu, удовлетворяющих линейным уравнениям (41), причем каждая переменная входит ровно в одно уравнение.
Чтобы не утонуть в громоздких обозначениях (сами переменные проиндексированы четырьмя индексами, а их еще в степень возводить...), сформулируем алгоритм Баума в абстрактных обозначениях, использующих мультииндексы. Пусть Мы начинаем с некоторой точки x0 в Rn+, удовлетворяющей системе m линейных уравнений

е
i|V(i)=j 
 xi = lj  ,         j=1,...,m  ,
(42)
и хотим искать точку локального максимума многочлена P, удовлетворяющую той же системе уравнений.
Чтобы спокойно делить и брать логарифмы исключим вырождения:
Поскольку многочлен P неотрицателен в положительном ортанте, максимизация P(x) равносильна минимизации E(x)=-lnP(x). Из-за выпуклости функции -ln(·)
E(x)-E(x0)
=
-ln  P(x)
P(x0)
 = -ln ж
и
е
d О D 
  adxd
P(x0)
 ц
ш 		= -ln ж
и
е
d О D 
 ж
и 		 adx0d
P(x0)
  xd
x0d
 ц
ш 		ц
ш
Ј

е
d О D 
 ж
и 		 adx0d
P(x0)
 ж
и 		-ln  xd
x0d
 ц
ш 		ц
ш
=

е
d О D 
 ж
и 		 adx0d
P(x0)
 (-lnxd) ц
ш 		-
е
d О D 
 ж
и 		 adx0d
P(x0)
 (-lnx0d) ц
ш
=
Q(x,x0)-Q(x0,x0)
и если удастся найти точку x, в которой
Q(x,x0) = -
е
d О D 
 ж
и 		 adx0d
P(x0)
 lnxd ц
ш 		< Q(x0,x0)  ,
то E(x) < E(x0), т.е. значение многочлена P удалось увеличить и этот шаг можно повторять снова. А если точка x0 является точкой глобального минимума функции Q(·,x0), то она является критической точкой P при условиях (42) (см. упражнение ниже ). При этом она может оказаться точкой локального максимума P, что и требуется, или другой критической точкой (минимумом или седлом), но тогда при почти любом ее возмущении она перестанет быть глобальным минимумом соответствующим образом возмущенной функции Q.
К счастью, точка минимума функции Q(·,x0) при условиях (42) единственна (а значит, это глобальный минимум) и находится явно. А именно, выписываем лагранжиан
LQ = -
е
d О D 
 ж
и 		 adx0d
P(x0)
 lnxd ц
ш 		- m
е
j=1 
 lj ж
и
е
i|V(i)=j 
 xi - lj ц
ш
и приравниваем нулю производные по всем xi:
0
=
 LQ
xi
 = -
е
d О D 
 ж
и 		 adx0d
P(x0)
  di
xi
 ц
ш 		-lV(i) = -  x0i
xi

е
d О D 
 ж
и 		adx0d  di
x0i
 ц
ш
P(x0)
 -lV(i)
=
-  x0i
xi

е
d О D 
  adx0d
x0i
P(x0)
 -lV(i) = -  x0i
xi
  i P(x0)
P(x0)
 -lV(i) = -  x0i
xi
 i(lnP(x0))-lV(i)  .
Значит
xilV(i) = -x0i i(lnP(x0))  ,
учитывая условия (42), получаем
ljlj =
е
i|V(i)=j 
 xilV(i) = -
е
i|V(i)=j 
 x0i i(lnP(x0))  ,
и подставляя последнее равенство в предпоследнее, получаем явную формулу для координат единственной критической точки функции Q(·,x0):
xi =  lV(i) x0i i(lnP(x0))

е
k|V(k)=V(i) 
 x0k k(lnP(x0))
  =  lV(i) x0i i P(x0)

е
k|V(k)=V(i) 
 x0k k P(x0)
 .
(43)
Поскольку при любом подходе к границе области определения (т.е. к координатным плоскостям) Q(·,x0) стремится к +Ґ, единственная критическая точка является точкой (глобального) минимума. Заданное этой формулой преобразование x0® x применяется итеративно, пока значение P(x) не перестанет возрастать. Это и есть алгоритм Баума.
Упражнение. Если точка x0 является точкой минимума функции Q, то она является критической точкой многочлена P при условиях (42).
Упражнение. Ограничения преобразования (43) на грани положительного ортанта склеиваются в общее непрерывное преобразование на его замыкании.
Для применения алгоритма Баума к обучению весов на ребрах распознавателя нужно только вернуться от компактных обозначений xi и P(x) для параметров и функции оценки к громоздким обозначениям wijvu и Хi=1N FSi® D(W), соответственно, и заметить, что поскольку каждая каждая оценка FSi® D(W) вычисляется нейронной сетью, производные ее логарифма по параметрам можно быстро вычислять методом обратного распространения , а логарифм произведения равен сумме логарифмов и производная суммы равна сумме производных.
Упражнение. Проверьте, что алгоритм Баума-Велша для дискретных HMM является частным случаем алгоритма Баума.
Алгоритм Баума можно обобщить на следующую ситуацию: коэффициентами ad многочлена вместо положительных чисел могут быть ограниченные положительные функции от других, отличных от xi, переменных, максимум которых как-то находится, например, произведение гауссианов. Тогда, грубо говоря, к преобразованию (43) добавляются преобразования для точной или итеративной максимизации коэффициентов. В качестве содержательного примера см. обучение HMM с непрерывным пространством состояний , а в качестве простого - обучение RBF-сетей .
Замечание. Алгоритм Баума, описанный выше для максимизации многочленов с неотрицательными коэффициентами при линейных ограничениях специального вида, можно перенести на еще более общие функции и ограничения. Сам простой и изящный вид шага итерации (43), где от максимизируемой функции P не требуется, якобы, ничего, кроме дифференцируемости и неотрицательности всех частных производных первого порядка, вызывает соблазн попробовать применить его к максимизации функций более общего вида. Но чтобы это применение было успешным, формула (43), вообще говоря, не годится. Например, для максимизации любого многочлена в любой компактной области можно сдвигом переменных загнать эту область в положительный ортант, добровольно согласиться соблюдать во время обучения условия (42) и прибавить к максимизируемому многочлену такой многочлен от этих условий, чтобы все коэффициенты суммы стали положительными. Прибавление многочлена от условий, естественно, не влияет на поиск точек экстремума при соблюдении этих условий, и такой многочлен всегда существует (например, R(x)=C(еj=1m lj+1)degP=C(еi=1nxi+1)degP при достаточно большом С). Получающиеся для шага итерации формулы имеют вид
xi = ci +  lV(i) (x0i-ci) (i P(x0)+CV(i))

е
k|V(k)=V(i) 
 (x0k-ci) (i P(x0)+CV(i))
с должным образом подобранными параметрами c1,...,cn,C1,...,Cm и несколько сложнее формулы для шага градиентного спуска. Почему-то они так нравятся распознающей общественности, что применяются, и иногда успешно, даже тогда, когда нет никакого разумного способа оценить значения параметров Сj, гарантирующие возрастание функции (не обязательно даже многочлена) P на каждом шаге, не говоря уже о сходимости к максимуму. См., например, [30].

References

[1]
Christopher M.Bishop, Neural Networks for Pattern Recognition, Oxford University Press, 1995.
[2]
W.S.McCulloch, W.H. Pitts, A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, 5, 115-133, 1943.
[3]
F.Rosenblatt, The perceptron: a probabilistic model for information storage and organization of the brain Psychological Review, 65:386-408, 1959.
[4]
А.Н.Колмогоров, О представлении непрерывной функции нескольких переменных суперпозицией непрерывных функций одной переменной и сложения, ДАН СССР, 114(5) стр. 953-956, 1957.
[5]
Larry S. Yaeger, Brandyn J. Webb, and Richard F. Lyon, Combining Neural Networks and Context-Driven Search for Online, Printed Handwriting Recognition in the NEWTON , AI Magazine, 19(1): Spring 1998, 73-90.
[6]
В.Н.Вапник, А.Я.Червоненкис, О равномерной сходимости относительных частот событий к их вероятностям, Теория вероятностей и приложения 16(2), 264-280, 1971.
[7]
D.E.Rummelhart, G.E.Hinton, R.J.Williams Learning Representations by Backpropagation Errors, Nature, 323:533-536, 1986.
Кроме научно-исследовательских трудов по нейронным сетям в последнее время появились десятки учебных пособий для студентов инженерных специальностей, например
[8]
Ф.Уоссермен, Нейрокомпьютерная техника (перевод на русский)
оригинал неизвестен, предположительно
P. D. Wasserman, Neural Computing: Theory and Practice, Van Nostrand Reinhold, New York, 1989
[9]
Teuvo Kohonen. Automatic formation of topological maps of patterns in a self-organizing system. In Erkki Oja and Olli Simula, editors, Proc. 2SCIA, Scand. Conf. on Image Analysis, pages 214-220, Helsinki, Finland, 1981. Suomen Hahmontunnistustutkimuksen Seura r. y.
[10]
Teuvo Kohonen. Self-Organizing Maps. Springer, Berlin, Heidelberg, 1995. (Second Extended Edition 1997, Third Edition 2002).
[11]
Samuel Kaski, Jari Kangas, Teuvo Kohonen, Bibliography of Self-Organizing Map (SOM) Papers: 1981-1997.
[12]
T.Hastie, P.Simard, E.Säckinger, Learning Prototype Models for Tangent Distance, Advances in Neural Information Processing Systems, vol. 7, MIT Press, pp. 999-1006, 1995.
[13]
В.Н.Вапник, А.Я.Червоненкис, Теория распознавания образов, М., Наука, 1974.
[14]
B.E.Boser, I.M.Guyon, V.N.Vapnik, A training algorithm for optimal margin classifiers, in Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, p. 144-152, ACM Press, 1992.
[15]
C.Cortes, V.Vapnik, Support Vector Networks, Machine Learning 20(3): 273-297, 1995.
[16]
J.Platt, Fast Training of Support Vector Machines using Sequential Minimal Optimization, 1998.
[17]
S.S.Keerthi, E.G.Gilbert Convergence of a Generalized SMO Algorithm for SVM Classifier Design, 2000.
[18]
J.Mercer, Functions of positive and negative type and their connection with the theory of integral equations, Philos. Trans. Roy. Soc. London, A 209:415-446, 1909.
[19]
N. Cristianini, J. Shawe-Taylor, An Introduction To Support Vector Machines (and other kernel-based learning methods), Cambridge University Press, 2000.
[20]
V.Vapnik, Statistical Learning Theory, Wiley, 1998.
[21]
V.Vapnik, An Overview of Statistical Learning Theory, IEEE Transactions on Neural Networks, 10(5):988-999, September 1999.
[22]
Christopher J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2): 121-167, 1998.
[23]
Alex J. Smola, Bernhard Schölkopf, A Tutorial on Support Vector Regression, NeuroCOLT2 Technical Report NC2-TR-1998-030, 1998.
[24]
C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines, IEEE Transactions on Neural Networks, 13(2):415-425, March 2002.
[25]
A.J.Viterbi, Error bounds for convolutional codes and an asymptotically optimal decoding algorithm Recognition, IEEE Trans. Informat. Theory, vol.IT-13, pp.260-269, 1967.
[26]
L.E.Baum, An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes, Inequalities, vol.3, pp.1-8, 1972.
[27]
Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of IEEE, vol.77, no.2, p.257-285, 1989.
[28]
Yoshua Bengio, Markovian Models for Sequential Data, Neural Computing Surveys, no.2, p.129-162, 1999.
[29]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1976.
перевод
А.Ахо, Дж.Хопкрофт, Дж.Ульман, Построение и анализ вычислительных алгоритмов, Мир, Москва, 1979.
[30]
D. Kanevsky, A generalization of the Baum algorithm to functions on non-linear manifolds, In: Proc. Internat. Conf. On Acoustics, Speech and Signal Processing, May 1995, Detroit, MI, Vol. 1., pp.473-476.
[31]
T. Hastie, R. Tibshirani, J. Friedman, The elements of statistical learning, Springer, 2001.
есть противозаконная электронная копия.

Footnotes:

1 Этот обзор, хотя и выставлен на публичное обозрение, является черновиком. Он постоянно меняется, в нем исправляются старые ошибки и появляются новые. Бдите!
2 Такая модель нейрона впервые была описана в работе [2] в 1943 году
3 За словом "хочется" скрыты теоремы, дающие оценки вероятностей ошибок и прочих свойств классификатора в зависимости от толщины полосы, см. историко-научное отступление
4При обсуждении распознавания одиночных объектов буквами X обозначались входы системы распознавания, а буквами Y - ее выходы. Мы сохраняем эти обозначения, хотя обычно в науке про марковские модели буквы X и Y обозначают входы и, соответственно, выходы некоторой части системы моделирования, т.е. наоборот.
5В практических реализациях эмиссию часто привязывают не к состоянию, а к переходу, и тогда дополнительное начальное состояние не нужно.

File translated from TEX by TTH, version 3.33.