Исследование методов сокращения размерности в задаче распознавания образов

Введение
Во всех современных системах распознавания образов повышение скорости и улучшение точности распознавания являются двумя главными критериями. Тем не менее, эти параметры обычно работают друг против друга – когда увеличивается скорость, точность уменьшается, и наоборот. Это особенно важно при работе со сложными системами, описываемыми большим числом параметров, поскольку по мере увеличения размерности данных информация, необходимая для эффективного анализа, растет в геометрической прогрессии. В 1961 году Ричард Беллман назвал эту проблему «проклятием размерности» . Увеличение размерности пространства влечет за собой множество недостатков, таких как переобучение, меньшая интерпретируемость (как следствие, меньшая точность модели) и увеличение времени обучения. Популярные подходы ориентированы на то, чтобы спроецировать информационное пространство с более высокой размерностью в пространство меньшей размерности, сохраняя как можно больше данных . Методы сокращения размерности обычно следуют этому общему принципу, чтобы устранить «проклятие размерности» и другие нежелательные факторы, присутствующие в данных с более высокой размерностью. Это сокращает время обучения и тестирования, удаляя менее важные признаки, а также повышает точность системы. Таким образом, исследование методов сокращения размерности данных является актуальной задачей.
Цель исследования
Целью исследования является применение методов сокращения размерности к задаче распознавания образов.
Материал и методы исследования
В качестве задачи распознавания образов в данной работе была выбрана задача распознавания рукописных символов текста на изображениях. В качестве набора данных использован набор MNIST, который состоит из 70 000 изображений: 60 000 обучающих для обучения модели и 10 000 тестовых для оценки точности. Каждое изображение MNIST – это оцифрованная картинка одной цифры, написанной от руки, имеющая размер 28 × 28. Каждое значение пикселя лежит в диапазоне от 0 (представляет белый цвет) до 255 (представляет черный цвет). Промежуточные значения отражают оттенки серого. Задача состоит в распознавании цифр (от 0 до 9), поэтому имеется всего 10 классов для классификации.
Мотивация эксперимента заключалась в том, чтобы продемонстрировать, как снижение размерности данных может привести к сокращению общего времени обработки данных и повышению точности системы, реализованной для решения одной из задач распознавания образов.
Для выполнения цели исследования были использованы такие методы снижения размерности, как метод главных компонент и стохастическое вложение соседей с t-распределением (t-distributed Stochastic Neighbor Embedding, t-SNE).
Метод главных компонент (Principal Component Analysis, PCA) – это метод линейного уменьшения размерности, который работает путем встраивания данных с более высокой размерностью в подпространство с более низкой размерностью. Основная идея метода главных компонент состоит в том, чтобы выразить исходные данные в терминах нового набора некоррелированных ортогональных базисных векторов, называемых главными компонентами

. Эти компоненты на самом деле являются собственными векторами ковариационной матрицы исходных данных. После этого преобразования ковариация между каждой парой новых компонент становится равной нулю, то есть отделяется влияние одного признака на другие. Причина, по которой метод главных компонент можно использовать для снижения размерности, заключается в том, что компоненты с более высоким рангом являются направлениями, в которых данные показывают наибольшую дисперсию. Можно было бы просто выбрать некоторые из наиболее важных компонент метода, которые достаточны для объяснения данных для обучения моделей.
Пусть x1, x2,..., xn – исходный набор данных в D-мерном пространстве. Цель метода состоит в том, чтобы представить набор данных в подпространстве W, где W D . yi как линейная комбинация переменных с i = 1…n определена следующим образом:
yi=AT (x-mx) (1)
где A=α1α2…αn – матрица со столбцами, имеющими собственные векторы ковариации исходных данных более высокой размерности, mx – среднее значение исходного набора данных.
Более современные нелинейные методы пытаются сохранить локальные свойства наборов данных более «мягким» способом. В частности, метод SNE (Stochastic Neighborhood Embedding, рус. Стохастическое вложение соседей) был разработан для сохранения идентичности соседства . Для этого используется функция стоимости, которая способствует тому, чтобы распределения вероятностей точек, принадлежащих окрестностям других точек, были подобными в многомерном пространстве и в его вложении малой размерности. В первоначальной формулировке для измерения этого сходства использовалось расстояние Кульбака-Лейблера. Более подробно, сначала оценивается вероятность того, что выборка xi в многомерном пространстве выберет выборку xj в качестве соседа:
pj|i=exp⁡(-||xi-xj||22σi2)k≠iexp⁡(-xi-xk22σi2) (2)
где σi – среднее стандартное отклонение с центром в xi.
Точно так же моделируется вероятность того, что yi, аналог xi в пространстве малой размерности, примет yj в качестве соседа:
qj|i=exp⁡(-||yi-yj||2)k≠iexp⁡(-yi-yk2) (3)
Расположение точек yi в пространстве малой размерности определяется минимизацией расстояния Кульбака-Лейблера распределения Q от распределения P:
KL(P|Q= i≠jpj|ilogpj|iqj|i (4)
t-SNE предлагает функцию стоимости, вдохновленную SNE, но использующую t-распределение Стьюдента, а не распределение Гаусса, чтобы вычислить сходство между двумя точками в пространстве малой размерности. Это распределение значительно облегчает так называемую проблему «скученности», наблюдаемую в SNE, когда удаленные выборки данных, например, области с низкой плотностью между естественными кластерами, сближаются в пространстве малой размерности. Кроме того, t-SNE фактически использует симметричную версию SNE, в отличие от первоначальной формулировки, где pj|i не обязательно было равно pi|j. Минимизация функции стоимости выполняется с использованием метода градиентного спуска.
Метод t-SNE хорош преимущественно тем, что он сохраняет метрику. Недостаток метода заключается в том, что, в отличие от PCA, он не является воспроизводимым, то есть его необходимо обучать заново для каждой новой выборки