Золотой билет. P, NP и границы возможного. Лэнс Фортноу
проблемами занимается особая математическая дисциплина – машинное обучение. На первом этапе алгоритм получает большую обучающую выборку (в нашем случае – несколько тысяч примеров написания для каждой цифры). По ней он должен сконструировать относительно несложную модель, которая позволит корректно отличать одну рукописную цифру от другой. Хорошо натренированный алгоритм безошибочно распознает незнакомые цифры даже в том случае, когда обучение завершилось давно.
За последние двадцать лет в этой области удалось добиться впечатляющих успехов. Современные методы классификации данных позволяют анализировать уже не тысячи, а миллионы обучающих примеров. Распознавать теперь можно не только чеки; некоторые программы редактирования изображений умеют вполне сносно фильтровать фотографии по лицам. Сайты интернет-компаний (Amazon, Netflix, Pandora и многие другие) рекомендуют книги, фильмы и музыку, основываясь на ваших предпочтениях и истории покупок. Программы распознавания голоса и автоматического перевода, конечно, не выдерживают конкуренции с человеком, однако дают нам общее представление о смысле написанного или сказанного. Спам-фильтры избавляют нас от нежелательных сообщений, а автомобили к 2020 году научатся ездить практически без нашего участия.
Дальше, очевидно, все станет только лучше. С какого-то момента успехи и достижения польются непрерывным потоком. Значит ли это, что сбривать больше нечего?
Нет, не значит. Принцип Оккама гласит, что самое простое описание следует считать самым лучшим, однако не помогает нам это описание найти. Современные методы машинного обучения работают с данными довольно примитивной структуры; обычно это просто набор не связанных друг с другом свойств. Найти самое простое описание, т. е. создать небольшую эффективную программу (на каком языке, неважно), которая умела бы быстро классифицировать данные, – задача чрезвычайно трудная и принадлежит классу NP.
Урбанский алгоритм позволяет быстро решить любую проблему из NP, а значит, найти простую программу для классификации данных будет не сложнее, чем решить школьную задачку по программированию. От нас потребуется лишь подавать на вход большие обучающие выборки: всю остальную работу алгоритм сделает сам. Так мы сможем получить практически любые знания.
Мы уже знаем, что при помощи новых технологий можно победить болезни и усовершенствовать национальную американскую игру. Вернемся назад в будущее и посмотрим, как урбанский алгоритм изменил саму суть искусства.
Автоматизация творческого процесса
Урбанский алгоритм в сочетании с «бритвой Оккама» позволяет получить практически любые знания – например, понять, что делает картины притягательными, музыку – популярной, а слова – берущими за душу: ведь если P = NP, мы можем просто перебрать все потенциальные варианты. Так мы найдем процедуру распознавания гениальности, а она даст нам возможность быстро находить и гениальные произведения.
В 2022 году Демократическая партия проводила очередные праймериз в Сенат