Классика баз данных - статьи

Продукты для крупномасштабного интеллектуального анализа данных и поддержки сообществ


Эдвард Чанг

В этом разделе описываются работы по созданию масштабируемых алгоритмов интеллектуального анализа Web-данных и социальных графов. Этими проектами руководит Эдвард Чанг, возглавляющий Google Research в Китае. На основе масштабируемой инфраструктуры интеллектуального анализа данных инженерная группа разрабатывает и внедряет два продукта поддержки социальных сетей. Работа этой группы привела к радикальному сокращению объема спама в результатах алгоритма PageRank в Китае (от 5% в 2006 г. до 1% в настоящее время).

Исследовательская работа фокусировалась на параллелизации шести критически важных алгоритмов машинного обучения: методов опорных векторов (Support Vector Machines, SVMs), декомпозиции сингулярных векторов (Singular Vector Decomposition, SVD), спектральной кластеризации (Spectral Clustering), поиска ассоциаций (Association Mining), вероятностного латентно-семантического анализа (Probabilistic Latent Semantic Analysis, (PLSA) и латентного размещения Дирихле (Latent Dirichlet Allocation, LDA). Целью распараллеливания этих алгоритмов являлось использование массивного распределенного хранилища данных и вычислительных сервисов Google. В частности, эта группа выполнила распараллеливание алгоритма SVMs [] и сделала полученную программу публично доступной вместе с исходным текстом по лицензии Apache.

Алгоритм SVMs широко используется при решении задач классификации из-за своей строгой теоретической обоснованности и успешного практического применения. К сожалению, этому алгоритму свойственны проблемы масштабируемости по отношению к использованию памяти и времени вычислений. Для преодоления этих проблем разработан параллельный вариант алгоритма SVMs (PSVM). PSVM позволяет сократить требуемый объем памяти за счет выполнения приближенной построчной факторизации матриц и загрузки на каждую из параллельно работающих машин только существенных данных. Время вычислений сокращается за счет разумного переупорядочивания последовательностей вычислений и выполнения их на параллельных машинах.
Кроме того, PSVM поддерживает отказоустойчивые вычисления для обеспечения возможности восстановления после отказов компьютеров-узлов.

Что касается вычислительной сложности, то пусть n обозначает число учебных образцов, p – размерность сжатой матрицы после факторизации (p значительно меньше n) и m – число машин. Если сравнивать PSVM с методом внутренних точек (Interior Point Method, IPM), то он позволяет сократить требования к памяти от O(n↑2) до O(np/m) и требует времени вычислений O(np↑2/m). Например, задача, решавшаяся на одной машине семь дней, на основе PSVM решается на 200 машинах за два часа. В настоящее время PSVM используется внутри Google для опознания распространяющих спам и предосудительных Web-сайтов. Поскольку реализация PSVM была сделана общедоступной, широко распространено скачивание кода.

Кроме PSVM, внутри Google доступны для использования параллельные версии алгоритмов SVD, PLSA и LDA. Эти алгоритмы полезны для решения задач классификации и совместного фильтрования (collaborative filtering). Что касается классификации, то PLSA применяется для обеспечения тегов для пользовательских запросов, коротких сообщений и пользовательских постов. В связи с совместным фильтрованием PLSA и LDA используются для поддержки различных средств рекомендаций, например, советов от друзей и экспертов, рекомендаций от форумов и подбора рекламы. Совместно эти два алгоритма применяются в двух продуктах, которые описываются ниже.

Первый продукт – это Knowledge Search, который сначала был запущен в России, потом в Китае [], а теперь запускается в нескольких других странах. Knowledge Search позволяет пользователям публиковать вопросы, а затем подбирает экспертов для своевременного ответа на вопросы. Отличительными чертами этого продукта по сравнению с конкурирующими продуктами являются обеспечение оперативной классификации вопросов, рекомендации родственных вопросов и подбор экспертов с учетом темы вопроса. Все эти возможности поддерживаются вышеупомянутой инфраструктурой машинного обучения.

Второй продукт – это Laiba, средство поддержки социальных сетей, изначально разработанное на основе Orkut. Группа сначала локализовала его, а затем быстро расширила его возможности, относящиеся, в частности, к совместному использованию фотографий и сервисам пользовательских взаимодействий. В Китае система Laiba была запущена в 2007 г. []. Как и Knowledge Search, этот продукт основывается на использовании крупномасштабных алгоритмов интеллектуального анализа данных для поддержки рекомендаций от друзей, сообщества или рекомендаций, основанных на контенте.

В настоящее время группа занимается дальнейшим расширением возможностей Laiba для поддержки платформы Google Open-Social [], которая позволит подключать Laiba и другие средства организации социальных сетей к приложениям сторонних разработчиков.


Содержание раздела