Объединение нескольких наборов данных

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

Что такое манифольд?

N-мерное многообразие является наиболее общим математическим пространством с пределами, непрерывностью и корректностью, а также допускает существование непрерывной обратной функции с n-мерными евклидовыми пространствами¹. Многообразия локально напоминают евклидово пространство, но могут и не быть евклидовым пространством. По сути, многообразие является обобщением евклидова пространства.

В топологии считается, что два объекта имеют одинаковую форму, если один из них можно
преобразовать в другой без разрезания или склеивания. Объекты с одинаковой формой
называются гомеоморфными. Многообразия гомеоморфны евклидовым пространствам.

Проблема выравнивания коллектора

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

Постановка задачи

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

Если нам нужны наборы данных X размером n×p и Y размером m×r, экземпляры которых лежат на одном и том же многообразии Z, то задача выравнивания состоит в том, чтобы найти f и g такие, что f( xᵢ) близко к g(yᵢ)евклидову пространству. В этом случае нас интересует сопоставление f:ℝᵖ→ℝᵏ и g:ℝʳ→ℝᵏ для некоторых скрытая размерность k. Мы используем ℝ для обозначения множества действительных чисел.

Каждая точка выборки xᵢиyᵢ может иметь точное соответствие, только если f(xᵢ) = g(yᵢ)иначе мы можем использовать предшествующую корреспонденцию как любую информацию о сходстве xᵢиyᵢ. [f(x); g(y)] будет унифицированным представлением X и Y в новом скрытом пространстве, тогда как f(X)иg(Y) будут новыми координаты X и Y.

Несколько идей для решения проблемы:

  1. Наряду с сохранением взаимосвязей между наборами данных сохраните индивидуальную структуру в каждом наборе данных, сопоставив аналогичные точки каждого набора данных с аналогичными местоположениями в евклидовом пространстве.
  2. Алгоритм выравнивания коллектора может быть неконтролируемым, полуконтролируемым или контролируемым в зависимости от того, сколько априорной информации доступно. Полная корреспонденция допускает контролируемый алгоритм, а неполная корреспонденция допускает полуконтролируемый или неконтролируемый алгоритм.
  3. Графические лапласианы каждого набора данных будут дискретной аппроксимацией одного и того же многообразия. Таким образом, диагональная конкатенация этих лапласианов вместе с недиагональными элементами, заполненными соответствием, является аппроксимацией этого многообразия.
  4. Мы можем использовать алгоритмы встраивания графов, чтобы сохранить локальное сходство, а соответствие может быть закодировано совместным лапласианом. Таким образом, выравнивание многообразия может быть сведено к проблеме обучения многообразию.

Функция потери

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

Если у нас есть c наборы данных X⁽¹⁾, X⁽²⁾, …, X⁽ᶜ⁾, тогда мы можем написать термин потери для набора данных, чтобы отразить сохранение локального сходства как

где F⁽ᵃ⁾ встраивается в a-й набор данных, т. е. новые координаты X⁽ᵃ⁾. Он говорит, похожи ли i-я и j-я строки, то есть когда W-term больше, чем F⁽ᵃ⁾(i, ·) и F⁽ᵃ⁾(j, ·) следует ставить близко друг к другу.

Для между наборами данных срок потери

который определяет стоимость сохранения соответствия между F⁽ᵃ⁾и F⁽ᵇ⁾. Таким образом, мы можем иметь полную функцию потерь как

Функция потерь для собственных карт Лапласа может быть записана с использованием совместной смежной матрицы как

где F — векторное представление всех наборов данных, а W — общая матрица смежности. Это говорит о том, что если i-я и j-ястроки X⁽ᵃ⁾ и X⁽ᵇ⁾ похожи в одном или разных наборы данных, что происходит, когда W(i, j) больше, чем их расположение в скрытом пространстве F(i, · ) и F(j, ·) должны стоять близко друг к другу. Мы можем переписать его как

где L — общий лапласиан всех наборов данных.

Таким образом, проблема оптимизации для выравнивания коллектора становится

где I — единичная матрица s × s, s — размерность новое пространство.

Оптимальность решения

Оптимальное решение вышеуказанной задачи оптимизации может быть решено с использованием множителя Лагранжа как

где F = [f₁, f₂, … fₛ], где решение представляет собой s наименьших ненулевых собственных векторов, а λ — множители Лагранжа.

Окончательный алгоритм

Учитывая c наборы данных X⁽¹⁾, X⁽²⁾, …, X⁽ᶜ⁾ все на одном многообразия, функция подобия S, обеспечивающая сходство двух точек выборки из одного и того же набора данных относительно геодезического расстояния вдоль многообразия, и некоторая информация о соответствии — может быть в виде сходства точек выборки из разных наборы данных (например, корреляция Пирсона, взаимная информация и т. д. — просто идея, нам нужно больше изучить), мы можем разработать алгоритм как

  1. Найдите матрицу смежности W⁽¹⁾, W⁽²⁾, …, W⁽ᶜ⁾ каждого набора данных, используя функцию подобия S — может включать вес между двумя экземплярами, если один из них является k-ближайшим соседом другого.
  2. Построить совместный лапласиан L.
  3. Вычислить sнаименьшие ненулевые собственные векторы Lf = λDф
  4. Строки следующих уравнений F являются новыми координатами X⁽ᵍ⁾:

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

Спасибо, что прочитали. Если вам понравилось то, что я пишу, и вы хотите поддержать мой контент, я прошу вас подписаться на Medium через https://rahulbhadani.medium.com/membership.

Рекомендации

  1. https://web.archive.org/web/20210506132703/https://www.math.lsa.umich.edu/~jchw/WOMPtalk-Manifolds.pdf
  2. https://www.math.arizona.edu/~glickenstein/research/laymanfin/node3.html
  3. https://web.archive.org/web/20160909193617/https://ocw.mit.edu/courses/mathematics/18-965-geometry-of-manifolds-fall-2004/lecture-notes/ лекция1.pdf
  4. https://my.vanderbilt.edu/stacyfonstad/files/2011/10/ShapeOfSpace.pdf
  5. https://people.csail.mit.edu/pkrafft/papers/wang-et-al-2010-manifold.pdf
  6. https://sites.google.com/site/changwangnk/home/ma-html