понедельник, 22 марта 2010 г.

Впечатления от Computer Science E-days


С 19-го по 21-е марта в загородном учебном центре Аракуль на берегу одноименного озера прошла школа Computer Science E-days, организованная усилиями компаний СКБ-Контур, Яндекс и отделения Microsoft Research.

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

Были озвучены планы компаний-спонсоров сделать данное мероприятие регулярным. Но обо всем по-порядку.


Прежде всего стоит отметить, что школа проходила в красивейшем месте, расположеном в самых что ни на есть Уральских горах. Озеро еще покрыто льдом, летом здесь скорее всего еще красивее. Однако, мне понравилось обилие снега в сочетании с довольно теплой погодой.







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



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





Теперь непосредственно о том, что же было в программе школы. Прежде всего это конечно же лекции людей, непосредственно занимающихся CS в России: представителей МГУ, УрГУ и Лаборатории статистических методов Яндекса.

Первый день, 19-е марта

А. М. Шур рассказал о комбинаторике слов. Докладчик описал историю развития данной области знаний, описал уже решенные и еще открытые вопросы и проблемы. Естественно, аудиторию интересовал вопрос применения комбинаторики слов к практике программирования и решения каких-то алгоритмически сложных задач. Комбинаторика слов применима везде, где исходную последовательность данных можно представить в виде слова в некотором алфавите, например в биологии при анализе ДНК, т.к. ДНК - это слово в алфавите А, Т, Г, Ц (название нуклеотидов можете поискать сами :)

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

Андрей Райгородский, руководитель Лаборатории статистических методов Яндекса, рассказал о веб-графах и их моделировании. Лекция была очень понятна даже слушателям с минимальным владением темой (т.е. мне). Основные моменты: показана неприменимость классической модели случайных графов к веб-графам. Рассмотрены модели Боллобаши-Риордана (суть в том, что каждый новый сайт будет ссылаться на те сайты, на которые ссылаются и другие, а не на какие-то малоизвестные сайты) и Кумара-Томкинса (большинство новых сайтов имеют какую-то тематику и будут ссылаться на другие сайты по своей тематике, но есть и т.н. аморфные сайты, которым все равно на что ссылаться). Так как большинство аудитории если и не знали о теории случайных графов, то были в той или иной степени в курсе SEO и создания сайтов, доклад вызвал бурную дискуссию.

В кулуарах съезда Школы удалось пообщаться с Андреем Михайловичем за бокалом вина, узнать как можно попасть в его лабораторию на работу (впрочем, мне это не грозит), какие исследования ведутся в Яндексе, какие статьи публикуются, поговорили об академической и неакадемической науке (т.е. науке, спонсируемой компаниями, такими как Яндекс) и об аспирантуре в его лаборатории. Очень интересная и содержательная дискуссия.

После лекции состоялся круглый стол с представителями СКБ-Контура и Яндекса. Обе компании рассказали о своих академических программах. Представители СКБ-Контура много говорили о грантах молодым преподавателям в области IT, но они предназначены только для представителей Екатеринбургских вузов. Так же СКБ-Контур предлагает стипендии для студентов, которые что-то делают помимо учебы, например развивают какой-либо OpenSource-проект. Помимо этого есть гранты исследовательским коллективам (здесь я не совсем понял идет ли речь только о ЕКБ или об Урале в целом). Понравилось, что очень честно рассказали о своей мотивации: им нужны конкуренты, нужно пространство для обмена идеями, ну и конечно же квалифицированные специалисты, которым будет куда уйти из Контура, но при этом остаться в Екатеринбурге.

Яндекс предлагает конкурсы интернет-математика для выявления и поддержки талантливых исследователей, инженеров-программистов и людей, способных решать сложные задачи. Так же у Яндекса есть школа анализа данных. Заинтересовали программы стажировки для программистов, в том числе и удаленной стажировки. К сожалению, как сказал Илья Сегалович, программ научной стажировки в Яндексе все же нет. Кстати, академические программы Яндекса представлял Дэн Расковалов, один из первых авторов Naumen Kernel. Мир тесен, как бы банально это ни звучало.

Второй день, 20-е марта

Юрий Окуловский рассказал о развитии такой интересной области науки, как робототехника. На фоне был показан ролик про применение уже существующих роботов в качестве беспилотных летательных аппаратов, саперов, горничных, боевой техники и т.д. Показал робота, который с помощью видеокамеры получает информацию об окружающем мире, находит кубики и складывает из них пирамидку. Это выглядело забавно. Вообще, основная проблема робототехники - отставание возможностей "мозга", от "тела", т.е. инженеры научились создвать уже довольно высококачественные "тела" для роботов, но вот с управляющими системами пока увы.

