plakhov: (Default)
Смотрите сегодня в нашей программе: [Cосиска], [Горбачев] и [Кони]
plakhov: (Default)
За восемнадцать лет существования интернет-поисковиков их сложность выросла на несколько порядков. В 1993 году полноценную (на тот момент) поисковую машину можно было создать в одиночку, сейчас в Яндексе работает 3000 человек, в Baidu - более 6000, в Yahoo - почти 15000, в Google - около 25000.

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

Счастливый пользователь ничего этого, конечно, не видит. Он, как правило, "мгновенно" получает всё те же десять ссылок с небольшими текстовыми аннотациями, и волен наивно думать, что поисковики в 2011 году работают точно так же, как и в 1995. Само по себе это хорошо: не стоит чинить то, что не сломано. Тем не менее, чем дальше, тем более парадоксальная складывается ситуация: Яндекс знает и понимает больше, чем показывает пользователю. Мы хотим сократить этот разрыв, и научить поисковик не только искать, но и общаться с человеком сложнее и умнее, чем это делается сейчас.

Если у вас светлая голова, вы хорошо знаете С++ (о да), живете в Москве или согласны переехать, и хотите поучаствовать в таких проектах - приходите.

Сейчас я торжественно расскажу, почему это работа мечты. Очень много субъективного, уж простите.

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

2) Здесь очень много умных людей и очень мало глупых (я уж не знаю, испытываете ли вы от этого такой же кайф, как и я). Даже если судить по формальным признакам - тут несколько докторов наук и несколько десятков кандидатов. Тут как Червоненкис, так и несколько человек, про которых есть именные статьи на луркморе. Еще это первое известное мне место работы, где действительно пригождается математическое образование (ну, положим, не когомологии де Рама, но матстат, дискретная математика всякая, анализ, и даже теория групп таки да, не говоря уже о machine learning'е).

3) Яндекс - идеальное место, если вы не видите перспектив в своей текущей индустрии. Поскольку тут часто приходится заниматься чем-то новым, чем-то, чего раньше вообще никто не делал, понятие "опыта работы" часто плохо определено. "Зажечь" может и новичок.

4) Здесь хорошо платят и есть куча всяких плюшек. По ссылке написано, что "оклад... заведомо не ниже среднерыночных условий в нашей отрасли". Что такое "среднерыночные условия" я, на самом деле, не знаю, поскольку давным-давно не заглядывал на сайты, где про них можно прочитать. По-моему, это само по себе хороший признак. Еще тут не капают на мозги, не стоят с секундомером, нет бюрократии, допускается свободная форма одежды и произвольное время прихода на работу.

5) (не главное для меня, но кому-то, может быть, пригодится) В Яндексе феноменально много умных и красивых девушек, и есть внутренний dating-сервис с фотками!

Если мне удалось правильно запудрить вам мозги, присылайте резюме через эту форму: http://company.yandex.ru/job/vacancies/dev_search_developer.xml

Если вы хотите удостовериться, что будете заниматься именно тем, о чем написано во вступлении, а не чем-нибудь другим (честности ради вынужден написать, что тут, в общем, и много где еще есть интересные задачи), напишите в комментариях что-нибудь вроде "хочу к Плахову".
plakhov: (Default)
В последние годы всё больше вещей на компьютере делаются онлайн, и всё меньше оффлайн. И некоторые вещи относительно последнего меня всё больше удивляют.

(подразумевается, что всё ниже перечисленное происходит на компьютере с хорошим постоянным подключением к интернету, потому и удивительно; удобно держать в голове аналогию "программа = сайт, операционка = поисковик")

