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

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

Топологический анализ данных

Я открыл для себя область топологического анализа данных, когда познакомился с платформой данных Ayasdi. Топологический анализ данных — это способ определить структуру в многомерных наборах данных. В своем выступлении специалист по данным Ayasdi Эллисон Гилмор на MLConf 2015 описывает, что топологический анализ данных может для определенных типов наборов данных победить проклятие размерности. Проклятие размерности распространено в науке о данных, где по мере увеличения количества признаков, например размерности вашего векторного пространства, расстояние между похожими точками увеличивается экспоненциально. Проклятие многомерности — одна из причин, по которой машинному обучению понадобились огромные объемы данных, с которыми мы сейчас сталкиваемся, чтобы начать показывать, на что они способны.

Как топологический анализ данных может победить проклятие размерности? Это проистекает из теории маломерных многообразий, вложенных в многомерные пространства, описанной в статье Нийоги, Смейла и Вайнбергера [1]. Теория, которую Эллисон описывает в своем выступлении, такова:

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

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

Сжатое зондирование

восстановление разреженных сигналов из нескольких тщательно сконструированных и, казалось бы, случайных измерений.

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

Сжатое зондирование — это область цифровой обработки сигналов, в которой используется определенная структура цифрового сигнала, по-видимому, нарушающая теорему Найквиста-Шеннона. Теорема Найквиста-Шеннона является наиболее фундаментальным законом цифровой обработки сигналов и утверждает, что для точного восстановления аналогового сигнала из дискретного представления этого сигнала вы должны производить дискретизацию с частотой, в два раза превышающей максимальную частоту, которую вы хотите дискретизировать. Например, если вы хотите создать цифровой сигнал, записав человеческий голос, максимальная частота которого составляет около 4 кГц, вам нужно сэмплировать в два раза больше или 8 кГц.

Сжатое зондирование было разработано математиками из Стэнфорда. В 2004 году Эммануэль Кандес, Теренс Тао и Дэвид Донохо доказали, что по сигналу, который был k-разреженным в некотором базисе, сигнал может быть восстановлен с помощью m › k отсчетов, даже когда m меньше числа отсчетов, диктуемого теоремой Найквиста-Шеннона [2, 3]. Важным понятием здесь является k-разреженность. Сигнал называется разреженным, если в некотором базисе количество ненулевых значений много меньше размерности базиса. Простым примером разреженного сигнала является последовательность всплесков, как показано ниже, где все значения равны нулю, кроме нескольких. Последовательности спайков обычно используются для представления активации нейронов.

Другие разреженные сигналы включают синусоидальные волны только с несколькими частотами, которые разрежены в базисе Фурье. Кроме того, некоторые черно-белые изображения, которые имеют лишь несколько переходов от черного к белому, разрежены в базе, которая измеряет переходы. Это приложение успешно применялось к медицинским изображениям, таким как изображения КТ и МРТ.

Сжатое зондирование, также известное как сжатая выборка, может рассматриваться как решение неопределенной системы линейных уравнений. В приведенном ниже примере предположим, что у нас есть измерение y, представляющее собой выборочную версию сигнала x. Обычно неопределенные системы линейных уравнений имеют бесконечно много решений, однако при при определенных ограничениях такие системы имеют единственное решение. Разреженность — одно из таких ограничений. Таким образом, если сигнал x является k-разреженным, а размерность y равна › k, то можно найти единственное решение системы линейных уравнений.

В [3] Кандес и Тао показали, что, используя гауссову случайную матрицу для D, можно точно восстановить x. Это захватывающий результат: из нескольких случайных проекций разреженного вектора x можно восстановить исходный вектор.

Как это связано с предыдущей теорией топологического анализа данных? Хотя эти разреженные сигналы не обязательно могут лежать в многообразии более низкого измерения, их можно рассматривать как встраивание сигнала более низкого измерения в пространство более высокого измерения. Таким образом, обе теории показывают, что количество измерений, необходимых для описания характеристик сигнала, связано с размерностью внутреннего пространства признаков, а не с размерностью любого пространства более высокой размерности, в которое встроены эти признаки.

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

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

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

Кроме того, недавно было объявлено о последнем наборе стипендиатов MacArthur Fellows, и Эммануэль Кандес был выбран в качестве стипендиата за его работу в области сжатого зондирования и статистики.

[1] Топологический взгляд на обучение без учителя на основе зашумленных данных, П. Нийоги, С. Смейл, С. Вайнбергер, SIAM J. Comput., 40(3), 646–663. (18 страниц). "Ссылка на сайт"

[2] Сжатое зондирование, Д. Донохо, Статистический факультет Стэнфордского университета. "Ссылка на сайт"

[3] Э. Дж. Кандес и Т. Тао. Почти оптимальное восстановление сигнала из случайных проекций: универсальные стратегии кодирования. IEEE Trans. Сообщить. Теория, 52 5406–5425. "Ссылка на сайт"