Линейная регрессия на пальцах в распознавании

В задаче распознавания ключевую роль играет выделение значимых параметров объектов и оценка их численных значений. Тем не менее, даже получив хорошие численные данные, нужно суметь правильно ими воспользоваться. Иногда кажется, что дальнейшее решение задачи тривиальное, и хочется «из общих соображений» получить из численных данных результат распознавания. Но результат в этом случае получается далеко не оптимальный. В этой статье я хочу на примере задачи распознавания показать, как можно легко применить простейшие математические модели и за счет этого существенно улучшить результаты.

О задаче распознавания образов

Задача распознавания образов – это задача отнесения объекта к определенному классу. Для определения принадлежности классу используют некоторый набор параметров объекта. Например, можно распознавать людей по некоторым их параметрам: расстояние между глазами, цвет кожи, длина носа, рисунок радужки, характерная частота голоса, количество пальцев и т. д. Эти параметры можно представить в виде числового вектора фиксированной размерности (для числовых параметров это тривиально, для цвета/рисунка радужки/изображения лица и пр. надо еще придумать, как это сделать). То есть у нас есть некоторое количество классов X₁, X₂, … X_N, есть опытный образец, описываемый набором значений параметров , и мы хотим про него сказать, не относится ли он к одному из этих классов. Обычно классы представлены в виде нескольких образцов этого класса: например визуальные изображения объекта с разных ракурсов, различные измерения параметров, различные экземпляры фотографий радужки. Тогда простейший метод распознавания – сравнить поступивший объект с каждым образцом каждого класса, и по расстоянию до ближайшего объекта принять решение, это он или не он.

На первый взгляд задача звучит как задача классификации с неопределенно большим количеством классов: каждый тип объекта – отдельный класс, и надо сравнивать новый объект с каждым классом. Это довольно сложная задача, особенно когда у нас нефиксированное число классов: например, при распознавании людей может пройти человек, которого нет в базе – то есть человек другого класса. Но на самом деле мы вычисляем разницу dx между исследуемым объектом и образцом класса и принимаем решение, один и тот же это объект или разные. Например, если мы хотим распознавать человека по отпечатку пальцев, то мы полученный отпечаток сравниваем со всеми отпечатками из некоторой базы данных, вычисляем меру похожести между каждой парой отпечатков, и по этой мере похожести для самого похожего отпечатка выносим решение о том, что это тот же человек, если отпечатки достаточно похожи, либо что этого человека нет в нашей базе, если самый похожий отпечаток все равно не похож. То есть наш классификатор принимает на вход не параметры объекта x, а разницу между параметрами двух объектов dx = x – xⁱ (лучше даже взять модуль разности каждой компоненты, чтобы был не важен порядок вычитания), и по этим параметрам выдает характеристику (меру похожести), позволяющую принять решение: это одинаковые объекты или разные. Это можно рассматривать как задачу классификации с двумя классами: «одинаковые пары объектов» и «разные пары объектов». Причем класс «одинаковые пары» будет кучковаться ближе к нулю, а разные – наоборот будут где-то в стороне. Традиционно классификатор должен выдавать численную меру похожести (например от 0 до 1), которая чем больше, тем больше вероятность того, что это разные объекты; далее в зависимости от требований системы определяется пороговое значение для принятия решения, от которого зависят ошибки первого и второго рода.

Как не надо делать

Изначально, глядя на эти параметры, хочется просто найти норму вектора разности – корень из суммы квадратов компонент: . То есть как евклидово расстояние между образцами, если параметры считать координатами. Чем оно меньше, тем более «похожи» эти два объекта, то есть больше шанс, что они одинаковые. Это правильно, но при ряде ограничений: все параметры должны быть некоррелированы (взаимно независимы), у них должно быть одинаковое распределение (они должны быть равнозначны). Обычно это не так (например, рост и вес не стоит считать независимыми, а форма носа — куда более надежная характеристика, чем форма рта или длина волос). Тогда давайте разным компонентам выберем разные весовые коэффициенты, чтобы усилить более важные параметры и ослабить менее важные: .

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

