Ну что, развлеклись? Теперь за работу.
До начала этого года я был уверен, что человеческий интеллект с точки зрения теории вычислительной сложности является какой-то неразрешимой загадкой. Люди практически непрерывно решают задачи построения когнитивных моделей по большому набору входов большой размерности, что выглядит подозрительно похожим на решение NP-полных задач. Я даже было думал, что все эти тысячи теоретиков что-то проглядели, и пытался, опираясь на работы Leslie Valiant'а, решить Monotone Parity-P за полином малой размерности. Какие-то интересные штуки я даже придумал, но все это получилось не особенно практично. Похоже, на халяву решать произвольные NP-полные задачи таки невозможно, и лет через 30 алгебраические геометры нам расскажут, почему.
Но это неважно. Совершенно неожиданно для себя я узнал, что британские ученые изобрели очередной мощный шаг в построении strong AI, и теперь хотя бы понятно, куда копать.
Для начала определимся с целями.
"Слабый" AI - это общее название для набора технологий (как уже существующих, так и находящихся в разработке), имитирующих те или иные аспекты умственной деятельности человека. Это размытая область, она различным пересекается с machine learning, статистикой, теорией оптимального управления, робототехникой, статистической лингвистикой, и т.д и т.п. Современные поисковики - самый типичный пример технологий этого класса.
Strong AI - это светлая мечта фантастов, машина, проходящая тест Тьюринга, и могущая заменить или превзойти человека в любом роде деятельности
кроме порнофильмов.
Переход сразу от первого ко второму выглядит подозрительно и похож на чудо. Должен быть правдоподобный промежуточный этап.
Таким этапом предлагается считать появление вычислительно приемлемых алгоритмов unsupervised learning, единообразно и в режиме реального времени решающих следующие задачи:
- парсинг естественного языка
- распознавание объектов на изображениях и видео
- распознавание речи
- установление структурированных ассоциативных связей в "сенситивной каше", состоящей из всего вышеперечисленного
Этого недостаточно, чтобы клепать автоматических Платонов, Невтонов и прочих Перельманов, но вполне достаточно для того, чтобы сделать типичного "тупого робота" из классической фантастики, которому можно доверить водить автомобили, поезда и танки, который сможет полностью заменить людей на производстве (за исключением инженеров-технологов), а также собирать урожай, доить коров
и встречаться со стиральной машиной. Назовем это, скажем, medium AI.
Но создание алгоритмов подобного класса - это все равно звучит фантастически, правда? А вот неправда. Оказывается, всё (хорошо, почти всё) уже придумано без нас, остается это свести воедино.
1) Были концептуальные трудности, связанные с тем, что не существует "единственно верного способа" ни поделить единый сенсорный поток на разные "объекты", ни понять, что перед нами один и тот же объект. Схожие проблемы неединственности и нечеткости возникают и с понятиями "синонимов", с таксономиями, и т.д. и т.п. Судя по всему, они благополучно разрешены при помощи структуры, называющейся lattice-ordered monoid of concepts (далее LOMoC). В
работах А. Кларка (не Артура, а Александра, прошу заметить) эти идеи развиваются для парсинга естественных языков. К сожалению, в его статьях описывается странноватая модель обучения, в которой нужен учитель, ученик может выполнять вычислительно крайне громоздкие операции (что-то типа O(n
7), где n - количество известных ему примеров фраз языка), да и объем коммуникаций "учителя" с "учеником" тоже нездорово большой. Тем не менее, уже сейчас это на вид сильно лучше и иерархии Хомского, и подавляющего большинства других языковых моделей. Читать можно начинать с Cla10 (
pdf)
LOMoC серьезно использует тот факт, что мы работаем именно со строками, т.е. "топология" входа линейна, а не 0-мерна (вход - множество или мультимножество), не двумерна (изображение), и тем более не является экзотической (скажем, когда вход - совокупность последовательных двумерных изображений, которые иногда аннотированы строками или множествами тэгов).
Но аналогичные структуры можно по аналогии построить и для других топологий, заменив операцию свертки строки и контекста соответствующей операцией конкатенации связного подмножества входа и его локального контекста. Вот только степени полиномов станут совсем кошмарными. Тем не менее, давайте пофантазируем (пока что) и представим себе, что это сделано. Какую генеративную модель "естественных изображений" смогла бы "понять" такая система? (здесь и далее, чтобы понять, откуда я взял дальнейшее, вам придется прочитать Кларка и, главное, понять его; а если так, то с вероятностью по меньшей мере 25% вы сидите слева от меня за соседним компьютером)
Неплохую. Например, с одной стороны, она поймет, что бывают "глаза", "рты" и "уши", поймет, что "лицо" - это правильно расположенная совокупность оных, поймет на произвольном изображении "лица", где там что (не зная, как что называется, а просто выделив соответствующие концепты). В то же время она будет знать, что Мона Лиза - это не только "лицо", но и "картина" (в смысле принадлежности к соответствующему concept class), а также что это та же самая картина, что и на входе номер 1358 (в смысле принадлежности к еще более узкому концепту). По картинке разным, частично пересекающимся или включающим друг друга ее подмножествам она сопоставит разные концепты. Сможет, например, парсить детские рисунки, правильно понимая, на какой объект реального мира это похоже, или отличать фото человека от фото портрета этого человека, висящего на стене.
2) Ну а как же нам свести размерность полинома к необходимой нам для поточных realtime алгоритмов сложности expected O(n
1+epsilon), и заодно избавиться от необходимости в явном "учителе"? Для этого нам придется вспомнить, что есть такая чудесная штука, как locality sensitive hashes. В web search с их помощью, в частности, ищут плотные двудольные подграфы в ориентированных графах "кто на кого ссылается", и таким образом вычисляют спам. Это уже успешно решенная задача, и решается она за О(числа вершин). Посмотри теперь на другой граф, а именно вот какой. Он двудольный, в нем вершины - это контексты и подмножества входов, а ребра отвечают на вопрос "какие подвходы встретились в каких контекстах". Что такое плотный двудольный подграф в нем? Ой, да это же и есть "концепт" Кларка!
А все это значит, что нам не нужно строить этот граф в явном виде! Мы можем, выбрав правильный набор хэшей, обрабатывать входы потоком, создавая "концепты" на лету. Кроме того, мы приобретем за счет рандомизированности дополнительную устойчивость к редким случайным ошибкам, например, встречающимся нам "неграмматичным" фразам или изображениям и тп., и избавимся от необходимости в учителе.
Вот в общем-то и все. Пора писать medium AI.
Сейчас я активно мониторю новые статьи про locality sensitive hashing (см. вчерашнюю запись в этом же журнале), и занимаюсь на работе чем-то максимально близким, что нашлось - semi-supervised извлечением и классификацией объектов из пользовательских запросов по их контекстам. Естественно, я пользуюсь при этом гораздо более "прикладными" методами, но, тем не менее, эта вся идея работает, черт возьми, я это вижу глазами.
Тем не менее, парсить естественные языки, кажется, для первого этапа сложновато. Начать нужно, скажем, с распознавания изображений общего назначения по этой схеме. По изображению искать "смысловые" near duplicates для его частей в имеющейся базе. Не знаю, буду ли я этим заниматься, но это неважно. Не я так кто-нибудь еще, не к 2017, так к 2025-му.
![[personal profile]](http://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
![[livejournal.com profile]](http://www.dreamwidth.org/img/external/lj-userinfo.gif){kind=small}
