Вручена премия Тьюринга — аналог Нобелевской премии в области информатики

Премия Тьюринга за выдающиеся достижения в области вычислительных наук учреждена полвека назад и ежегодно вручается Ассоциацией вычислительной техники (Association for Computing Machinery, ACM) — старейшей (основана в 1947 году) и крупнейшей (92 тысячи специалистов, по данным 2009 года) компьютерной ассоциацией со штаб-квартирой в Нью-Йорке. Сумма премии составляет 250 тысяч долларов. Спонсоры премии — корпорации Intel и Google.

Компьютерную «нобелевку» за 2010 год вручили профессору Гарварда Лесли Вэлианту за «вклад в теорию алгоритмов, включая теорию приближенно правильного обучения (PAC), теорию сложности перечисления и алгебраических исчислений, а также теорию параллельных и распределённых вычислений».

Звучит заковыристо, но на самом деле с практическими воплощениями этих теорий в той или иной форме регулярно имеет дело каждый пользователь компьютера, электронной почты и цифровых «мыльниц».

Лесли Вэлианту 61 год, он родом из Великобритании, где он закончил Имперский колледж в Лондоне и Уорикский университет, преподавал, а в начале 1980-х перебрался в Гарвард. Здесь в 1984 году им и был написан труд «Теория обучающегося» — «A Theory of the Learnable», который до сих пор цитируют все теоретики и практики прикладного программирования обучаемых систем.

Собственно, главным достижением Вэлианта стала теория приближенно правильного обучения — Probably Approximately Correct Learning (PAC-learning), в информатике известная просто как теория Вэлианта. Теория представляет собой математический анализ самообучающихся алгоритмов, учитывающий, что очень важно, их вычислительную сложность: то есть объем работ, который требуется для решения задачи и получения машиной вероятно наиболее истинной гипотезы за эффективное время, используя приемлемый (или даже жестко заданный) объем вычислительных ресурсов.

Отработав достаточное число учебных итераций, машина может научиться «предсказывать будущее», находя гипотезы, удовлетворяющие учебным данным.

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

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

Так что эти модели оставались довольно примитивными, неавтономными (машинам требовались шпаргалки), медленными, а качество обучения — низким.

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

Проще говоря, компьютеры в большей мере стали «думать по-человечески».

Практическим выходом теории Вэлианта стал целый кластер программного обеспечения, имитирующего работу интеллекта — от хорошо знакомых всем программ распознавания речи, работающих в реальном времени, до эффективных интеллектуальных алгоритмов, находящих наиболее релевантную информацию по запросу, а также эвристических спамовых фильтров, умеющих отличать «правильные» письма от «неправильных». Все эти технологии уже реализованы и активно используются, притом совсем недавно новый суперкомпьютер IBM Watson, наделенный системой искусственного интеллекта, понимающей вопросы, сформулированные на естественном языке, и находящей на них ответы в базе данных, принял участие в телевикторине «Jeopardy!» (российский аналог — «Своя игра») и обыграл соперников-людей, заработав 1 млн долларов.

Из пока нереализованных проектов Вэлианта остается распознавание компьютером беглой речи на лету.

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

Среди других достижений Вэлианта, отмеченных премией Тьюринга, его труды о параллельных и распределённых вычислениях.

Например, предложенная им система рандомизации маршрутов (randomized routing) оказалась эффективной в предотвращении «битовых заторов» и потерь данных в коммуникационных сетях.

В прошлом году премия Тьюринга была присуждена Чарльзу Тэкеру, создавшему в 1974 году первый персональный компьютер Alto и сеть Ethernet, а в 2008-м — Барбаре Лисков за вклад в теорию и практику объектно-ориентированного программирования.

Алан Тьюринг (1912–1954) — английский математик и криптограф, возглавлявший группу по взлому кода знаменитой немецкой шифровальной машины «Энигма». Тьюринг, разработавший абстрактную модель универсальной вычислительной машины, частным случаем которой являются все современные ЭВМ, а также концепцию искусственного интеллекта, считается одним из отцов-основателей современной информатики.