Топологический анализ данных (TDA)
Jul. 13th, 2013 02:32 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipahttp://en.wikipedia.org/wiki/Topological_data_analysis
Никто не разбирался? Понимаю, что вряд ли, но вдруг? На уровне идеи кажется разумным. Есть даже компания Ayasdi в Пало-Альто, которая на основе TDA делает продукт.
Никто не разбирался? Понимаю, что вряд ли, но вдруг? На уровне идеи кажется разумным. Есть даже компания Ayasdi в Пало-Альто, которая на основе TDA делает продукт.
no subject
Date: 2013-07-13 08:42 pm (UTC)С приложениями и даже с содержательной теорией там пока так себе. Я не знаю, что именно делает компания Ayasdi, но экстраполируя от "прикладных" статей Карлссона и его сотрудников я бы предположил, что topological persistence играет роль секретного ингредиента кока-колы.
no subject
Date: 2013-07-13 10:24 pm (UTC)Насчет Ayasdi -- очень может быть.
Advanced math and software rarely mix well. Even when the company does OK, the original advanced math claim tends to fade into the background
Цитата из статьи, откуда я узнал об Aysadi и TDA: http://www.dbms2.com/2013/07/12/predictive-modeling-ayasdi/
no subject
Date: 2013-07-14 06:05 pm (UTC)Пусть есть несколько точек, для которых мы хотим найти "правильную" топологическую структуру. Пусть у нас есть несколько топологических пространств-кандидатов на этих точках, и пусть на наборе пространств есть линейный (это требование можно ослабить) порядок, причем тождественное отображение непрерывно, если рассматривается из "меньшего" пространства в "большее". Единственный (насколько я знаю и с точностью до небольших модификаций) рабочий пример - точки погружаем в метрическое пространство и отождествляем те из них, расстояние между которыми меньше некоторого порога, а в остальном топологию индуцируем из метрики; упорядочиваем по величине порога.
Далее можно рассмотреть какой-нибудь топологический инвариант в каждом пространстве, скажем, число компонент связности (или другие числа Бетти). Можно рассмотреть последовательность значений этого инварианта на пространствах-кандидатах (в примере - это число компонент связности как функция порога); я буду дальше называть этот объект бар-кодом (другое название - persistence diagram). Доказано несколько теорем такого типа: если наборы точек "близки", то их бар-коды "близки".
Здесь надо остановиться и восхититься: мы по дискретному объекту - набору точек - построили штуку, которая отражает "топологические свойства в целом", устойчивую к "шевелениям". Например, рассмотрим все точки сферы. Бар-код, соответствующий числу компонент связности, очень прост: это функция, тождественно равная 1. Теперь рассмотрим "сэмпл", близкий к сфере в следующем смысле: на расстоянии меньше d от любой точки сферы есть точка сэмпла и наоборот, на расстоянии меньше d от любой точки сэмпла есть точка сферы. Тогда бар-код сэмпла получается из бар-кода сферы шевелением каждой точки графика не более чем на d.
Обратное неверно - насколько я понимаю (я не видел этого опубликованным, но устно "все знают"), для любой пары топологических пространств можно построить реализующие их наборы точек, бар-коды которых близки любым заданным образом. Поэтому возникает вопрос, что же мы можем извлечь из бар-кода и какие нужны предположения о "хорошести". Карлссон (см. ссылку в википедии) ограничился тем, что предложил более-менее такой сценарий: если в бар-коде есть "длинный" интервал, где значение постоянно, мы сочтем его истинным значением, а любое из соответствующих пространства - истинным топологическим пространством. Никаких обоснований у этого подхода нет.
Niyogi, Smale, Weinberger, "A topological view..." (формально это не про бар-коды, но только формально) показали вот что: если есть сэмпл из поверхности и точки сэмпла расположены существенно гуще, чем "расстояние от поверхности до себя" (то есть надо рассмотреть те точки поверхности, которые "в пространстве" гораздо ближе, чем "вдоль поверхности", и взять пару самых близких), то некоторая процедура позволяет по бар-коду (предобработанного) сэмпла найти истинное (=описывающее поверхность) значение. К сожалению, если продраться сквозь все их оценки к численным значениям, получаются совершенно нереальные числа, такой плотности в жизни не бывает (если я правильно помню, надо 10^5 точек вблизи окружности на плоскости, чтобы понять, что это окружность). Зато требуемый размер сэмпла не зависит от размерности объемлющего пространства, если она достаточно велика по сравнению с размерностью поверхности.
Мне кажется, что именно в интерпретации бар-кодов не хватает еще одной глубокой теоретической идеи, чтобы получился практически полезный метод. Помимо этого, есть вычислительная трудность: если вычислять бар-код "в лоб", время растет экспоненциально от количества точек (у меня получалось работать примерно с сотней точек). То есть надо как-то переходить к подвыборке или подвыборкам.
И одно финальное замечание: за почетное название "топологический анализ данных" боролся еще http://en.wikipedia.org/wiki/Statistical_shape_analysis by Dryden&Co. Насколько я слышал (про эту область я ничего не знаю), с прикладными результатами у них гораздо лучше.
no subject
Date: 2013-07-14 07:47 pm (UTC)А Вы практически использовали для каких задач? Если интересно, я могу описать задачу, которая есть у нас.
no subject
Date: 2013-07-15 04:30 pm (UTC)Если Вы поделитесь своей задачей (в той мере, в которой это не секрет), мне будет очень интересно, хотя я вряд ли смогу что-нибудь полезное сказать в ответ.
no subject
Date: 2013-07-17 02:08 pm (UTC)Но попробую дать ее в такой формулировке. Хотя в силу дискретности сложно формулировать математическим языком.
Есть набор X дискретных переменных (то есть каждая переменная принимает несколько дискретных значений). T(X, t) -- это некоторая последовательность во времени чисел (дискретных матриц чисел): то есть в момент t (на самом деле это не момент, а временной промежуток) для каждого значения переменной из X можно сопоставить некоторое значение. Чаще всего это значение -- 0. То есть всего может быть несколько миллионов возможных комбинаций, но не-нули около 1%. На всякий случай, dim T(X, t) = dim (X)
Есть другой набор Y дискретных переменных. И есть множество Z, каждый из элементов которого реализует некоторое значение Y (каждой из переменной).
I(T(X, t), Z, t) -- это некоторая "реализация" Z на T(X, t). В любой ячейке T(X, t) лежит какое-то число. I() описывает, как это число (количество) "расходуется" по разным Z. Для любой ячейки x из X, сумма по всем z из Z, I( T(x, t), z, t) = T(x, t). dim I = dim X
Далее, есть еще V(I) -- некоторый аналог функции цены, их может быть несколько.
Теперь, поскольку это описание малопонятно, в терминах предметной области:
X -- это описание параметров рекламных площадок (inventory),
T -- это трафик, который на них приходит
Y -- это описание параметров рекламных кампаний
Z -- описание самих кампаний (существующих, а не возможных)
I -- решение, о том, когда, где и в каком объеме каждую кампанию показывать
V -- измеренная эффективность кампании в данной ячейке трафика
У нас есть специальный адаптивный алгоритм, который вычисляет I на основании истории V(t<t0), чтобы максимизировать V(t0). Но возникает следующая задача. Пусть у нас есть новая кампания z1. Где ее лучше всего показывать? Проблема в том, что для нее нет еще истории, а набрать достаточно статистики и истории может быть очень дорого. Чтобы как-то подсказать алгоритму , нам надо понять, на какую кампанию или группу кампаний похожа новая. Иногда это можно сделать декларативно. Но иногда нет. Для проверки гипотезы "похожести" необходимо кластеризовать и факторизовать T или V. И там сразу все сложно и неприятно. В частности из-за разряженности матриц. Приходится отбрасывать некоторые переменные (уменьшать размерность, аналог проекции), чтобы уменьшить количество нулей. У меня возникла мысль, что топологический подход может дать что-то новое тут. Поскольку топология может позволить абстрагироваться от размерности. Но возможно, что я ошибаюсь.
no subject
Date: 2013-07-21 05:05 pm (UTC)no subject
Date: 2013-07-23 11:54 pm (UTC)