Одной из самых сложных задач является обеспечение движения автомобиля, управляемого роботом, в городе. Уже решена задача управления автомобилем на трассе, на полигоне, но в реальном городе с лихачами, пешеходами и прочими блондинками обеспечить безопасное движение пока не удается. Здесь уместно было вспомнить трагически погибшего Томми.

Михаил Волков представил доклад о синхронизируемых автоматах. Суть в следующем: если для автомата возможно такое управляющее слово (т.е. последовательность управляющих воздействий), которое переводит его из любого состояния в четко заданное одно и то же состояние, то автомат называется синхронизируемым. Зачем это надо? Например мы отправили корабль на Луну, но он пропал за ее темной стороной и мы не знаем в каком состоянии находится его управляющий автомат, однако есть связь по командному каналу, соответственно, посылаем синхронизируещее слово и автомат переходит в известное нам состояние. В лекции была проведена параллель между автоматами и теорией кодирования. Интересно, что слайды были на английском языке.

Александр Куликов, координатор CS-клуба при Петербургском отделении математического института им. Стеклова, рассказал о том, что такое P и NP, какие задачи являются NP-полными и NP-трудными. Отметил, почему уменьшить основание степени в O(a^n) лучше, чем увеличить вычислительную мощность компьютера, на котором ведется рассчет. Самым интересным конечно был рассказ о применении неточных алгоритмов, однако и имеющих уже полиномиальную сложность. Т.е. в некоторых задачах, нам достаточно не точного, а оценочного результата, найти который можно за полиномиальное число шагов, используя полиномиальную память. Были приведены примеры: задача о максимальном разрезе, задача комивояжера на метрическом пространстве и т.д.

После данного доклада был перерыв, в котором можно было принять участие в стрельбе из лука. Огневая позиция выглядела примерно так:



Антон Конушин прочитал лекцию про семантическую сегментацию изображений. Если коротко, то есть две задачи: поиск объектов на изображении и разделение изображения на сегменты с определением их семантики. Под поиском объектов понимается определение присутствует ли заданный объект на заданном изображении и если присутствует, то каковы его границы. Наиболее часто искомыми объектами являются человеческие лица, пешеходы и автомобили. Была показана интересная демка - едет автомобиль и в поле зрения водителя определяются все пешеходы, в том числе и движущиеся.

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

Андерей Райгородский рассказал о веб-графах и применении их в ранжировании. Кто хоть немного знаком с SEO, знает, что основными факторами ранжирования сейчас являются ссылочные факторы, т.е. количество и качество ссылок, ведущих на сайт. Определяется это количество и качество с помощью такого параметра, как Page Rank (в случае, если мы строим граф постранично, если же похостово, то Host Rank). Был рассмотрен алгоритм рассчета Page Rank для веб-графа. В данном алгоритме есть сложность: нужно решить линейное уравнение с десятками миллиардов неизвестных на разреженной матрице. Кстати, именно поэтому Google пересчитывает Page Rank в среднем раз в шесть месяцев.

После введения понятия Page Rank была рассмотрена следующая интуиция: пусть пользователь ходит по сайтам и просто кликает на ссылки, имеющиеся на сайтах. Однако, пользователь ведь может и ввести что-то в адресной строке браузера. Т.е. перейти с сайта на сайт не по ссылке, а напрямую. Назовем это телепортацией и введем вероятность телепортации. Отразим ее в формуле рассчета Page Rank. Вот теперь можно экспериментировать, задавая эмпирические значения данной вероятности. Например, ТИЦ - тематический индекс цитируемости - задаем эту вероятность отличную от нуля, если сайт соответствует некоторой тематике и присваиваем нуль, если не соответствует. Другая возможность - Trust Rank и AntiTrust Rank. Суть в следующем: присваиваем нуль (соответвенно, не нуль) если мы не доверяем сайту и не нуль (соответственно, нуль), если доверяем (доверяем - математическая величина, вычисляемая по совокупности параметров, например, если домен .edu, то доверяем). Точных алгоритмов поисковых машин никто не знает (кроме их разработчиков), но есть мнение, что так работает Google.

