Information Retrieval

Содержание

Наивный байесовский подход
Модель векторного пространства (VSM)
Метод PageRank – основа поисковой системы Google
Машины опорных векторов (SVM)

Наивный байесовский подход

Задача выделения спама

Предположим, что имеется два класса документов: S (спам) и ¬S (хорошие).

Пусть P(W_i|C) - условная вероятность того, что i-е слово документа D встречается в документе из класса C. Тогда вероятность документа D при условии класса C равна

P(D|C) = ∏_i P(W_i|C).

Вопрос, на который бы нам хотелось узнать ответ, это какова вероятность того, что документ D принадлежит классу C, т.е. P(C|D). Теорема Байеса говорит нам, что

P(C|D) = P(C) P(D|C) / P(D).

В конкретных терминах (когда C=S или C=¬S)

P(D|S) = ∏_i P(W_i|S),

P(D|¬S) = ∏_i P(W_i|¬S).

Используя теорему Байеса, можем записать

P(S|D) = P(S) ∏_i P(W_i|S) / P(D),

P(¬S|D) = P(¬S) ∏_i P(W_i|¬S) / P(D).

Разделив одно выражение на другое, получим

P(S|D)/P(¬S|D) = P(S)/P(¬S) ∏_i P(W_i|S)/P(W_i|¬S).

"Для красоты" возьмём логарифм от обеих частей равенства:

ln (P(S|D)/P(¬S|D)) = ln (P(S)/P(¬S)) + ∑_i ln (P(W_i|S)/P(W_i|¬S)).

Таким образом, можем найти ln (P(S|D)/P(¬S|D)). Если получилось, что ln (P(S|D)/P(¬S|D))>0, то это значит, что P(S|D)>P(¬S|D), то есть вероятность того, что данный документ - спам, больше вероятности того, что не спам. Так что если ln (P(S|D)/P(¬S|D))>0, то мы письмо отправляем в папку Spam, иначе - в Inbox.

Модель векторного пространства (VSM) и весовые функции

Вес TF-IDF

tf - term frequency (частота слова)
idf - inverse document frequency (обратная частота документа)

Предположим, нам дан набор документов {d_j} и набор слов {t_i}, встречающихся в документах из набора. Задача состоит в том, чтобы установить, насколько важно i-е слово для характеризации j-го документа.

Естественно предположить, что чем чаще встречается слово в документе, тем более оно важно для его характеризации. Поэтому введем величину tf_ij:

tf_ij = (сколько слов t_i в документе d_j) / (сколько слов t_i во всем документе d_j).

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

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

idf_i = log ( (сколько документов в наборе)/(сколько документов, содержащих i-е слово) ).

Чтобы избежать деления на ноль в случае, если конкретного слова в документе вообще нет, в знаменатале можно добавить 1.

idf_i = log ( (сколько документов в наборе)/(1 + сколько документов, содержащих i-е слово) ).

Итак, меру важности i-го слова в j-м документе можно определить как

tf-idf_ij = tf_ij • idf_i,

где tf_ij и idf_ij вычисляются по вышеприведённым формулам.

G. Salton, C. Buckley. (1988). Term-weighting approaches in automatic text retrieval. Information Processing & Management 24 (5): 513–523.

Модель векторного пространства (Vector Space Model)

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

Каждый документ представляется как вектор v_j. Каждая компонента такого вектора v_ij отвечает какому-то слову. Значение i-й компоненты j-го вектора берётся равной весу по TF-IDF для i-го слова и j-го документа: v_ij = tf-idf_ij. При этом, если слово не встречается в данном документе, то значение соответствующей компоненты вектора равно 0.

Угол между двумя векторами v1 и v2 будет являться мерой схожести данных документов: чем ближе угол к 0, тем более похожи документы; если угол равен π/2, то документы совершенно не похожи.

На практике легче вычислять не сам угол, а его косинус:

cos θ = v1 • v2 / ||v1|| ||v2||

(как обычно, скалярное произведение векторов делится на произведение их норм). Чем ближе cos θ к 1, тем более похожи документы; если cos θ = 0 то документы совершенно не похожи.

