Вупи Голдберг в векторах: оцениваем размерность пространства лиц

Всякий раз, когда мы включаем телефон и глядим в камеру, ему приходится решать сложную задачу: понять, его ли хозяин сейчас пытается его включить. По сути, это один из самых близких нам сейчас примеров задачи распознавания образов. Ее можно сформулировать так: пусть у нас имеется большая библиотека фотографий лиц разных людей в разных ракурсах. Как по новой фотографии лица определить, принадлежит ли она кому-то из людей в библиотеке, и если да, то кому именно? Математик Денис Федосеев с мехмата МГУ и его коллеги попытались выяснить, какой размерности должно быть пространство признаков, которые позволят отличить Вупи Голдберг от Шона Коннери.

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

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

Лица в векторах

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

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

Значит, чтобы решить задачу распознавания образов, нужно понять, какую геометрию имеет множество точек, построенное нейросетью. Вопрос осложняется еще и тем, что объемлющее пространство, в котором живут точки, как правило имеет огромную размерность. Например, некоторые из стандартных в индустрии нейросетей  (скажем, ResNet50 и ResNet100) работают с пространством размерности 512. Чтобы понять, насколько это необозримо, приведу пример: возьмем точку в 512-мерном пространстве и для каждой ее координаты скажем только, положительная она или отрицательная. Получим 2⁵¹² вариантов, что больше числа атомов в наблюдаемой части Вселенной. То есть для такой размерности даже простейшая попытка классифицировать точки по знаку координат обречена на провал.

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

Лоскутное одеяло

Многообразие — это, говоря неформально, многомерный «разумный» аналог кривой или поверхности. Пусть, например, у нас есть плоскость, двумерный объект. Если мы вырежем из нее маленький кусочек, получим так называемый двумерный диск. Разрешим себе изгибать этот диск — главное его не разрывать и не склеивать его точки. Теперь будем склеивать из таких изогнутых дисков «лоскутное одеяло». Полученный объект уже может быть устроен «хитрее» диска. Например, из двух изогнутых листов можно склеить сферу, которая на диск совсем не похожа. Это и есть неформальное описание устройства многообразия. В общем случае вместо двумерного диска — кусочка плоскости — нужно брать диски многомерные, кусочки многомерного пространства фиксированной размерности.

Чем удивительна гипотеза о многообразии? Допустим, точки оказались сосредоточены вблизи многообразия размерности 20 в 512-мерном пространстве. Это означает, что в любой области этого многообразия можно выбрать 20 параметров, и точки в этой области будут описываться только этими параметрами — а не всеми 512.

Пусть, к примеру, мы работаем с фотографиями голливудских звезд. У нас есть несколько фотографий Шона Коннери — они расположены близко друг к другу и описываются 20 параметрами. Это уже не вполне очевидно (точки в 512-мерном пространстве могут быть очень близки, но отличаться всеми координатами), но все-таки не контринтуитивно: фотографии одного человека похожи, поэтому можно в принципе ожидать, что они будут отличаться каким-то небольшим числом параметров.

Но пусть теперь у нас еще есть фотографии Вупи Голдберг. Они тоже описываются двадцатью параметрами. И, что самое удивительное, отличие — или схожесть — фотографий Вупи Голдберг от фотографий Шона Коннери тоже описывается всего-навсего 20 параметрами.

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

Путешествие по многообразиям

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

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

Первый метод имеет чисто геометрическую природу и использует так называемую размерность Минковского. Идея его в следующем. Пусть в пространстве имеется многообразие M, размерность которого мы хотим оценить. Разобьем объемлющее пространство на кубики с фиксированной длиной стороны r и посчитаем, сколько кубиков пересеклось с изучаемым многообразием. Обозначим это число через N(r).

Будем теперь уменьшать размер кубика, а количество кубиков, соответственно, увеличивать. Представим себе предельную ситуацию: кубики сжались в точки. Тогда множество кубиков, пересекающихся с нашим многообразием, в точности с ним совпадает, а остальные кубики заполнят остальную часть пространства. Отсюда можно предположить, что отношение N(r) к общему числу кубиков как-то описывает «размер» многообразия M.

На деле примерно так все и обстоит. Оказывается, что если устремить r к нулю, отношение логарифма N(r) и логарифма 1 / r стремится к некоторому числу. Оно и называется размерностью Минковского:

Теперь посмотрим на связь числа кубиков с многообразием с другой стороны. Пусть размер кубика мал. Тогда кубики, пересекающиеся с многообразием, покрывают все M и немного вылезают за его пределы. Причем чем меньше размер кубика, тем точнее они аппроксимируют многообразие. Известно, что число N(r) при маленьких r ведет себя примерно как V / rⁿ, где V — n-мерный объем нашего многообразия M (размерности n, которую мы хотим оценить). Этот факт можно понимать так, что V пропорционально N(r)rⁿ: здесь N(r) — количество рассматриваемых кубиков, а rⁿ — объем подкубика размерности, совпадающей с размерностью многообразия: эта величина близка к объему пересечения кубика с многообразием M. Например, рассмотрим простой случай: когда многообразие M — двумерная горизонтальная плоскость в трехмерном пространстве. Когда мы покрываем кубиками трехмерное пространство, пересечение кубика со стороной r с этим многообразием M — это в точности квадратик со стороной r (и площадью — то есть двумерным объемом — r²). Если многообразие устроено сложнее, точного равенства не получится, но при малых значениях r отличие тоже будет мало (как говорят, имеется асимптотическая формула).

Логарифмируя это соотношение, получаем, что при маленьких r логарифм N(r) устроен примерно как (log V − n log r). Логарифм объема — это некоторая константа, значит log N(r) есть некоторая линейная функция от логарифма длины стороны кубика, производной которой будет в точности размерность n. Поскольку N(r) можно посчитать экспериментально, этот метод дает возможность оценить размерность: достаточно получить N(r) из эксперимента, и вычислить тангенс угла наклона касательной к графику этой функции. Это и будет оценка на размерность n.

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

Вторая особенность, возникающая при применении метода к реальным данным, связана с размерностью объемлющего пространства и вычислительными возможностями компьютера. Как вычислить N(r)? Самое естественное — взять каждый кубик из всех, на которые разбито пространство (точнее, его ограниченный кусок, в котором мы живем), и проверить, пересекается ли он с М. На практике такой метод оказывается неприменим. В самом деле, пусть все наше многообразие М поместилось в кубе со стороной 1. Если мы рассмотрим даже r = ½, то мы получим 2⁵¹² кубиков. Это число мы уже упоминали выше: оно все еще превышает число атомов в наблюдаемой части вселенной, а потому совершенно необозримо.

С другой стороны, в реальности наше многообразие М не непрерывно, а состоит из конечного множества точек, которых относительно немного. И правильной тактикой оказывается рассматривать не кубики на предмет пересечения с М, а, наоборот, точки М — и отмечать, в какие кубики они попали. Такое обращение подхода делает этот метод вычислительно эффективным и применимым.

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

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

Здесь V(t) — n-мерный объем шара радиуса t (а n — все еще искомая размерность М).

Это распределение можно вычислить эмпирически по имеющемуся облаку точек, а значит, чтобы оценить размерность, достаточно подобрать такое n, что эмпирически подсчитанное максимально похоже на экспоненциальное, указанное выше, для этого n. Для поиска подходящего n используется следующий метод. Во-первых, хорошо известно, что у экспоненциального распределения квадрат первого момента равен второму. Во-вторых, для сравнения двух распределений можно использовать так называемую статистику Колмогорова-Смирнова, которую можно рассматривать как некоторое расстояние между распределениями. Соответственно, алгоритм оценки размерности выглядит так.

Для множества «подозрительных» n (кандидатов на роль размерности) вычисляются моменты распределения и статистика Колмогорова–Смирнова. Из претендентов выбирается такое n, для которого одновременно достигается минимум статистики Колмогорова–Смирнова и выполняется равенство А₁² = А₂ для моментов. Если среди кандидатов подходящего n не нашлось, максимальное допустимое значение n увеличивается и алгоритм повторяется.

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

Как ужать 512 в 25 

Эксперименты, проведенные на реальных базах данных фотографий людей показали, что оба метода дают близкие результаты, что косвенно подтверждает правильность этих результатов (поскольку методы совершенно различны по своей природе, близкие результаты свидетельствуют о достоверности). Оказалось, что размерность находится где-то в диапазоне от 22 до 26. Это интересно само по себе — это значит, что хотя размерность пространства огромная, 512, сами точки существенно описываются только примерно 25 параметрами.

Кроме того, этот результат подтверждает и гипотезу о многообразии, поскольку если бы множество точек было устроено хаотично, следовало ожидать, что методы оценки размерности «увидят» все пространство и дадут 512 или близко к тому. А приятно маленький ответ подсказывает, что структура многообразия действительно есть. А значит, ее можно исследовать и благодаря этому учить компьютер все лучше и лучше отличать Шона Коннери от Вупи Голдберг.