September 17th, 2009

любопытно

RuSSIR

Вернулся с RuSSIR. Сам ничего не читал, только слушал. Краткий отчет: Eugene Agiсhtein жжот, за пять лекций тема моделирования пользовательского поведения и использования оного для повышения качества поиска раскрыта полностью. Несмотря на "академическое происхождение" лектора, почти все, о чем он рассказывал, отлично применимо на практике в самом что ни на есть Яндексе. Прямо сейчас садись и код пиши (чем, собственно, я и собираюсь заняться через пять минут).

Из докладов James G. Shanahan узнал что-то о том, какие вообще "высокотехнологичные" задачи существуют в интернет-рекламе. В двух словах: грамотное применение машинного обучения, линейного/нелинейного программирования и других милых техник позволяет сильно увеличивать CTR, более полно использовать рекламные площади, и меньше раздражать пользователей. Забавно, что системы рекламы в видеоиграх (то, с чем я несколько раз сталкивался в разных ролях) в этом смысле крайне примитивны, несмотря на свое относительно современное происхождение (а может быть, как раз поэтому). Не знаю, может быть, все уже изменилось, но полтора года назад уж точно все было так. Кому интересно, могу рассказать больше в личной беседе.

Проблема лекций Джимми состояла в том, что интересное занимало 30% времени, а остальное было посвящено всякой совершенно introductory математике. Нет, ну я все понимаю, но просыпаться в половине восьмого и идти на первую лекцию, чтобы послушать про градиентный спуск (да даже и про равновесие Нэша), это уж как-то чересчур.

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

Djoerd Hiemstra (имя читается как "Дьёрд", а фамилию, по его словам, не могут правильно прочитать даже голландцы, а я и тем более) рассказал немного о document language model. Приятные лекции, хотя и не содержавшие ничего особенно нового. Кроме того, он показал, как вылядит язык запросов к структурированным коллекциям, учитывающий релевантность результатов (если говорить грубо), и как на его основе можно небольшими скриптами вполне прилично (в смысле соотношения "цена/качество" уж точно) решать задачи вроде "система поиска фотографий экспертов по данной тематике" (скрипт не пользователь пишет, а разработчик, один раз; для пользователя это выглядит как обычный tab в поисковике). Если честно, мне эта демонстрация показалась гораздо более интересной в смысле применения в Enterprise and Desktop Search, чем весь одноименный курс, о котором я поэтому писать не буду.

Институт системного анализа, как обычно, рассказал про 85 крутейших семантических падежей (или в прошлый раз их было 17? цифру помню, но к чему она относилась, забыл). Если честно, мне кажется, что за несколько лет можно было придумать для демонстрации хоть один запрос, на который Экзактус отвечает лучше, чем мы, или чем big G. Или, если таких запросов не существует, то как-то, что ли, подумать и об этом. Но я, конечно, не специалист в семантических падежах.

Семинар РОМИП не понравился. Типичный отчет выглядит так: "мы сделали такое-то подмножество всем известных факторов ранжирования / признаков тематичности / критериев качества сниппетов, скомбинировали их таким-то простым методом, и получилось то-то, а эти результаты гораздо лучше, чем если бы мы вообще ничего не делали". И так подряд. Единственное, что мне показалось интересным - Паша Карпович рассказал про pfound, а Миша Лебедев про машинное обучение в построении сниппетов. Но про pfound все, кто в Яндексе работает, знают, а Мишу я и без всяких семинаров мог бы послушать.

Познакомился с учениками Школы Анализа Данных (бывшими? или все еще? почему-то вот это я пропустил мимо ушей). Отличная компания, просто зачет. Кроме этого увидел, как выглядит antilamer, а также узнал, кто такой max_b, и решил пару его задач. Понял, что общаться с теми, кто на пять-шесть лет младше меня, намного прикольнее, чем с людьми моего возраста. Видимо, я инфантилен.

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

Для меня эта неделя была самой полезной за последний год, совершенно точно.
любопытно

Да, и задачки, конечно

1а) (широко известная) Есть очень большой файл, в котором лежит очень много (точнее, 2N+1) целых 64-битных чисел. Известно, что в нем N пар одинаковых чисел, и еще одно "непарное". Требуется найти это самое "непарное" число за O(N) времени и O(1) памяти. Естественно, числа в паре не обязательно идут подряд - иначе было бы слишком просто.

1б) То же самое, но чисел 2N+2, и непарными являются два из них. Требуется найти оба.

2) (из другой оперы) Есть шахматная доска 8х8, любая клетка которой может быть покрашены в черный или в белый цвет. Разрешается взять любой квадрат 3х3 или 4х4, и перекрасить каждую клетку внутри этого квадрата в противоположный цвет. Верно ли, что из любой начальной раскраски таким образом можно получить одноцветную доску?