При интернет-поиске поисковый запрос представляется в виде вектора точно так же, как документ, а затем сравнивается со всеми документами, имеющимися в кэше. Посредством вычисления косинуса угла между запросом и документом осуществляется ранжирование по релевантности: чем больше косинус, тем выше в списке результатов поиска документ.

G. Salton, A. Wong, C. S. Yang (1975). A Vector Space Model for Automatic Indexing. Communications of the ACM, vol. 18, nr. 11, pages 613–620.

Весовые функции

В качестве меры важности слова не обязательно всегда использовать TF-IDF, то есть TF в качестве локальной весовой функции и IDF - в качестве глобальной. Можно использовать любую кобинацию из следующих (и многих других, на самом деле) локальных и глобальных весовых функций.

Локальные весовые функции:

Binary: l_ij = 1, если слово i есть в документе j, =0 в противном случае
"Вариация на тему" индикаторной (характеристической) функции

TermFrequency (TF): l_ij = tf_ij, сколько раз слово i встретилось в документе j
- Наша "родная" TF из TF-IDF. Чем чаще слово встречается в документе, тем лучше оно его характеризует.

Log: l_ij = log (tf_ij + 1).
Почти как TF, но чем больше данных слов мы уже встретили, тем менее ценно следующее встреченное слово для характеризации документа.

Augnorm: l_ij = (1 + tf_ij / MAX_i tf_ij ) / 2
"Aug" означает "augmented". Тоже "вариация на тему" TF.

Глобальные весовые функции

Binary: g_i = 1

Normal: g_i = 1 / (∑_j tf_ij^2)^(1/2)

Idf: g_i = log (n/df_i)
n - сколько документов в наборе,
df_i - сколько документов из набора содержит слово i.
Наша "родная" IDF из TF-IDF. Чем меньше документов, содержащих i-е слово, тем более это слово будет ценно для характеризации документа, в котором оно встретилось.

GfIdf: g_i = gf_i / df_i,
где gf_i - сколько раз слово i встречается во всём наборе документов
Похожа на Idf, только другой числитель и без логарифма. Знаменатель по-прежнему говорит, что чем меньше документов, тем более значимо слово. Числитель же говорит, что чем чаще слово встречается во ВСЕХ документах, тем оно значимее.

Entropy: g_i = 1 + ∑_j (p_ij log p_ij / log n), где p_ij = tf_ij / gf_i.

Используется формула для «общевселенского» понятия энтропии - ожидаемого количества информации, необходимого для полного определения состояния системы:

S = - k ∑_j P_j ln P_j,

где P_j - вероятности пребывания рассматриваемой системы в различных состояниях при условии, что мы имеем полную информацию о системе. В качестве этих вероятностей состояний системы у нас выступают tf_ij / gf_i, представляющая собой по сути условную вероятность j-го документа при i-м слове.

Недостатки VSM

Латентный семантический анализ

Пусть X=[x_ij], i=1 ,.., m, j=1, ..., n - матрица с m строк и n столбцов, у которой (i,j)-й элемент описывает встречаемость слова i в документе j (например, вес TF-IDF).

Строкой матрицы X будет вектор, соответствующий слову и показывающий связь данного слова с каждым документом: t_i^T = [x_i1, ..., x_in] (верхний индекс T означает транспозицию).

Столбцом матрицы будет вектор, соответствующий документу и показывающий связь данного документа с каждым словом: d_j^T = [x_1j, ..., x_mj].

Скалярное произведение между двумя вектор-словами t_i^T t_p даёт «корреляцию» (similar pattern of occurance) между словами по всем документам. Матричное произведение X X^T содержит все эти скалярные произведения. Элемент (i, p), равный элементу (p, i), содержит скалярное произведение t_i^T t_p = t_p^T t_i.

Аналогично, скалярное произведение между двумя вектор-документами d_j^T d_q даёт «корреляцию» между документами по всем словам, а матричное произведение X^T X содержит все такие скалярные произведения.