0) Программы нужно инсталлировать! А перед этим - покупать! Мало того, о них нужно откуда-то еще узнать до этого! А если программа тебе не понравилась, её потом нужно специальным образом удалять!
1) Чтобы пользоваться собственным компьютером, нужно знать и помнить гораздо больше, чем для любого нормального места в интернете (да и чем для них для всех вместе взятых). В Сети по сравнению с этим можно жить, не приходя в сознание.
2) Практически нигде автоматически не исправляются опечатки; даже неверную раскладку исправляет разве что какая-то сомнительная сторонняя программа.
3) Саджеста нигде нет. Каждый раз, когда Полина сохраняет рисунок, и пишет в качестве названия что-нибудь вроде "кот и со", я ожидаю, что сейчас в drop-down появится "кот и собака". Не появляется.
4) Там, где саджест есть, он убогий. Не знает, в общем-то, ничего, кроме названий имеющихся на моем компьютере файлов. Диалог открытия файла подсказывает (и потом открывает) файлы только из текущей директории - даже если я уже начал вводить название, а в этой директории нет такого файла! Даже то, что он всё-таки подсказывает, по релевантности не упорядочивается. Не понимает, что "фильмы" - это длинные видеофайлы. Не знает, что "my documents" и "мои документы" - одно и то же.
5) Музыкальный проигрыватель радостно сообщает, что файл Manowar - 01 - Wheels Of Fire.mp3, находящийся в папочке Music/Manowar/1988 - Kings Of Metal исполняет неизвестный исполнитель в неизвестном жанре, альбом неизвестен, и неизвестно зачем это вообще слушать

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

Bing-Sting

Feb. 2nd, 2011 01:08 pm
plakhov: (Default)
Напишу о вчерашнем скандале. Весьма скользкая тема, поэтому лишний раз напомню, что мой блог отражает мое личное мнение, вовсе не обязательно совпадающее с официальной позицией моего работодателя. Также заявляю, что все глупости - мои личные, а все умные мысли принадлежат коллегам.

Стоит сразу предупредить, что "большие ребята" до сих пор спорят между собой о том, как всю эту историю воспринимать. При этом многие люди, разбирающиеся в проблеме куда как меньше, уверены, что им-то всё понятно. Я не хочу ругаться словами на букву Х, но после чтения некоторых комментариев возникает именно такое искушение.

Итак, Google официально обвинил Bing (конкурирующую поисковую систему, написанную в Microsoft) в том, что Bing "списывает" у него результаты. Обвинил не голословно. Решающий эксперимент, доказывающий *нечто* (что именно, мы обсудим ниже), выглядел следующим образом: инженеры Google искусственным образом модифицировали выдачу по нескольким бессмысленным словам вроде indoswiftjobinproduction, на тот момент в интернете вообще не встречавшимся, добавив на первую позицию какую-то совершенно невинную страничку (естественно, не содержавшую эти слова). Дальше несколько (порядка двадцати) сотрудников Google разошлись по домам, оттуда задали эти запросы и кликнули на (синтетические) первые результаты. Сразу несколько комментаторов этот момент почему-то пропустили: в заявлении Google недвусмысленно говорилось, что на результат они кликали. Это важно (почему - ниже). Делалось всё это при помощи Microsoft Internet Explorer со включенными настройками и дополнениями, позволяющими браузеру отправлять в Microsoft данные о посещенных сайтах, не нарушая при этом пользовательских соглашений.

Через две недели по некоторым из этих запросов ровно те же результаты появились в выдаче Bing, что и позволило Google сделать свое заявление.

Что, предположительно, происходит: при переходе (клике) на определенную страничку или встроенная фича браузера под названием Suggested Sites, или Bing Toolbar передает в Microsoft информацию, что на такую-то страничку пользователь пришел по такой-то ссылке. Пока что это совершенно нормальное поведение, оно описано в пользовательском соглашении, и позволяет реализовать некоторые фичи браузера/тулбара, без этого невозможные. Тот факт, что сотрудники Google на результаты кликали, позволяет утверждать, что собственно поисковую выдачу браузер не парсил (если бы это было не так, вряд ли Google отказал бы себе в удовольствии поставить "некликающий" эксперимент, после чего иметь неплохие шансы засудить Microsoft, в отличие от текущей ситуации).

В Microsoft полученные данные обрабатывались, и, если referrer указывал на страницу результатов поиска Google, сохранялись в виде "мы знаем, что по такому-то запросу Google показал такую-то страничку, и пользователь на неё кликнул", после чего начинали влиять на ранжирование результатов в Bing. А вот это уже выглядит очень некрасиво, правда? К счастью, всё закончилось хорошо, Bing получил отличный щелчок по носу, силы Добра наказали силы Зла (пусть не юридически, но хотя бы публично унизив), и т.п., да?

К сожалению, это далеко не конец истории.
Представим на секунду, что все клики во всех поисковиках нам известны. Как можно было бы их использовать?

Способ А) "Если мы знаем, что по этому запросу наша выдача плохая, давайте добавим в неё кликабельные результаты из выдачи конкурентов по тому же запросу". Технически это совершенно элементарно, и автоматически затыкает все "дырки" и ошибки с полнотой индекса, синонимами, опечатками, результатами, переведенными с других языков, и т.д. и т.п.

