Главные графы

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Метод главных графов (principal graphs, elastic principal graphs) — метод нелинейного снижения размерности и аппроксимации данных, предложенный и развитый А. Н. Горбанем, А. Ю. Зиновьевым и соавторами как обобщение метода главных компонент, k-means и главных многообразий. Главный граф представляет данные объектом малой сложности: графом, вложенным в исходное признаковое пространство. Вложение выбирается так, чтобы одновременно минимизировать среднеквадратичную ошибку аппроксимации данных и штрафовать чрезмерную длину, изгиб и ветвление графа.

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

Изображение:Principal graph vs pca.png
PCA аппроксимирует данные одной линейной главной компонентой, тогда как главный граф может иметь ветвления и поэтому описывает распределения со сложной топологией.

Мотивация

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

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

  • вершины графа вкладываются в \mathbb{R}^m;
  • рёбра задают соседство и позволяют интерпретировать граф как кусочно-линейный скелет;
  • звёзды и рёбра графа задают упругий штраф, не позволяющий графу произвольно подстроиться под шум;
  • графовая грамматика управляет ростом топологии: например, разрешает добавить вершину или разделить ребро.

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

Краткая историческая сводка

В 1901 году К. Пирсон предложил аппроксимировать многомерные наблюдения «прямыми и плоскостями наилучшего приближения», что стало геометрической основой PCA. Позднее k-means сформулировал близкую задачу аппроксимации не прямыми и плоскостями, а конечным набором центров. В 1980-е годы Т. Хасти и В. Штюцле ввели главные кривые как самосогласованные нелинейные обобщения главных компонент, а карты Кохонена дали алгоритмически близкую нейросетевую конструкцию с регулярной сеткой узлов.

В работах Горбаня и Зиновьева была развита техника эластичных карт (elastic maps): главные многообразия строятся как упругая сетка, вложенная в пространство данных. В этой конструкции регулярность задаётся простым квадратичным функционалом длины и изгиба. Затем Горбань, Зиновьев, Самнер и соавторы расширили эту схему на графы произвольной, но контролируемой топологии: топология строится графовыми грамматиками, а вложение каждого кандидата оптимизируется по эластическому функционалу.

Термин «principal graph» ранее использовался Б. Кеглем и А. Крыжаком для кусочно-линейной скелетизации символов. Подход Горбаня и соавторов отличается универсальным штрафом для ветвящихся точек: идеальная конфигурация задаётся не списком специальных типов вершин, а условием гармоничности или плюригармоничности звёзд графа.

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

Пусть X=\{x_i\}_{i=1}^N, x_i\in\mathbb{R}^m — конечный набор многомерных наблюдений. Пусть Y\subset\mathbb{R}^m — аппроксимирующий объект. Ортогональной проекцией точки x на Y называется P(x,Y)=\arg\min_{y\in Y}\operatorname{dist}(x,y). Возможна неоднозначность проекции; в алгоритмах обычно фиксируют одно из ближайших значений.

Среднеквадратичное расстояние от выборки до аппроксимирующего объекта: \operatorname{MSD}(X,Y)= \frac1N\sum_{i=1}^N \operatorname{dist}^2(x_i,P(x_i,Y)). Взвешенная версия при w_i>0: \operatorname{MSD}_W(X,Y)= \frac{1}{\sum_i w_i}\sum_{i=1}^N w_i\,\operatorname{dist}^2(x_i,P(x_i,Y)).

Главный объект должен:

  1. хорошо аппроксимировать данные в смысле малого \operatorname{MSD};
  2. удовлетворять регуляризующим условиям, ограничивающим геометрическую, структурную и конструкционную сложность.

Для PCA множество Y — аффинное линейное подпространство. Для k-means множество Y — конечный набор центров. Для главных графов Y получается как образ вершин графа и, при необходимости, как кусочно-линейная интерполяция по его рёбрам.

Эластичный граф

Пусть G=(V,E) — простой неориентированный граф. Для k\geq 2 k-звездой в G называется подграф с вершинами v_0,v_1,\ldots,v_k и рёбрами (v_0,v_i), i=1,\ldots,k. Вершина v_0 называется центральной. 2-звезда называется ребром (rib) в терминологии эластичных карт; это не ребро графа, а тройка соседних вершин, штрафующая изгиб.