В конце лекции была рассмотрена измененная модель Боллобаши-Риордана: при создании сайта будем ссылаться не на сайт, у которого больше ссылок, а на сайт, у которого больше Page Rank. Получим интересные результаты.

Далее состоялся круглый стол с представителем Microsoft Research в России и координатором CS-клуба при ПОМИ - Александром Куликовым. У Александра получился интересный рассказ об истории создания клуба, его инициативах, российских и международных школах по CS. К сожалению, доклад был вынесен в столовую и слушать/смотреть было неудобно. Сам стол затянулся и погряз в рутинных рассуждениях о технических деталях трансляции заседаний создаваемого клуба в Екатеринбурге. Какой смысл делить шкуру неубитого медведя, я не понял. Единственное, что понравилось - идея провести Software Engineering E-days.

Третий день, 21-е марта

Антон Конушин прочитал интересный доклад о методе грубой силы на основе больших коллекций изображений. Основная идея: анализировать картинку лучше при помощи других картинок. Интуиция метода такая: в интернете присутствуют миллиарды изображений. Подавляющее большинство из них не являются уникальными, например присутсвуют сотни, если не тысячи, фотографий Спасской башни Кремля или Мавзолея Ленина. Предположим, мы хотим вырезать участок изображения (например, мешающий нам автомобиль) и поместить туда что-то другое (например, себя любимого). Для этого нам нужно вырезать участок изображения, найти в интернете похожее на него (т.к. уже много изображений снабжено GPS-метками, то поиск упрощается) и подставить на нужное место нуный участок найденого изображения. Естественно, будут несостыковки по фону, освещенности и тени, но можно ввести и эти критерии в поиск. Так же сущесвуют методы сглаживания неровностей, в частности для фона используются методы из математической физики. Не обошлось и без демки: было показано изменение многих изображений, детально, в динамике. Это захватывает.

Так же Антон рассказал об методах поиска источника освещения для объекта и о том, что данный метод применяется для проверки факта фотомонтажа, причем успешно, несмотря на его математическую сложность.

Андрей Райгородский закрывал конференцию докладом о методах поиска неестественных структур на веб-графе. Суть в следующем: многие сайты используются для продвижения других сайтов (например, продают ссылки или являются сайтами-сателитами). Созданная с помощью таких сайтов неестественная структура называется "ссылочное кольцо". Впрочем, если раньше это и было кольцо, то сейчас это - двудольный граф, который необходимо анализировать. Существует опубликованный в печати алгоритм поиска таких структур на основе шинглов. Если честно, я не все ньюансы понял, но суть в том, что мы ищем сайты, ссылающиеся на множество других, не связанных друг с другом сайтов. По словам Андрея Михайловича, данный алгоритм работает и на веб-графе Яндекса находит десятки тысяч ссылочных колец. Правда не обходится и без курьезов: качество работы алгоритма зависит от двух констант, которые нужно подбирать эмпирически. Когда в Яндексе не умели подбирать эти константы, в найденые кольца попадал и сам сайт Яндекса, а также такие структуры, как Мой Круг. Такие факты приводят к тому, что невозможно банить любые сайты только на основе данных, полученных с помощью одного алгоритма. Все равно нужно, чтобы сайт был проверен человеком.

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

Рассказ будет неполным без выводов. Общее впечатление такое: безумно понравилось. На высоте была организация Школы. Впечатлил уровень докладов и докладчиков, стоит сказать особое спасибо тем, кто их приглашал. Конечно, почти все доклады были углублены в математику тех процессов, которые осуществляются с помощью компьютера, но углублены на минимально необходимый для их понимания уровень. В целом можно сказать, что компьютерная наука есть, компьютерная наука есть не только где-то, но и в России, а центры такой науки расположены в том числе и на Урале (имеется ввиду Уральский государственный университет и Яндекс.Екатеринбург). Стоит отметить, что такие наукоемкие компании, как Яндекс спонсируют развитие этой науки, причем не только в ее прикладном (выявим закономерность и внедрим ее), но и в фундаментальном (выявим закономерность, математически обоснуем и опубликуем статью) аспекте. Это очень радует.

Немного ссылок:

- официальный сайт Школы, на нем будут выложены все материалы докладов и фотографии.

- Хэштег Школы в Twitter.

Понравилось сообщение - подпишитесь на блог или читайте меня в twitter

Комментариев нет:

Отправить комментарий

Любой Ваш комментарий важен для меня, однако, помните, что действует предмодерация. Давайте уважать друг друга!