Способ Б) Предположим, мы используем какие-то пользовательские факторы ранжирования в работе своего поисковика. Для решения вопроса о том, как упорядочить первые 20 результатов, мы считаем эти пользовательские данные не только по данным о поведении "своих" пользователей, но и по данным о поведении пользователей конкурентов.

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

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

Теперь о том, почему, если все начнут активно использовать способ Б, поиск не только не ухудшится, а совсем даже наоборот. Дело в том, что сейчас web-поиск - индустрия, очень тяготеющая к установлению монополии. Если в поисковике А ищут 50% пользователей, а в поисковике Б - только 10%, то у поисковика А впятеро больше данных о пользовательском поведении. Это очень серьезный гандикап, фундаментально влияющий на качество поиска, практически непреодолимый. Что еще хуже, чтобы запустить новый поисковик, которым прямо сейчас ищут 0% пользователей, нужно... нужно что? Я даже не представляю. Можно быть семи пядей во лбу, собрать супер-команду, написать идеальный код, придумать какие-нибудь новые мега-фичи (вроде социального поиска), но отыграть существующую безумную фору это вряд ли поможет. Еще раз - не потому, что вы хуже умеете искать; вы можете при прочих равных условиях искать гораздо лучше, вот только "невидимая рука рынка" этого не поймет, потому что этих "прочих равных условий" у вас никогда не будет. Таким образом, повсеместное использование способа Б улучшит качество поиска у всех, и одновременно усилит содержательную конкуренцию. Хорошо? Конечно, хорошо!

Неоднозначность вчерашнего скандала состоит в том, что:
1) В Microsoft использовали и не А и не Б, а нечто среднее между ними.

2) Эксперимент, проведенный Google фактически проверял не то, "этичный" или "неэтичный" вариант поведения имеет место, а то, влияют ли данные о переходах с других поисковиков на полноту индекса Bing (а не только на ранжирование). Он очевидно свидетельствует о том, что да, влияют; к сожалению, это совсем не то, что на самом деле хотелось бы знать.

3) Заявления Google содержат крайне двусмысленные утверждения. Разумеется, их полностью устроила бы ситуация, при которой публика будет считать аморальным вообще любое использование пользовательских данных, собранных из иных источников, нежели логи серверов поисковой системы, поскольку такая "конвенция" сделала бы их "вечной монополией". В итоге Singhal говорит, например, следующее: "The PageRank feature sends back URLs, but we’ve never used those URLs or data to put any results on Google’s results page. We do not do that, and we will not do that". Строго говоря, эти слова можно понять так, что они будут правдивыми (смотря что понимать под "put any results" и под "that"), но, как мне кажется, для 99% людей они звучат как "мы не используем в ранжировании данные, собираемые Хромом и тулбаром", что совсем уж неправда.

Всё это не радует и не даёт возможность по итогам однозначно зачислить Google в "силы Добра", а Microsoft в "силы Зла".

As a sidenote, хотелось бы отметить, что маркетинг и вообще организационная структура Google невероятно круты; я не знаю, в какой другой компании смогли бы задумать, провести и идеально обыграть подобную "спецоперацию", правильно выдержав все сроки, подобрав нужные скриншоты, выверив тексты и содержание заявлений и т.п., чтобы произвести подобный ошеломляющий эффект. Во всяком случае, не в Microsoft, судя по их запоздалым и "беззубым" ответам.

Ссылка для самостоятельного изучения и отслеживания развития всей этой истории (англ.): http://searchengineland.com/google-bing-is-cheating-copying-our-search-results-62914
plakhov: (Default)
Стивен Вольфрам сравнил, как различные поисковики справляются с заданиями из Jeopardy! ("Своей игры").

Стивен не то чтобы самый надёжный источник информации, к тому же, конечно, этот пост в первую очередь является (не очень скрытой) рекламой Вольфрам.Альфы; но цифры, которые он там приводит, меня удивили - и не столько тот факт, что Яндекс (английская версия которого является даже не бетой, а альфой) в них выглядит весьма достойно, сколько тот, что он в них вообще присутствует в качестве одного из примеров modern search engine landscape.

С чем всех коллег и поздравляю. :)
plakhov: (Default)
Что вы искали в интернете, но не смогли найти?
plakhov: (Default)
http://www.wolframalpha.com/input/?i=average+penis+length