Пусть для каждого k\geq 2 выбрано семейство S_k из k-звёзд. Эластичный граф — это граф с выбранными семействами S_k, в котором каждому ребру E^{(i)}\in E поставлен в соответствие модуль растяжения \lambda_i>0, а каждой звезде S_k^{(j)}\in S_k — модуль изгиба \mu_{kj}>0.

Примитивный эластичный граф — эластичный граф, в котором каждая нетерминальная вершина, то есть вершина степени больше единицы, является центром k-звезды, образованной всеми её соседями. В таком графе семейства звёзд полностью определяются топологией графа.

Пусть \phi:V\to\mathbb{R}^m — вложение вершин графа в пространство данных. Если E^{(i)}(0), E^{(i)}(1) — концы ребра E^{(i)}, а S_k^{(j)}(0),\ldots,S_k^{(j)}(k) — вершины k-звезды, причём S_k^{(j)}(0) центральная, то эластическая энергия вложения задаётся функционалом U^\phi(G)=U^\phi_E(G)+U^\phi_R(G), где U^\phi_E(G)= \sum_{E^{(i)}}\lambda_i \left\|\phi(E^{(i)}(0))-\phi(E^{(i)}(1))\right\|^2, U^\phi_R(G)= \sum_{S_k^{(j)}}\mu_{kj} \left\|\sum_{i=1}^{k}\phi(S_k^{(j)}(i)) -k\phi(S_k^{(j)}(0))\right\|^2.

Первый член штрафует суммарное растяжение рёбер. Второй член штрафует отклонение центральной вершины звезды от среднего положения её соседей. Для 2-звезды это дискретный аналог квадрата второй производной, то есть штраф за изгиб.

Метафора упругой мембраны

Изображение:Elastic membrane metaphor.png
Эластичная карта как мембрана: данные тянут узлы к себе, а внутренние рёбра и 2-звёзды сопротивляются растяжению и изгибу.

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

Для k-звезды с центром y_0 и концами y_1,\ldots,y_k энергия имеет вид u_{S_k}=\mu_{S_k}\left\|\sum_{i=1}^k y_i-k y_0\right\|^2. В пружинной интерпретации этот член можно записать как u_{S_k} =k\mu_{S_k}\sum_{i=1}^k \|y_i-y_0\|^2 -\mu_{S_k}\sum_{i>j}\|y_i-y_j\|^2. То есть звезда эквивалентна системе положительных пружин от центра к концам и отрицательных пружин между концами. Эта запись объясняет, почему локальная «мембрана» выпрямляется: минимум достигается, когда центр совпадает со средним своих соседей.

Энергия аппроксимации

Для фиксированного вложения \phi вершины графа разбивают выборку на ячейки ближайших узлов: K^{y_j}=\{x\in X:\ y_j=\arg\min_{y_k\in V} \|\phi(y_k)-x\|\}. Энергия аппроксимации: U_A^\phi(G,X)= \frac{1}{\sum_{x\in X}w(x)} \sum_{y\in V}\sum_{x\in K^y} w(x)\|x-\phi(y)\|^2, где w(x)\geq 0 — веса точек; в простейшем случае w(x)=1.

Оптимальное вложение при фиксированной топологии минимизирует полный функционал U^\phi=U_A^\phi(G,X)+U^\phi(G). В узловой версии проекция точки берётся на ближайшую вершину. Для визуализации и получения внутренних координат часто используют кусочно-линейную интерполяцию по рёбрам и проекцию на ближайшую точку полученного полилинейного объекта.

Идеальные и плюригармонические вложения

Штраф звезды обращается в нуль тогда и только тогда, когда центральная вершина совпадает со средним значением соседних вершин: \phi(S_k^{(j)}(0))= \frac1k\sum_{i=1}^k \phi(S_k^{(j)}(i)). Вложение называется идеальным, если все такие штрафы равны нулю.

Для примитивного эластичного графа это условие означает, что вложение является гармонической функцией на графе: значение в каждой нетерминальной вершине равно среднему значению в ближайших соседях. Для общего эластичного графа, где звёзды могут включать не всех соседей центра, авторы используют понятие плюригармонического отображения: отображение \phi:V\to\mathbb{R}^m плюригармонично, если указанное среднее условие выполнено для каждой выбранной k-звезды.

Плюригармонические вложения играют роль «идеальных» конфигураций. Эластическая энергия измеряет отклонение главного графа от этой идеальной формы; тем самым она является мерой нелинейности и нерегулярности.

Сложность главного графа

Главные графы у Горбаня и соавторов формулируются как аппроксиматоры контролируемой сложности. Используются три типа сложности.