Итак, мы хотим определить весовые коэффициенты. Для этого мы пройдемся по всем парам объектов из тестовой выборки и для каждой компоненты посчитаем ее среднее значение и дисперсию для одинаковых пар и для разных пар. А вот что дальше с этим делать – не очень понятно. Весовые коэффициенты должны быть тем больше, чем больше расстояние между средними значениями (), при этом еще они должны быть меньше, если дисперсия очень большая, то есть компоненты скорее шумовые, чем информативные. Всякие мои попытки оптимизации на этом этапе приводили к тому, что надо брать одну самую важную компоненту, а остальные не рассматривать, что очевидно не даст хорошего результата. В итоге я забил на дисперсии и просто считал для каждой компоненты, показатель степени k подбирался опытным путем, и для разных наборов параметров лучший показатель мог получиться равным как 0.01, так и 4.

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

Линейная регрессия

Правильный подход – это математически формализовать задачу и найти оптимальное в каком-то смысле решение. Как известно, простейшая функция – линейная функция, так что мы будем искать функцию вида (да, с виду это очень похоже на те самые весовые коэффициенты). Нахождение такой функции и называется линейной регрессией. Коэфициенты b₀, b₁,… b_n подберем таким образом, чтобы эта функция по МНК наиболее хорошо подходила под правильные значения для тестовой выборки. А правильные значения – это Y=0 для одинаковых объектов и Y=1 для разных. Интуитивно кажется, что величина b₀ должна быть равной 0, ибо на нулевом векторе разницы у нас гарантированно одинаковые объекты. Но мы не будем играть в угадайку и вычислим b₀ по-честному. Таким образом, мы по сути определяем направление в n-мерном пространстве, по которому одинаковые и разные пары будут отличаться наиболее сильно.

(источник) Сумма квадратов ошибок будет определяться как . Здесь и далее M — количество объектов тестовой выборки, верхний индекс обозначает номер объекта в выборке, нижний индекс — номер компоненты объекта. Минимизируется эта ошибка в точке, в которой производная по каждой компоненте равна нулю. Элементарная математика приводит нас к системе Ab=f, где A – матрица (n+1)*(n+1), , , , i, k = 1..n. , . Вычисляем элементы матрицы по тестовой выборке, решаем систему, получаем коэффициенты, строим функцию.

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

Мой опыт показывает, что такая функция различает одинаковые и разные пары объектов куда лучше, чем наугад подобранные весовые коэффициенты. Что не удивительно, ибо эта функция оптимальна в некотором смысле.

Проблемы?

Какие могут возникнуть проблемы?

Во-первых, для определения коэффициентов функции n параметров надо вычислить матрицу размером (n+1)*(n+1), то есть все точки изображения 256х256 представить в виде отдельных параметров уже не получится, никакой памяти не хватит. Тут можно прибегнуть к традиционным методам понижения размерности, в частности PCA. Либо можно выбрать некоторое количество наиболее значимых параметров (например, отсеять те, у которых среднее значение для разных не превосходит среднее значение для одинаковых, или слишком большая дисперсия). А так как статью полностью никто не читает, то я предлагаю выбирать параметры, у которых самые красивые номера, например, которые оканчиваются на семерку.

Другая проблема – если линейной аппроксимации недостаточно, и функция слишком плохо разделяет классы. Тогда можно применять более сложные классификаторы – adaboost, SVM + kernel trick (статья на тему) и т. д.

Еще одна важная проблема всех систем «обучения с учителем» — переобучение. Грубо говоря, если у нас очень много разных параметров, то при обучении можно обнаружить некоторые закономерности, которых на самом деле нет (случайные флуктуации). Тогда при проверке вне обучающей выборки этой псевдозакономерности уже не будет, что негативно скажется на результате распознавания. На википедии упомянуты методы борьбы с этим, такие как регуляризация, перекрестная проверка и др.

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

Выводы

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