Теперь предположим, что существует разложение матрицы X такое, что U и V - ортогональные матрицы, а Σ - диагональная матрица. Это называется сингулярное разложение матрицы (SVD): X = U Σ V^T, Σ – диагональная матрица, U, V – ортогональные матрицы (U^T U = U U^T = E),

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

X X^T = (U Σ V^T) (U Σ V^T)^T = U Σ V^T V Σ^T U^T = U Σ Σ^T U^T,

X^T X = (U Σ V^T)^T (U Σ V^T) = V Σ^T U^T U Σ V^T = V Σ^T Σ V^T.

Так как матрицы Σ Σ^T и Σ^T Σ диагональные, все собственные векторы матрицы X X^T должны содержаться в матрице U, а все собственные векторы матрицы X^T X должны содержаться в матрице V. Оба произведения имеют одинаковые ненулевые собственные значения, задаваемые ненулевыми значениями Σ Σ^T или, что то же самое, ненулевыми значениями Σ^T Σ. Таким образом, разложение выглядит так:

║ x_11 ... x_1n ║   ║┌   ┐   ┌   ┐║   ║σ_1 ...  0 ║   ║[  v_1  ]║ 
║  .        .   ║   ║│   │   │   │║   ║ . .     . ║   ║    .    ║ 
║  .        .   ║ = ║│u_1│...│u_l│║ • ║ .   .   . ║ • ║    .    ║ 
║  .        .   ║   ║│   │   │   │║   ║ .     . . ║   ║    .    ║ 
║ x_m1 ... x_mn ║   ║└   ┘   └   ┘║   ║ 0  ... σ_l║   ║[  v_l  ]║ 

Значения σ_1, ... σ_l называются сингулярными значениями, а u_1, ..., u_l и v_1, ..., v_l - левыми и правыми сингулярными векторами. Заметим, что единственная часть матрицы U, которая влияет на t_i - это i-я строка. Назовём этот вектор-строку t^_i. Аналогично, единственная часть V^T, которая влияет на d_j - это j-й столбец, d^_j. Это не собственные векторы, но векторы, зависимые от всех собственных векторов.

Оказывается, что когда мы берём k наибольших сингулярных значений и их соответствующие векторы из U и V, мы получаем матрицу ранга k, аппроксимирующую X с наименьшей ошибкой (в смысле нормы Фробениуса). Замечательное свойство этой матрицы также в том, что она переводит векторы-слова и векторы-документы в понятийное пространство. Таким образом, вектор t^_i имеет k элементов, каждый из которых даёт встречаемость i-го слова в одном из k понятий. Аналогично вектор d^_j дает связь между j-м документом и каждым понятием. Запишем эту аппроксимацию как

X_k = U_k Σ_k V_k^T.

Альтернативный вариант записи:

X~ = U Σ~ V,

где Σ~ содержит лишь k наибольших значений матрицы Σ, остальные – нули.

Сингулярное разложение единственно с точностью до перестановки строк, столбцов или знаков. Положим, что все Σ положительны (и упорядочены по убыванию?).

Что значит «с наименьшей ошибкой»? Норма Фробениуса (Гильберта-Шмидта):

Теорема Экарта-Янга (Eckart-Young, 1936). Если мы хотим аппроксимировать матрицы M матрицей M~ ранга r в том смысле, что мы хотим минимизировать норму Фробениуса для разности между M и M~ при условии rank M~ = r, оказывается, что решение дается сингулярным разложением матрицы M. (Доказывается несложно, но я не буду здесь писать доказательство.)

Теперь мы можем следующее:
- Узнать близость документов j и q в понятийном пространстве путём сравнения векторов d^_j и d^_q (как было Vector Space Model). Это дает нам кластеризацию документов.
- Сравнить слова i и p, сравнив векторы t^_i и t^_p, что дает кластеризацию слов в понятийном пространстве.
- Имея поисковый запрос, рассмотреть его как мини-документ и сравнить его с документами в понятийном пространстве. При этом d^_j для запроса легко вычислить по формуле d^_j = Σ_k^(-1) U_k^T d_j.

