Завершение интервью с Алексеем Винокуровым. В сфере его профессиональных интересов – искусственный интеллект, Machine Learning (машинное обучение), Information Retrieval (поиск информации), алгоритмы обработки больших объемов текстов, видео и графической информации.
Его научная карьера состоялась в британских Университете Лондона (University of London) и Университете Саусхэмптона (University of Southampton). Сейчас он работает в частной компании в Кембридже.
Первая часть интервью с Алексеем Винокуровым об одном из центральных неразрешенных вопросов информатики доступна здесь
Дмитрий Крылов: Мне всегда казалось, что построение того или иного алгоритма не зависит от категории задач и ее принципиальной решаемости за полиномиальное время. Это ведь прикладные задачи с рецептом решения, – нет?
Алексей Винокуров: Построение алгоритма – нет, но было доказано что НП-полные задачи типа задачи коммивояжёра являются ключевыми. Эти задачи легко узнаваемы, решение «в лоб» состоит в простом «жадном» переборе вариантов, что сразу выдаёт сложность класса «экспонента». Все неполиномиальные (читай интересные или из реальной жизни) задачи сводятся к задаче коммивояжёра, например, задача о разложении N задач по M процессорам, необходимая для решения в любой многозадачной операционной системе. Любая подвижка в решении данных задач означает подвижку по всему классу «жадных» то есть неполиномиальных задач, то есть ценность подвижки умножается многократно. Не говоря о такой подвижке как решить за полиномиальное время-память. Отсюда и весь сыр-бор про гипотезу – можно ли решить или стоит оставить попытки?
Д.К.: Получается, что люди ищут эвристические решения задачам типа задачи коммивояжера и без доказательства этой теоремы, неясно, существует ли они вообще. Задача загрузки многопроцессорных машин это один пример. А что еще? Насколько я понимаю, сейчас много задач, связанных с обработкой информации в Интернете, и к ним большой интерес. Там есть такого же класса задачи, наверное. В принципе Интернет можно легко представить в виде графа, стало быть, навигационные задачи и классификационные задачи это тоже задачи типа коммивояжера?
А.В.: Именно так и есть. Сейчас попытаюсь навскидку вспомнить 5 или 6 классических НП-полных задач, сводимых одну к другой. Одна из них была с графом. В принципе сам коммивояжёр это задача с «взвешенным» графом. Каждое ребро имеет вес – расстояние от одного пункта до другого. Была задача на раскраску графа была: рёбра надо раскрасить так чтобы смежные рёбра имели разный цвет. Задача о вершинном покрытии – найти покрытие, то есть такой подграф, что каждая вершина исходного графа имеет с ним хотя бы одно общее ребро. Задача о клике тоже графная. И так далее…
Д.К.: Представим себе, что доказательство существует. Как бы это может изменить Интернет в ближайшие годы и десятилетия?
А.В.: Если доказано что можно, то криптологи взвоют, потому что окажется, что широкораспространённые алгоритмы с открытым ключом такие как RSA, лежащие в самой основе безопасного Интернета, вовсе не безопасные. Следовательно, пойдёт новый виток в развитии шифровальных алгоритмов. Тем временем, правда, нельзя будет по Интернету ничего сделать – даже безопасно купить книжку на «Амазоне». Ну, а остальные, не столь озабоченные безопасностью, наверное, обрадуются, – ведь огромный класс задач, включая задачи по поиску и обработке информации в Интернете, вдруг станут «умнее». Например, поисковики поумнеют на порядок. Станет легче искать себе виртуальных друзей по интересу – например, «френдов» в блогах, так как появятся умные алгоритмы, которые проанализировав контент вашего блога, предложат вам потенциальных товарищей. Кстати, это будет прогресс и для сайтов знакомств.
Д.К.: Расскажите, что еще интересного происходит в информатике. Над чем Вы работаете сейчас?
А.В.: Одним из интересных и перспективных направлений я считаю дальнейшее развитие Machine Learning (машинного обучения). В последние годы это направление очень активно развивалось, а началось всё с двух советских учёных, Вапника и Червоненкиса (тоже выпускника МФТИ, как и я), которые просто хотели найти оптимальный алгоритм разработки золотых и алмазных месторождений. А получилась целая сногсшибательная теория. По сути, это наука о том, как научить машину не просто распознавать, а именно предсказывать. Например, натренировав её на истории цены какой-нибудь акции на бирже, можно прямо извлекать выгоду из «умности» алгоритма, предсказывая цену.
Но это далеко не единственное приложение. Их тысячи. Например, в какой-то момент я занимался тренировкой машины на автоматическое подписывание текста под картинками. То есть на входе была относительно большая коллекция картинок с подписями, машина должна была «обучиться», то есть уловить какую-то закономерность, и, получив новую картинку, должна была каким-то образом выдать несколько слов, которые бы наиболее характеризовали данную картинку. Иногда получались весьма интересные результаты. Ну, это очень кратко.
Интересных приложений просто миллион, от «умных» пылесосов до военных роботов и машин, которые ездят без водителя.
Дмитрий Крылов, PhD, независимый эксперт по инновационным технологиям