Геометрическая сложность — отклонение вложения от идеального плюригармонического графа. Для эластичных главных графов она явно измеряется энергией U^\phi(G).

Структурная сложность — неубывающая функция числа вершин, рёбер и звёзд: SC(G)=SC(|V|,|E|,|S_2|,\ldots,|S_m|). Например, можно ограничить только число вершин SC(G)=|V| или число ветвлений степени 3.

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

Пусть выбраны графовая грамматика, ограничения SC_{\max} и CC_{\max}, а также коэффициенты \lambda_i и \mu_{kj}. Эластичным главным графом для выборки X называется эластичный граф G, вложенный в \mathbb{R}^m отображением \phi, такой что SC(G)\leq SC_{\max}, CC(G)\leq CC_{\max}, и полный функционал U^\phi минимален среди допустимых вложений и допустимых графов, достижимых выбранной грамматикой.

Процедура обучения

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

Оптимизация вложения при фиксированном графе

При фиксированном разбиении \{K^y\} функционал U^\phi является положительным квадратичным функционалом по координатам узлов. Поэтому новые положения вершин находятся из системы линейных уравнений: \sum_{k=1}^{p} a_{jk}\phi(y_k)= \frac{1}{\sum_{x\in X}w(x)} \sum_{x\in K^{y_j}} w(x)x, где p=|V|, a_{jk}=\frac{n_j\delta_{jk}}{\sum_{x\in X}w(x)} +e_{jk}+s_{jk}. Здесь n_j=\sum_{x\in K^{y_j}}w(x). Матрицы e_{jk} и s_{jk} зависят только от рёбер, звёзд и коэффициентов упругости.

Для ребра E^{(i)} с весом \lambda_i и концами k_1,k_2 матрица e обновляется так. Новые значения обозначены тильдой: \tilde{e}_{k_1k_1}=e_{k_1k_1}+\lambda_i. \tilde{e}_{k_2k_2}=e_{k_2k_2}+\lambda_i. \tilde{e}_{k_1k_2}=e_{k_1k_2}-\lambda_i. \tilde{e}_{k_2k_1}=e_{k_2k_1}-\lambda_i.

Для k-звезды с весом \mu_i, центральной вершиной N_0 и внешними вершинами N_1,\ldots,N_k матрица s обновляется так: \tilde{s}_{N_0N_0}=s_{N_0N_0}+k^2\mu_i. При 1\leq l,m\leq k: \tilde{s}_{N_lN_m}=s_{N_lN_m}+\mu_i. \tilde{s}_{N_0N_l}=s_{N_0N_l}-k\mu_i. \tilde{s}_{N_lN_0}=s_{N_lN_0}-k\mu_i.

Алгоритм EM-типа:

  1. выбрать начальное положение узлов;
  2. разбить данные на множества ближайших узлов K^{y_j};
  3. при фиксированном разбиении решить разреженную систему линейных уравнений для новых \phi(y_j);
  4. повторять два предыдущих шага до сходимости.

Как и k-means, эта процедура гарантирует локальный минимум, но не глобальный. Поэтому на практике применяют стратегии продолжения: начинают с жёсткого графа, то есть больших \lambda и \mu, затем постепенно «смягчают» его. Для регулярных сеток внутренней размерности d используется масштабировка \lambda=\lambda_0 s^{(2-d)/d}. \mu=\mu_0 r^{(2-d)/d}. где s — число рёбер, r — число 2-звёзд. Для произвольных графов размерность не всегда определена, поэтому коэффициенты выбираются из прикладных соображений или адаптивно.

Рост топологии графа

Графовая грамматика — набор правил вида A\to B, где A и B — эластичные графы. Применение правила заменяет в текущем графе копию A на копию B и соединяет её с остальным графом согласно меткам.

Алгоритм построения эластичного главного графа:

  1. инициализировать граф двумя вершинами, соединёнными ребром; начальное вложение берётся на первом главном направлении так, чтобы данные проектировались на отрезок между этими вершинами;
  2. применить все операции текущей грамматики ко всем допустимым местам графа, получив набор кандидатов G_1,G_2,\ldots;
  3. отбросить кандидаты, нарушающие ограничения SC_{\max} и CC_{\max};
  4. для каждого допустимого кандидата оптимизировать вложение EM-процедурой;
  5. выбрать кандидат с минимальным значением U^\phi и заменить текущий граф;
  6. повторять до исчерпания допустимых преобразований или достижения заданной конструкционной сложности.