Метод PageRank – основа поисковой системы Google

Описание метода PageRank

Метод PageRank позволяет ранжировать web-страницы по важности. Полагается, что страница важна, если на нее ссылаются другие важные страницы.

Связи между страницами представляются в виде ориентированного графа (V, E). В качестве вершин выступают сами страницы, в качестве ребер - ссылки с одной страницы на другую.

Для вершины v графа (V, E) определим

d⁺(v) = число ребер, исходящих из v,

d^-(v) = число ребер, входящих в v.

Требуется, чтобы ранжирующий вектор r отображал r: V → R₊ так, что

r(v) = ∑_{(u, v)ϵE} r(u) / d⁺(u).

Пусть r нормированный:

∑_v r(v) = 1.

Матрицей смежности графа называется такая матрица A, что

A_{u, v} = 1, если (u, v) ϵ E,
A_{u, v} = 0, в противном случае.

Определим матрицу D как

D_{u, v} = d⁺(u), если u = v,
D_{u, v} = 0, в противном случае

и матрицу M как

M = D^-1 A.

Тогда PageRank-уравнение запишется в виде

r = r M.

Другими словами, r - левый собственный вектор матрицы M, соответствующий собственному значению 1.

Чтобы M была корректно определена, необходимо, чтобы d⁺(v) > 0 для всех v.

Если для некоторых v d⁺(v) = 0, то матрица M определяется как

M_{u, v} = (1 - α) / d⁺(u) + α / n, если (u, v) ϵ E
M_{u, v} = α / n, в противном случае,

что может быть представлено как

M = (1 - α) D^-1 A + α / n J,

где J - матрица, состоящая из всех 1. По утверждению С. Брина и Л. Пейджа используется α = 0.15.

Последнее допускает следующую вероятностную трактовку. Представим, что обезьяна бродит по Сети и на каждом шаге она может решить либо перейти по произвольной ссылке, имеющейся на странице (с вероятностью 1 - α), либо посетить совершенно произвольное место в Сети (с вероятностью α). Предположим, что обезьяна бродит по Сети очень долго, и в конце концов получаем одно распределение вероятностей нахождения обезьяны на каждой странице. Так как

r(v) = ∑_u r(u) M_{u, v},

вероятность нахождения обезьяны на странице v равна r(v).

Степенной метод

Для численного решения уравнения

r = r M

применяется следующий итерационный метод, известный как степенной метод.

Берется некоторое начальное приближение r⁽⁰⁾, и каждая следующая итерация вычисляется по формуле

r⁽ⁱ⁺¹⁾ = r⁽ⁱ⁾ M,

∑_v r(v) = 1.

Связь с цепями Маркова

Цепью Маркова называется последовательность случайных величин X₁, ..., X_n, ..., для которых

P(X_n+1 = i_n+1 | X_n = i_n, X_n-1 = i_n-1, ..., X₀ = i₀) = P(X_n+1 = i_n+1 | X_n = i_n):

условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний.

Цепь Маркова называется стационарной, если переходные вероятности P(X_n+1 = i_n+1 | X_n = i_n) не зависят от n.

Матрицей переходных вероятностей называется матрица P, для которой

P_ij = P(X_n+1 = j | X_n = i).

P является стохастической матрицей, то есть ∑_j P_ij = 1.

Состояние j называется достижимым из состояния i, если существует такое n = n(i, j), что

p_ij⁽ⁿ⁾ = P(X_n = j | X₀ = i) > 0.

Состояния i и j называются сообщающимися, если i достижимо из j и j достижимо из i. Свойство сообщаемости порождает на пространстве состояний отношение эквивалентности. Порождаемые классы эквивалентности называются неразложимыми классами. Если цепь Маркова такова, что ее состояния образуют лишь один неразложимый класс, то она называется неразложимой.

Периодом состояния j цепи Маркова называется число

d(i) = gcd (n ϵ N: P(X_n = i | X₀ = i) > 0),