Я вот не понимаю, а как Вольфрам себе представляет процесс озарения "действительно, не ввести ли мне в математический поисковик такой вот запрос"? То, что на него будет дан ответ, отличный от "Wolfram|Alpha does not yet know how to respond to your exact query", это тайное знание, которое должно передаваться из уст в уста (чёрт, какие-то не те коннотации)?

Когда они запускались, я был уверен, что у Стивена есть хитрый план, и постепенно простым смертным вроде меня станет понятно, что на самом деле Альфой офигенно удобно пользоваться, и что она в чем-то потеснит традиционные поисковики. Не может ведь быть такого, чтобы автор New Kind of Science и Mathematica не понимал очевидных вещей.

Черт, я даже повелся "на слабо", и научился парсить википедию и "умно" отвечать на запросы вроде [самый низкий баскетболист] (из тех, рост которых указан в википедии, но об этом мы вслух не будем говорить). Убил месяц, наверное. Как вы думаете, какое количество пользователей задает такие запросы, насколько надежные получаются ответы, и стоит ли это количество внедрения хрупкой и экзотической "базы знаний"? Праавильно.

В итоге у меня лично получалось извлечь пользу из wolphram|alpha только при помощи запросов вроде http://www.wolframalpha.com/input/?i=x^5%3Dx+%2B+1 (таким образом я узнал, на какую именно экспоненту похожа функция f, для которой f(n) = f(n-4) + f(n-5)). Целых три раза! Думаю, это больше среднестатистического количества. И даже так работает, к сожалению, далеко не всегда.

Например, я выяснил для себя, что функция, задаваемая простым рекуррентным соотношением f(n) = f(n/2) + f(n-1) растёт быстрее любого многочлена, но медленнее любой экспоненты. f(1) равно, скажем, 1. Если n не делится на 2, можно округлять в любую сторону, неважно.

Интересный зверь; может быть, про него давно известно больше?
http://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%28n%29+%3D+f%28n%2F2%29+%2B+f%28n-1%29
(сообщает нам Альфа, попыхивая трубкой)

В общем, как-то я в недоумении.
plakhov: (Default)
Запустили систему, над которой я работал последний год. За это время я успел её сначала полюбить, а потом возненавидеть (не переставая любить).

Технология "Спектр"

Здесь могу рассказать некоторые технические подробности, которые в официальный пост не вошли.

Система исследует запросы всех пользователей Яндекса и выделяет в них различные объекты
Тут произошла интересная вещь. Самым мощным источником информации для построения этой онтологии оказываются результаты выделения в массе поисковых запросов типичных "контекстов" и "концептов". Позже я ознакомился с работами A.Clark и некоторых других авторов, и оказалось, что этот сигнал неспроста. Подобный "парсинг" представляет собой некоторое (естественно, пока что крайне примитивное) приближение к тому, как человеческие существа учатся разговаривать на естественных языках. Такие вот 2017-дела.

Естественно! поверх всего этого работает много ручных правил всяких, фикслистов ("бензопила такая-то это не автомобиль" и т.п.), хаков, "чтение" википедии происходит по совершенно другим правилам, производится финальный проход совсем уж прямо алгоритмом Ахо-Корасик по заголовкам и снипетам готовых результатов в поисках спамоглупостей, и т.д. и т.п. Но все равно интересно, что из этого всего может выйти в прекрасном далёком.

поиск Яндекса максимизирует вероятность того, что человек найдет именно то, что искал
Это предложение описывает не столько результат, каким его хотелось бы видеть :), сколько процесс: используется честная вероятностная модель пользователя и его поведения, и выдача составляется таким образом, чтобы максимизировать некоторое матожидание в этой модели. Если обозначить количество url'ов на первой странице выдачи за N, то сложность этой процедуры экспоненциально растет с увеличением N (задача является NP-сложной, кроме шуток). К счастью, N, как правило, равно 10, к тому же простой "жадный" алгоритм для неё работает хорошо.

