Премия Тьюринга за выдающиеся достижения в области вычислительных наук учреждена полвека назад и ежегодно вручается Ассоциацией вычислительной техники (Association for Computing Machinery, ACM) — старейшей (основана в 1947 году) и крупнейшей (92 тысячи специалистов, по данным 2009 года) компьютерной ассоциацией со штаб-квартирой в Нью-Йорке. Сумма премии составляет 250 тысяч долларов. Спонсоры премии — корпорации Intel и Google.<1>
Компьютерную «нобелевку» за 2010 год вручили профессору Гарварда Лесли Вэлианту за «вклад в теорию алгоритмов, включая теорию приближенно правильного обучения (PAC), теорию сложности перечисления и алгебраических исчислений, а также теорию параллельных и распределённых вычислений».
Звучит заковыристо, но на самом деле с практическими воплощениями этих теорий в той или иной форме регулярно имеет дело каждый пользователь компьютера, электронной почты и цифровых «мыльниц».
Лесли Вэлианту 61 год, он родом из Великобритании, где он закончил Имперский колледж в Лондоне и Уорикский университет, преподавал, а в начале 1980-х перебрался в Гарвард. Здесь в 1984 году им и был написан труд «Теория обучающегося» — «A Theory of the Learnable», который до сих пор цитируют все теоретики и практики прикладного программирования обучаемых систем.
Собственно, главным достижением Вэлианта стала теория приближенно правильного обучения — Probably Approximately Correct Learning (PAC-learning), в информатике известная просто как теория Вэлианта. Теория представляет собой математический анализ самообучающихся алгоритмов, учитывающий, что очень важно, их вычислительную сложность: то есть объем работ, который требуется для решения задачи и получения машиной вероятно наиболее истинной гипотезы за эффективное время, используя приемлемый (или даже жестко заданный) объем вычислительных ресурсов.
Отработав достаточное число учебных итераций, машина может научиться «предсказывать будущее», находя гипотезы, удовлетворяющие учебным данным.
Машина, таким образом, может сама, без подсказок, научиться угадывать правильный ответ — таковым, к примеру, может стать «улыбка» в серии «не улыбок», которую должна уловить цифровая «мыльница» (данная опция, знакомая многим обладателям данного устройства, тоже выросла из вэлиантовской «теории обучающегося»).
Важным условием теории Вэлианта является именно эффективность. Естественно, модели машинного обучения создавались и до этого, но уровень их накопительной сложности всегда провоцировал различные тупиковые рекурсии в алгоритмах обучения, когда определение правильной гипотезы оказывалось невозможным без подсказки, а также экспоненциальный рост вычислительных ресурсов уже на ранних стадиях обучения.
Так что эти модели оставались довольно примитивными, неавтономными (машинам требовались шпаргалки), медленными, а качество обучения — низким.
Вэлиант, использовав свои предыдущие математические наработки в теории сложности перечислений и алгебраических вычислений (в частности, им был предложен способ по надежному выделению класса функций, вычисляемых наиболее эффективно), разрешил это затруднение. Начиная с середины 1980-х в программировании обучаемых систем началась настоящая революция, поскольку были найдены инструменты, позволяющие искусственному интеллекту снижать свой уровень энтропии, полагаясь, так сказать, на собственные силы, а не внешние каналы упорядоченных данных (подсказки, сравнительные таблицы, рутинный перебор сценариев, и т. д.).
Проще говоря, компьютеры в большей мере стали «думать по-человечески».