Объемы научных данных увеличиваются с поразительной скоростью, потому появляется необходимость в новых математических методах и методах анализа. Наборы данных становятся все больше и сложнее во многих дисциплинах, связанных, например, с нейронными сетями, астрофизикой или медициной.
Физик из Северо-Восточного университета (США) Алессандро Веспиньяни (Alessandro Vespignani) занимается моделированием поведения фондового рынка, предсказанием результатов выборов и другими статистическими задачами. В его распоряжении находятся несколько терабайт данных, полученных из социальных сетей, и почти все они [данные] неструктурированные.
Для обработки собранных данных Веспиньяни использует широкий набор математических инструментов и методов. Он сортирует миллионы твитов и проводит поиск по ключевым словам. Веспиньяни эффективно используют поэтапный подход к анализу больших данных. Однако математик Йельского университета Рональд Койфман (Ronald Coifman) утверждает, что недостаточно просто собирать и хранить громадные объемы информации, их нужно грамотно организовывать, а для этого нужна специальная структура.
Вершины и ребра
Возникший в XIII веке город Кёнигсберг (ныне Калининград) состоял из трёх формально независимых городских поселений, которые были расположены на островах и берегах реки Преголи, делящей город на четыре главные части. Эти четыре участка земли соединялись между собой семью мостами. В XVIII веке математик Леонард Эйлер ломал голову над популярной в то время загадкой: как пройти по всем семи мостам Кёнигсберга и вернуться в начальную точку, не ступая по каждому из мостов дважды?
Чтобы ее решить, Эйлер построил модель из точек и линий и обнаружил, что задача имеет решение только в том случае, если к каждому «островку земли» будет вести четное количество мостов. Так как в Кёнигсберге было нечетное количество мостов, это путешествие оказалось невозможным.
Взяв за основу идею Эйлера, математик Стэндфордского университета Гуннар Карлссон (Gunnar Carlsson) начал строить карты данных, представляя громоздкие наборы данных как сеть из вершин и ребер. Подход называется топологическим анализом данных (TDA – Topological Data Analysis), и, по словам Гуннара, «позволяет структурировать неструктурированные данные, чтобы в последствии проанализировать их методами машинного обучения». На видео Карлссон объясняет, как топологический анализ помогает исследователям интерпретировать большие наборы данных.
Как и в случае с задачкой про мосты, здесь все «связано» со связями, простите за каламбур. Социальные сети – это карта взаимоотношений между людьми, где вершинами являются имена, а ребрами – связи. Карлссон считает, что этот подход можно использовать в других сферах, например, для работы с геномными последовательностями. «Можно сравнить последовательности и выявить количество различий. Полученное число можно представить как функцию расстояния, которая будет показывать, насколько сильно они отличаются», – объясняет Карлссон.
Проект Карлссона Ayasdi создан именно для этого: он позволяет упрощать представление данных высокой размерности. Если ваш многоразмерный набор данных имеет 155 переменных, то как будет выглядеть запрос, учитывающий их все и разом? Карлссон сравнивает эту задачу с поиском молотка в темном гараже. Если у вас есть фонарик, то вы будете последовательно просматривать содержимое гаража, пока не наткнетесь на нужный вам инструмент – этот процесс достаточно долгий и может вывести вас из себя. Гораздо эффективнее включить свет – вы сразу найдете и молоток, и коробку гвоздей, хоть вы и не подозревали, что они вам понадобятся. Технология Ayasdi как раз зажигает лампочку.
Применяя топологические методы, мы словно проецируем сложный объект на плоскость. Опасность заключается в том, что некоторые закономерности — словно иллюзии в театре теней, и на самом деле не существуют. Более того, ряд учёных полагает, что к некоторым наборам данных топологические методы вообще неприменимы. Если ваш набор данных искажен или неполон, то они могут дать совершенно некорректные результаты.
Бритва Оккама
В феврале 2004 года математик Стэндфордского университета Эммануэль Кандес (Emmanuel Candes) пытался найти способ улучшить размытое изображение. Кандес применил один из разработанных алгоритмов и ожидал увидеть незначительные улучшения, однако перед ним предстала четкая картинка. По словам Кандеса, вероятность этого равнялась вероятности угадать десять цифр номера банковской карты, зная первые три. Но то была не случайность. Метод сработал и с другими изображениями.
Ключом к успеху стала, так сказать, математическая версия бритвы Оккама: из миллионов возможных вариантов реконструкции конкретного нечеткого изображения лучше всего подойдет самая простая версия. Это открытие породило метод Compressed sensing.
Сегодня он применяется в видеотрансляциях по сети. Количество данных при передаче видео так огромно, что приходится их сжимать. Обычно для того, чтобы сжать данные, необходимо сначала получить все биты, а затем отбросить незначимые. Метод Compressed sensing позволяет определить значимые биты, не требуя предварительного их сохранения.
«Если я провожу скрининг населения на наличие редкого заболевания, нужны ли мне анализы крови всех людей? Ответ – нет. Достаточно провести лишь несколько испытаний, поскольку искомый «фактор» встречается очень редко, то есть является разреженным», – отметил Кандес. Предположим, что у нас есть один зараженный в группе из 32 человек. У каждого из них мы взяли кровь на анализ. Если тест отрицательный, то инфицированных нет. Но если результат положительный, то как найти зараженного?
Кандес считает, что можно взять половину образцов (16) и провести повторный анализ. Если результат положительный, то инфицированный находится в этой группе, если нет, то в другой. Далее группа снова делится пополам, и тестирование повторяется. Таким образом, вы получите ответ за 5 тестов, вместо 32, если проверять каждого по отдельности. В этом суть метода Compressed sensing.
Метод Compressed sensing может помочь в работе с большими наборами данных, часть которых была утеряна или повреждена. Хорошим примером будет обработка медицинских записей, в части которых имеют опечатки, допущенные персоналом поликлиники. Еще один пример – система распознавания лиц: если человек наденет очки, его все равно можно будет узнать.
Пока Кандес превозносит методику Compressed sensing, Карлссон придерживается топологического подхода. Однако эти два метода лишь дополняют друг друга, но никак не конкурируют. «В конце концов, наука о данных – это нечто большее, чем просто сумма методологий, – настаивает Веспиньяни. – Объединив несколько методов, мы сможем создать что-то совершенно новое».
P.S. Совсем недавно мы публиковали подборку источников по машинному обучению для начинающих и рассказывали про глубокое обучение. Конечно, мы делимся и собственным опытом: немного о разработке системы квантовой связи и о том, как из простых студентов готовят продвинутых программистов.
Автор: Университет ИТМО