Эта вероятностная модель схожа с яндексовской метрикой pfound, о которой и Паша Карпович, и Илья Сегалович уже рассказывали в разных местах, и даже называется похоже. Она используется не только в текущем запуске, но и во многих других местах, где приходится иметь дело с тем, что разные пользователи хотят видеть в выдаче разные вещи (например, хоть как-то приближает к пониманию того, как определить, насколько уместны русскоязычные результаты в результатах украинского поиска). Я не могу сказать, что прямо изобрёл её (после некоторого количества размышлений такая модель кажется самоочевидной, так что её не раз переизобретали, а "о чем-то таком" в отделе качества поиска думали, наверное, вообще все), но всё-таки довел её до состояния named entity и популяризовал внутри компании.

И про название. Практически "всю дорогу" технология называлась "Разнообразием" ("Diversity"). Переименовать решили ближе к концу, когда после анонса во внутренней рассылке выяснилось, что "разнообразие" люди склонны понимать слишком буквально, и ожидают увидеть выдачу не сбалансированную по потребностям пользователей, а именно что максимально разнообразную. А "Спектром" при этом внутри называли совсем другую штуку. Ну что, всё как всегда.

Upd. Огромное спасибо прекрасной [livejournal.com profile] petsen, которая героически менеджила проект всё это время, проводила со мной ликбез насчёт всяких лингвистических тонкостей, уговаривала меня оставить одни безумные идеи и всерьез рассмотреть другие, ну и вообще подымала боевой дух. И Грише привет! :)
plakhov: (Default)
Я сегодня видел рекламный ролик конференции поисковых оптимизаторов, и вот что подумалось.

Смогли бы мы объяснить умному человеку, жившему 10000 лет назад (тогда тоже жили очень умные люди), что такое деньги? Конечно, смогли бы. А что такое магазин? Наверное, это ненамного сложнее.

А что такое онлайн-магазин? Здесь уже, конечно, не обойтись без потери смысла, но, во всяком случае, концепция магазина, в котором можно рассмотреть потенциальную покупку через специальное окошко, позволяющее видеть на огромном расстоянии, и заказать доставку этой покупки, в голове вполне помещается. Условно скажем, что это второй уровень вложенности новых понятий.

Отлично, теперь выясняем, что такое поисковые системы (ограничимся "коммерческими" запросами). Это третий уровень вложенности. Теперь нам нужно рассказать, что такое SEO. Это четвертый. Затем мы рассказываем, что такое конференция SEOшников. И, наконец, что такое рекламный ролик для конференции сеошников. Получится, что нужно пройти как минимум шесть уровней причинно-следственных отношений, иногда весьма нетривиальных, пока мы не дойдем до понятного физического результата этих действий, выразимого в "биологических терминах".

Но это еще что. Оптимизатор может, например, купить себе кусочек ботнета, чтобы скачивать выдачу без капчи. Это же какой уровень вложенности вообще, как бы не десятый?

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

sets

Sep. 4th, 2010 05:10 pm
plakhov: (Default)
Google Sets офигенный. Одна из немногих существующих технологий, аналог которой я не очень понимаю, как сделать.

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

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

Нет, я верю, что это такой тестовый полигон, что этой запчасти можно найти тучу применений, которые пользователям незаметны, но поиск улучшают. Скажем, бесплатные тематические классификаторы. Непонятно только, зачем её в таком случае наружу светить.

brainstorm

Sep. 1st, 2010 09:13 pm
plakhov: (Default)
Очевидно, что именно российский поисковик должен показывать на первом месте по запросу, скажем, [в контакте]. Как и по запросу [одноклассники], как и по запросу [google]. Таких полным-полно, и задают их миллионами (называется "навигационные запросы").

Как вы думаете:
1) А что показывать в остальной десятке? Ссылки на клоны и аналоги? Обзорные статьи о том, что это за сайт, о его фичах, статистике и т.п? Порно и бесплатную музыку? Всё сразу?
2) Десятка результатов по таким запросам вообще нужна? Если нет, то что показывать вместо неё?
(идея по таким запросам сразу отправлять пользователя на искомую страницу a la "I'm feeling lucky" мне известна, она плохая по ряду причин, хотя один клик и экономится)

Поскольку я не дизайнер, а значит, мало могу повлиять на п.2, интереснее, конечно, мысли про п.1
Но если что-то офигенное придумаете про п.2, тоже интересно.

SIGIR-2010

Jul. 28th, 2010 10:23 pm
plakhov: (Default)
На прошлой неделе побывал на SIGIR. Это такая конференция по "поиску информации". Если последние два слова кажутся вам расплывчатыми и могущими означать что попало, то отбросьте сомнения - вам не кажется, так оно и есть.