где gcd обозначает наибольший общий делитель.

Если d(j) > 1, то состояние j называется периодическим. Если d(j) = 1, то состояние j называется апериодическим. Периоды сообщающихся состояний совпадают. Таким образом, период любого неразложимого класса цепи Маркова определен и равен периоду любого своего представителя. Соответственно, классы делятся на периодические и апериодические. Если цепь Маркова неразложима, то периоды всех ее состояний совпадают и принимаемое ими общее значение называется периодом цепи. Цепь называется периодической, если ее период больше единицы, и апериодической в обратном случае.

Стационарным распределением π называется вектор-строка с ∑_i π_i = 1, удовлетворяющая уравнению

π = π P.

Таким образом, ранжирующий вектор r алгорифма PageRank является стационарным распределением цепи Маркова с матрицей переходных вероятностей M.

Стационарное распределение существует всегда, но в общем случае необязательно единственно. Единственность обеспечивается, если матрица P неразложима и апериодична.

Литература

Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30: 107{6), 117, 1998. Proceedings of the Seventh International World Wide Web Conference.

Ширяев А.Н. Вероятность. — М.: Наука, 1980.

Машины опорных векторов (SVM)

Используемые сведения из курса методов оптимизации

Задача нелинейной оптимизации

Прямая задача:

f(x) → min_x,
g_i(x) ≤ 0, i = 1, ..., m,

Функция Лагранжа:

L(x, λ) = f(x) + ∑_i^m₌₁ λ_i g_i(x).

Условия Каруша-Куна-Таккера (необходимое условие экстремума): Пусть функции f, g_i, i = 1, ..., m, непрерывно дифференцируемы в точке x^*. Если x^* - локальный минимум, то найдутся такие λ_i, i = 1, ..., m, что

1. grad L(x^*, λ) = 0 (условие стационарности),
2. λ_i g_i(x^*) = 0, i = 1, ..., m (условие дополняющей нежесткости),
3. g_i(x^*) ≤ 0, i = 1, ..., m (условие допустимости),
4. λ_i ≥ 0, i = 1, ..., m (условие неотрицательности).

Двойственная задача:

r(λ) → max_λ,
λ_i ≥ 0, i = 1, ..., m,

Двойственная задача к двойственной задаче - прямая задача. Решение двойственной задачи является решением прямой задачи и наоборот.

Задача квадратичного программирования

Прямая задача:

f(x) = ¹/₂ x^T Q x → min_x,
A x ≤ b,

где x, b ϵ Rⁿ, Q - симметричная n x n матрица (частный случай задачи нелинейной оптимизации).

Функция Лагранжа:

L(x, λ) = ¹/₂ x^T Q x + λ^T (A x - b).

Двойственная задача:

- ¹/₂ λ^T A Q^-1 A^T λ - b^T λ → max_λ
λ ≥ 0.

Двойственная задача также является задачей квадратичного программирования.

Полные формулировки и доказательства см. в доступных учебных и справочных материалах по методам оптимизации.

Случай линейной разделимости

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

D = {(x_i, y_i) | y_i ϵ {-1, 1} } _i^m₌₁,

где y_i - индикатор класса, к которому относится точка x_i,
x_i - d-мерный вектор.

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

Задача состоит в отыскании гиперплоскости, отделяющей точки из класса y_i = 1 от точек из класса y_i = -1. При этом расстояние от этой гиперплоскости до ближайшей точки из обучающего набора с каждой стороны гиперплоскости должно быть максимальным.

Уравнение гиперплоскости:

w ∙ x - b = 0,

где w - нормальный (перпендикулярный) вектор к гиперплоскости. При этом величина ^b/_||w|| определяет расстояние от начала координат до гиперплоскости.

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

w ∙ x - b = 1,
w ∙ x - b = -1.

Расстояния между этими гиперплоскостями равно ²/_||w||. Таким образом, следует минимизировать ||w||. При этом необходимо, чтобы точки из обучающего набора оставались вне области, ограниченной гиперплоскостями:

w ∙ x_i - b ≥ 1