Изображение:Graph grammar operations.png
Две базовые операции роста: добавить вершину к вершине и разделить ребро.

Главные деревья и metro map

Простейший важный класс главных графов — главные деревья.

Главное дерево — ациклический примитивный эластичный главный граф.

Для построения главных деревьев используется грамматика роста O_{\mathrm{grow}}:

  • add a node: к любой вершине v добавляется новая вершина z и новое ребро (v,z);
  • bisect an edge: ребро (v,v') удаляется, добавляется вершина z и два ребра (v,z), (z,v').

Так как граф примитивный, список звёзд изменяется автоматически вместе с топологией. Последовательное применение этих операций порождает деревья. Для улучшения результата авторы также используют грамматику сжатия O_{\mathrm{shrink}}, включающую удаление листа и удаление ребра. Комбинация роста и последующего «подрезания» уменьшает лишние ветвления и сливает звёзды, разделённые короткими мостами.

Для визуализации главного дерева используется представление metro map. Дерево вкладывается в двумерную схему так, чтобы:

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

Название подчёркивает смысл: это не буквальная проекция, а схематическая карта структуры данных, подобная схеме метро. Расстояние на такой карте оценивают суммой длин ветвей, а классы или плотности точек можно показывать размером и окраской узлов.

Связь с PCA, k-means и картами Кохонена

Если убрать рёбра и звёзды, остаётся аппроксимация конечным набором независимых центров — это близко к k-means. Если задать регулярную решётку и сделать её достаточно жёсткой, эластичная карта приближается к линейным главным многообразиям PCA. При промежуточных значениях упругости получается нелинейная аппроксимация, способная изгибаться, но не следовать каждому шумовому отклонению.

Карты Кохонена также используют узлы и соседства между ними, но в классической формулировке SOM задаётся алгоритмом самоорганизации, а не явным минимизируемым функционалом с контролем геометрической, структурной и конструкционной сложности. Эластичные главные графы делают этот контроль явным: качество аппроксимации, регулярность и сложность входят в одну постановку.

Главное отличие от PCA состоит не только в нелинейности. PCA сохраняет глобальную линейную систему координат, но не умеет создавать ветвления. Главный граф может выражать ситуацию, когда данные расходятся по нескольким ветвям от общего ствола: например, траектории дифференцировки клеток, варианты динамического режима или несколько родственных классов объектов.

Практические замечания

  • Метод чувствителен к выбору коэффициентов \lambda, \mu и ограничений сложности. Большие значения дают гладкие и жёсткие графы, малые значения увеличивают риск переобучения.
  • Из-за локальности EM-оптимизации полезны стратегии смягчения, несколько инициализаций и ограничение грамматики.
  • Для данных с выбросами желательно использовать веса w(x), робастные модификации расстояния или предварительную очистку данных.
  • Для визуализации важно различать граф как аппроксиматор в \mathbb{R}^m и его двумерную схему; metro map может искажать углы и расстояния ради читаемости.
  • При пропущенных значениях можно модифицировать расстояния и проекции, поскольку алгоритм требует главным образом вычисления ближайших узлов и решения квадратичной задачи.

См. также

Приложения

  • Визуализация многомерных данных. Главные деревья и metro map дают двумерные схемы ветвящихся распределений, часто более интерпретируемые, чем линейная PCA-проекция.
  • Биоинформатика и транскриптомика. В работах Горбаня и Зиновьева эластичные карты и главные деревья применялись к данным микрочипов, где нелинейные карты лучше разделяли подтипы опухолей и нормальные ткани.
  • Анализ геномных текстов. Principal trees использовались для анализа 7-кластерной структуры бактериальных геномов и визуализации частотных признаков фрагментов ДНК.
  • Динамические системы. Главные многообразия и графы применялись для аппроксимации инвариантных многообразий и траекторий в фазовом пространстве.
  • Сравнительная политология и социальные данные. Нелинейные главные объекты использовались для построения низкоразмерных карт стран и режимов, когда линейная PCA-плоскость сглаживает важные нелинейные зависимости.
  • Скелетизация и распознавание образов. Исторически principal graphs применялись для кусочно-линейной скелетизации рукописных символов; эластичная регуляризация делает такие скелеты устойчивее.
  • Разведочный анализ данных. Метод удобен как промежуточный инструмент между кластеризацией и снижением размерности: узлы графа задают грубые кластеры, а рёбра показывают связи между ними.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B»
Личные инструменты