Ситуация примерно следующая. Конференция начиналась больше тридцати лет назад, когда с интернетом в мире было не очень, и была посвящена library science, то есть по сути науке о том, как бы так библиотекарям правильнее вести архивы, индексы и картотеки, чтобы наиболее эффективно удовлетворять потребности ученых и аналитиков, приходящих к ним со своими странными запросами вроде "а что бы мне почитать про математику древнего Вавилона". Если точнее, участвовали в конференции адепты молодой и нахальной ветви этой науки, утверждавшие (здесь я ради веселья и троллинга всё несколько упрощаю), что для этого достаточно знать, сколько раз какое слово входит в какой документ, и использовать КОМПЬЮТЕРЫ, а всякие там "ключевые слова", тематические индексы, вручную построенные выжимки и иные плоды труда рабов почти бесполезны, т.к. поиск по ним проигрывает не то что tf/idf или не дай бог BM25, а даже простейшим vector space model (это метод, который только звучит научно, а на самом деле сводится к тому, что тот документ у нас будет релевантнее, в котором слова запроса удельно встречаются чаще).

Ссылались они при этом на Cranfield Experiments, которые доказали в общем-то ровно преимущество простых, тупых и идеально автоматизируемых методов (было это еще в шестидесятых годах, когда компьютеры поиском информации особенно не занимались). То, как эти эксперименты были организованы, очень похоже на то, как тестируют и сравнивают поисковики сейчас во всяких TREC'ах и ROMIP/РОМИП'ах: есть набор документов (коллекция), есть набор запросов, и есть набор оценок, составленных вручную - какой набор документов какому запросу релевантен; этого достаточно, чтобы верифицируемо сравнивать результаты работы разных методов поиска. В итоге получилось то, что получилось - общепринятые патентованные методы (тм) никакой пользы не приносят. Автор экспериментов сомневался, стоит ли публиковать эти результаты, ибо боялся, что ему никто не поверит, и это в лучшем случае. Совершенно справедливо - скажем, для диссертации и по сей день приходится честно заполнять примерно стопиццот разных custom fields вроде "тематики" и "ключевые слова"; не знаю, пользуется ли ими кто-нибудь для поиска, но если и пользуется - сам себе злобный буратина. Забавно, что в комментариях у avva буквально в прошлом году появлялись гневные сторонники классической library science, и смешивали с грязью все эти ваши новомодные гугли и википедии, которые, по их мнению, и рядом не лежали со старой доброй универсальной онтологией "библиотечного классификатора"; про cranfield paradigm, которая за пятьдесят лет стала настолько общим местом, что на этой конференции ее чуть не объявили замшелой и устаревшей, они, судя по всему, не слышали.

Хорошо, в 1978 году идеи автоматически искать информацию при помощи компьютеров (а не специально обученных библиотекарей), строить инвертированный индекс, и, страшно сказать, применять при этом вероятностные модели, были новыми и обещали произвести революцию (что характерно, произвели). Прошло 30+ лет, и, пусть кому-то это нравится, а кому-то нет, люди ищут информацию в интернете на пять порядков чаще, чем в библиотеках. И как же изменился SIGIR, чтобы отразить эту смену реальности, и зачем туда ездят люди из Яндекса, Microsoft Bing, Yahoo, Google, и прочих интересных компаний, хотите вы спросить (а может, и не хотите). А также наверняка вам интересно, во сколько обойдутся такси и хот-доги в Женеве, и зачем в отеле "Интерконтиненталь" стоит двуспальная кровать в коридоре возле бассейна. Обо всем этом завтра, а сейчас Полина (см. юзерпик) выгоняет меня из-за комнефпм ПАНТЕРА КИТТИ КИТТИ

untranslit

Jul. 1st, 2010 03:53 pm
plakhov: (Default)
Пишут, что научились расшифровывать древние языки:
http://web.mit.edu/newsoffice/2010/ugaritic-barzilay-0630.html
(пишет, в частности, [livejournal.com profile] vitus_wagner)

Это не совсем расшифровка языка. Это возможность, зная русский язык, понять вот такой текст:

Poslali amerikancі shpiguna na Ukraїnu: navchili movі, odjagli v nacіonal'nij odjag. Jde vіn selom.
- Dobrogo ranku, dіdusju!
- Zdrastuj, amerikans'kij shpigune!
- Dobrogo ranku, babusju!
- Zdrastuj, amerikans'kij shpigune!
- Dobrogo ranku, hlopchiku!
- Zdrastujte, djadju amerikans'kij shpigune!
- Da zvіdki zh vi uzjali, wo ja amerikans'kij shpigun?
- Bo ti, sinochku - negr.

