Самообучающиеся алгоритмы находят новые области применения

18 ноябрь, 2013 - 10:52
Самообучающиеся алгоритмы находят новые области применения

Какая комбинация визуальных признаков свидетельствует о присутствии определенного объекта на цифровом снимке? Какие звуки речи соответствуют определенным словам? Какой набор медицинских, генетических и внешних факторов ведет к развитию того или иного заболевания? Большинство приложений искусственного интеллекта, так или иначе, требуют нахождения статистических корреляций между переменными. С ростом количества переменных, вычисление их совместной статистики превращается в исключительно трудоемкую задачу. Но такие расчеты можно значительно упростить, обладая дополнительной информацией о структуре данных — например, что за буквой «Т» (и за соответствующим ей звуком) часто следует буква «R», но никогда «Q».

В статье, подготовленной для ежегодной конференции, проводимой Neural Information Processing Systems Foundation в декабре, исследователи MIT описывают новую методику, позволяющую расширить подмножество наборов данных, для которых возможно эффективное упрощение структуры. Предложенный алгоритм позволит распространить методы искусственного интеллекта на новый круг задач, таких как анализ функционирования социальных сетей.

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

В техническом контексте, идея представленной работы заключается в оптимизации вероятностной графической модели, состоящей из узлов и ребер (или дуг) между ними. Все ребра характеризуются определенным весовым коэффициентом, отражающим статистическую взаимосвязь между соединяемыми ими узлами. Например, в вышеприведенном лингвистическом примере, ребро между узлами, соответствующими «Т» и «R», будет по весу значительно превосходить то, что соединяет «Т» и «Q».

Как установлено уже давно, представление данных в графическом виде способствует ускорению алгоритмов машинного обучения в том случае, если не содержит замкнутых контуров, например, имеет древоподобную структуру. Замкнутые петли, как указывает один из авторов публикации, Ин Лю (Ying Liu), аспирант факультета электротехники и информатики MIT, создают проблему, поскольку делают алгоритм статистических умозаключений слишком «самоуверенным». Для обоснования заключений о статистической взаимосвязи каждый узел рассылает сообщения своим соседям, включающие только локальную информацию и поступающие данные от других соседей. Наличие петли означает, что принимаемые им сообщения отчасти содержат сведения от него самого.

В более ранней работе те же авторы показали, что эффективное машинное обучение возможно даже для «контурного» вероятностного графа при условии, что в нем достаточно невелико число «узлов обратной связи» (feedback vertex set, FVS) — т.е. таких узлов, удаление которых превращает граф с петлями в древоподобный.

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