для x_i из первого класса,

w ∙ x_i - b ≤ -1

для x_i из второго класса.

Это можно записать в виде

y_i (w ∙ x_i - b) ≥ 1, i = 1, ..., m.

Таким образом, получаем задачу оптимизации:

||w|| → min_{(w, b)}
- (y_i (w ∙ x_i - b) - 1) ≤ 0, i = 1, ..., m.

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

¹/₂ ||w||² → min_{(w, b)}
- (y_i (w ∙ x_i - b) - 1) ≤ 0, i = 1, ..., m.

Это задача квадратичного программирования, которая может быть решена стандартными методами квадратичного программирования. Однако использование для решения метода Лагранжа облегчает обобщение задачи на случай линейной неразделимости (см. ниже).

Функция Лагранжа для этой задачи:

L_P(w, b, λ) = f(x) + ∑_i^m₌₁ λ_i g_i(x) w ∙ w / 2 - ∑_i^m₌₁ λ_i y_i w ∙ x_i + ∑_i^m₌₁ λ_i y_i b + ∑_i^m₌₁ λ_i.

Условия Каруша-Куна-Таккера:

1. стационарности:

∂L_P / ∂w = w - ∑_i^m₌₁ λ_i y_i x_i = 0,

где ∂L_P / ∂w = (∂L_P / ∂w₁, ..., ∂L_P / ∂w_d),

∂L_P / ∂b = ∑_i^m₌₁ λ_i y_i = 0,

∂L_P / ∂ λ_i = g_i(x) = 0.

2. дополняющей нежесткости:

λ_i g_i = - λ_i (y_i (w ∙ x_i - b) - 1) = 0, i = 1, ..., m,

3. допустимости:

- y_i (w ∙ x_i - b) + 1 ≤ 0, i = 1, ..., m,

4. неотрицательности:

λ_i ≥ 0, i = 1, ..., m.

Стационарная точка функции Лагранжа определяет решение задачи оптимизации. Подстановка уравнений из условий стационарности в правую часть функции Лагранжа сводит ее к двойственной функции с λ_i в качестве двойственных переменных. Таким образом, двойственная задача запишется как

L_D = - ¹/₂ ∑_i^m₌₁ ∑_j^m₌₁ λ_i λ_j y_i y_j x_i ∙ x_j + ∑_i^m₌₁ λ_i → max_λ
∑_i^m₌₁ λ_i y_i = 0, i = 1, ..., m,
λ_i ≥ 0, i = 1, ..., m.

Мы можем найти все λ, решая эту задачу методами квадратичного программирования. Затем из первого уравнения из условий стационарности мы можем найти w:

w = ∑_i^m₌₁ λ_i y_i x_i.

В точке, являющейся опорным вектором, λ_i > 0; в точке, не являющейся опорным вектором, λ_i = 0.

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

- λ_i (y_i (w ∙ x_i - b) - 1) = 0, i = 1, ..., m,

Класс новой точки x определяется как

class (x) = sign (w ∙ x - b).

Случай линейной неразделимости

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

- y_i (w ∙ x_i - b) - 1 ≥ 0.

Тогда задача формулируется следующим образом:

f(w, ξ) = ¹/₂ ||w||² + C ∑_i^m₌₁ ξ_i
y_i (w ∙ x_i - b) ≥ 1 - ξ_i, i = 1, ..., m,
ξ_i ≥ 0, i = 1, ..., m,

где C задается пользователем. Можно представлять себе C как плату за ошибки. Малая C максимизирует margin, и гиперплоскость менее чувствительна к outliers в обучающем наборе. Большая C минимизирует число ошибочно классифицированных точек.

Функция Лагранжа:

L_P = ¹/₂ ||w||² + C ∑_i^m₌₁ ξ_i - ∑_i^m₌₁ λ_i (y_i (w ∙ x_i - b) - 1 + ξ_i) - ∑_i^m₌₁ μ_i ξ_i.

Условия Каруша-Куна-Таккера:

1. стационарности:

∂L_P / ∂w = w - ∑_i^m₌₁ λ_i y_i x_i = 0,

где ∂L_P / ∂w = (∂L_P / ∂w₁, ..., ∂L_P / ∂w_d),

∂L_P / ∂b = ∑_i^m₌₁ λ_i y_i = 0,

∂L_P / ∂ b = ∑_i^m₌₁ λ_i y_i = 0,

∂L_P / ∂ξ_i = C - λ_i - μ_i = 0.

∂L_P / ∂λ_i = - (y_i (w ∙ x_i - b) - 1 + ξ_i) = 0.

2. дополняющей нежесткости:

λ_i g_i = - λ_i (y_i (w ∙ x_i - b) - 1 + ξ_i) = 0, i = 1, ..., m,

3. допустимости:

- (y_i (w ∙ x_i - b) - 1 + ξ_i) ≤ 0, i = 1, ..., m,

4. неотрицательности:

ξ_i ≥ 0, i = 1, ..., m,

λ_i ≥ 0, i = 1, ..., m,

μ_i ≥ 0, i = 1, ..., m.

μ_i ξ_i = 0, i = 1, ..., m.

Подставляя первые два выражения из условий стационарности в правую часть функции Лагранжа, получаем следующую двойственную задачу:

L_D = - ¹/₂ ∑_i^m₌₁ ∑_j^m₌₁ λ_i λ_j y_i y_j x_i ∙ x_j + ∑_i^m₌₁ λ_i → max_λ
∑_i^m₌₁ λ_i y_i = 0, i = 1, ..., m,
0 ≤ λ_i ≤ C, i = 1, ..., m.

Вектор w можно найти из первого уравнения из условий стационарности:

w = ∑_i^m₌₁ λ_i y_i x_i.

Константа b может быть найдена усреднением по всем b, соответствующим элементам обучающего набора, которые вычисляются посредством следующих двух условий Каруша-Куна-Таккера:

λ_i (y_i (w ∙ x_i - b) - 1 + ξ_i) = 0,
(C - λ_i) ξ_i = 0.

Последние уравнения также показывают, что ξ_i = 0, если λ_i < C. Следовательно, b может быть усреднена лишь по тем элементам обучающего набора, для которых 0 ≤ λ_i < C.

Если λ_i < C, то ξ_i = 0. Опорные векторы лежат на расстоянии ¹/_||w|| от разделяющей гиперплоскости. Когда λ_i = C, опорные векторы - это ошибочно классифицированные точки, если ξ_i > 1. Если 0 < ξ_i ≤ 1, то опорные векторы классифицированы верно, но лежат ближе, чем на расстоянии ¹/_||w|| от гиперплоскости.

Нелинейная классификация

Для обобщения метода опорных векторов на случай нелинейной классификации используется kernel trick ("фокус с ядром"): везде в вышеизложенных рассуждениях вместо скалярного произведения используется функция-ядро:

x ∙ x' → k(x, x').

Некоторые распространенные ядра:

k(x, x') = (x ∙ x')^d,

k(x, x') = (x ∙ x' + 1)^d,

k(x, x') = exp (- γ ||x - x'||²), γ>0,

k(x, x') = exp (- ||x - x'||² / (2 σ²) ).

Численные методы

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

Но наиболее эффективный алгоритм отыскания решения задач квадратичного программирования, возникающих в методе опорных векторов, был разработан Джоном Платтом. С алгоритмом можно ознакомиться на личной странице автора http://research.microsoft.com/~jplatt/ или в магистрской диссертации Дж. Мака.

Литература

Вапник В.Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.

Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, New York, 1995.

Аоки М. Введение в методы оптимизации. — М.: Наука, 1977.

Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. — М.: ФИЗМАТЛИТ, 2008.

Platt J. Fast training of SVMs using Sequential Minimal Optimization. Advances in Kernel Methods Support Vector Machine, pp. 185-208, MIT Press, Cambridge, 1999.

Mak G. The Implementation of Support Vector Machines Using the Sequential Minimal Optimization Algorithm (Master's Thesis).