(анекдот рассказал [livejournal.com profile] ygam)
Мой пример даже чуть сложнее того, что они сделали для угаритского языка: научились сопоставлять алфавиты (при условии, что оба фонетические, и что такое сопоставление возможно провести взаимно-однозначно, что неверно уже в случае транслита), и научились после этого находить в тексте "знакомо выглядящие слова" (умильно выглядит оговорка - “Of those that are incorrect, often they’re incorrect only by a single letter, so they’re often very good guesses” - а чего они еще хотели-то с этим методом?)

Так что пока не AI.
plakhov: (Default)
Консервативный сценарий, то есть, если сингулярности не случится.
Появление аналогичных web-поисковикам, и не менее продвинутых, систем, ориентированных на отдельные, более узкие области. Чтобы это имело смысл, области гораздо лучше монетизируемые (в пересчете на одного пользователя, естественно).

1) Переход ученых от текущей системы индексов цитирования, которая afaik всех достала, на несколько конкурирующих систем "поиска экспертов по тематике", построенных по принципу web search: множество факторов ранжирования, зависимость рейтинга от "запроса", закрытые алгоритмы, антиспам в явной форме (кто не верит, что это кому-нибудь нужно - меня после доклада на мехмате об этом спросил профессор в контексте "не собираемся ли такое делать"! русский профессор!)

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

3) Adult matching (идея [livejournal.com profile] pg). Подбирать пары для знакомств с различными целями. :) Сам алгоритм подбора state of the art, то есть machine learning, факторы, обучающая/тестовая выборка и т.п. Должно работать гораздо лучше, и чем брачные агентства, и чем всякие там современные мамбы.

Наверное, можно и другие придумать. Жизнь покажет.

Можно было бы стартапчик организовать, но как-то не люблю этим заниматься (пробовал ~пять лет назад, крайне не понравилось), а в Яндексе хорошо, интересно, кормят, и есть обязательства.
plakhov: (Default)
Их неожиданно много.

Перечисляю в порядке убывания моей оценки того, насколько интересно было бы в нем поучаствовать сферическому читателю данного ЖЖ:
1) Яндекс запустил "Интернет-математику 2010". По-моему, она даже интереснее, чем прошлогодняя, и "ближе к жизни". Нужно предсказывать пробки в Москве.
2) Алёна разместила у себя вопросы для собеседования AI-программистов в игровой индустрии. Не соревнование, но использовать этот пост для того, чтобы померяться в комментариях, можно.
3) Yahoo запустил соревнование по ранжированию, как две капли воды похожее на яндексовскую "Интернет-математику 2009". Даже формат данных тот же самый.
4) Горячие уральские робототехники, о которых я недавно писал, тем временем допилили свой эмулятор робота, и свой вариант управляющей программы для него уже можно писать.
5) И, кстати, в "Интернет-математику 2009" по-прежнему можно сабмитить результаты, чем [livejournal.com profile] alsafr недавно и воспользовался для небольшого defacing'а таблицы результатов :)
plakhov: (Default)
1. Мне нужно срочно отучаться употреблять слово "внезапно".
2. Вот у вас в базе миллионов сто картинок, и вам нужно их поделить на группы полудубликатов. Это значицца что у нас такое. Хочется понимать, что resize, смена цветности, дополнительное лого в уголке, фильтр какой-нибудь и последующий copy-paste на новый хост не делает картинку новой - это та же самая картинка. Ну и когда пользователь в нее ткнет, выдавать ему сразу всю группу дублей, примерно так. Описывать всю эту задачу целиком со всеми деталями в посте я, конечно же, умру, поэтому сосредоточимся на самом вкусном.
Все проблемы - гвозди )

Ну и для порядка.
Disclaimer 1: поиск дубликатов в Яндекс.Картинках работает не так
Disclaimer 2: поиск дубликатов в текстах веб-страниц работает не так
meta-disclaimer: у нас вообще, кажется, ровно именно так ничего не работает
plakhov: (Default)
Господа математики, матлингвисты, machine learner'ы и прочие естественные интеллекты.

Расскажите мне, как искать би-клики в двудольных графах.
На эту тему есть всякая литература, например, Makino "New Algorithms for Enumerating All Maximal Cliques".
Проблема в том, что в ней везде предполагается, что граф нам известен в точности.

А на самом деле известно, что граф двудольный, и известен набор его вершин; но информация о наличии или отсутствии ребра не обязательно точна. По наблюдаемым данным можно, например, для каждого потенциального ребра вычислить оценку вероятности того, что оно присутствует в исходном графе, и доверительный интервал для этой оценки (для каждого ребра свой). Хочется уметь перечислять в нем все структуры, которые с высокой вероятностью являются bi-cliques.

Естественно, эта постановка не фиксирована жестко, умение решать какие-то «похожие задачи» тоже пригодилось бы.

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

OH SHI~

Dec. 24th, 2009 03:24 pm
plakhov: (Default)
Злостно нарушу NDA:

[finder@...]$ svn up
A skynet
A skynet/kernel
A skynet/tools
A skynet/api
U .

Не, ребята, ну нельзя же так явно-то!
plakhov: (Default)
Две недели назад в Google Official research blog была опубликована запись о сотрудничестве с компанией D-Wave, а конкретнее, об опыте применения квантового компьютера в задачах классификации изображений. Пост содержал примечательную фразу "in our experiments we observed that this detector performs better than those we had trained using classical solvers running on the computers we have in our data centers today".

Все это одновременно пугало и воодушевляло, и вызвало желание разобраться, что конкретно было сделано. Благо, пост содержал ссылки на статьи, в которых и метод машинного обучения, и сами эксперименты были описаны в подробностях.

Мой вывод вкратце: прорыва не случилось; маркетинг Google, кажется, совершил ошибку, "вписавшись" за D-Wave. Технические подробности в следующем посте.

Здесь немного пояснений для неспециалистов - чем квантовый компьютер отличается от обычного, и какое именно чудо нам обещали.

Электронные вычислительные машины стали привычными устройствами и никого, в общем, не удивляют. Никого не удивляет и прогресс в этой области. Десять лет назад вычислительная мощность компьютеров стабильно удваивалась каждые полтора года, и к этому все привыкли. Сейчас это уже не совсем так, но в рейтинге суперкомпьютеров продолжают появляться новые, более мощные, домашние устройства становятся удобнее, дешевле, мобильнее, обрастают ядрами процессора и специализированными картами для расчетов графики, физики, и т.д. и т.п.

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

Например, появление полноценных квантовых компьютеров означало бы необходимость полностью переделать современные схемы шифрования и электронной безопасности, так как "взлом" современных шифров после этого становится тривиальным. А ведь современная криптография - давно никакая не военная экзотика; на ее основе работают, например, соединение по протоколу https с веб-сайтами банков и интернет-магазинами, шифрование разговора по Skype, Java-апплеты, наконец, обычные банкоматы. Нет, ну и военные/спецслужбистские переговоры все-таки тоже, конечно.

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

Часть заявки Google и D-Wave состояла в том, что они смогли придумать для квантовых компьютеров "мирное применение" в реальных повседневных задачах распознавания и классификации изображений (и не только). Это было бы само по себе замечательно. Те самые "ядерные электростанции".

Но основным достижением было, конечно, то, что статьи и результаты якобы демонстрировали применение полноценного работающего квантового компьютера "почти промышленного" качества.

И вот тут начинается самое интересное. Дело в том, что, в отличие от обычного компьютера, квантовый - устройство совершенно магическое. Электронная вычислительная машина является, по сути, просто разогнанным в миллиард раз механическим арифмометром. За счет этого "умножения на миллиард" она выглядит очень умной и начинает уметь что-то нетривиальное, но логику ее работы все-таки можно понять от и до и объяснить "на пальцах", используя для этого всем привычные аналогии - счёты, шестеренки, etc.

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

Все попытки построить подобное устройство пока что выглядят достаточно жалко. Серьезными достижениями считаются прототипы прототипов прототипов, вроде последнего Йельского сверхпроводникового, на два кубита. На фоне этого многочисленные пресс-релизы D-Wave выглядят фантастически, и подтверждение их серьезности со стороны Google было как гром среди ясного неба. Жаль, что увы и ох.

Дальнейшие ссылки по теме для тех, кто хочет почитать об этом без математики и без технических подробностей:
Page generated Jul. 25th, 2017 06:53 pm
Powered by Dreamwidth Studios