Алгоритмы *

В этом году в московском офисе Яндекса пройдёт юбилейная 25-я конференция Combinatorial Pattern Matching — главное в мире событие в области алгоритмов на строках.

Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:

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

В соседнем посте была приведена интересная задача, условие которой звучит следующим образом:

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

На ближайшее время позволим себе абстрагироваться от точных численных значений и положим вероятность того, что бриллианты зашиты, равной p, а количество стульев — n.

Хотите узнать правильное решение этой задачи? Добро пожаловать под кат!

Часто за собой замечаю, что при виде какой-нибудь программы, игры или сайта у меня возникают странные мысли. И мысли эти меня пугают. А думаю я всякий раз о том, как эту программу/сайт/игру можно подхачить, взломать, обойти защиту, автоматизировать, расширить функциональность. Наверное, профессиональная деформация дает о себе знать. Или это подсознательное желание использовать накопленные знания, не находящие применения на работе. Как правило, эти желания остаются на уровне мыслей, но бывают исключения. Об одном таком случае я и расскажу вам сегодня…

Сегодня в App Store вышло обновленное приложение Яндекс.Перевода для iOS. Теперь в нем есть возможность полнотекстового перевода в офлайн-режиме. Машинный перевод прошел путь от мейнфреймов, занимавших целые комнаты и этажи, до мобильных устройств, помещающихся в карман. Сегодня полнотекстовый статистический машинный перевод, требовавший ранее огромных ресурсов, стал доступен любому пользователю мобильного устройства – даже без подключения к сети. Люди давно мечтают о «вавилонской рыбке» – универсальном компактном переводчике, который всегда можно взять с собой. И, кажется, мечта эта постепенно начинает сбываться. Мы решили, воспользовавшись подходящим случаем, подготовить небольшой экскурс в историю машинного перевода и рассказать о том, как развивалась эта интереснейшая область на стыке лингвистики, математики и информатики.



«Это все делает машина», «Электронный мозг переводит с русского на английский», «Робот-билингва» – такие газетные заголовки увидели читатели ликующей прессы 8 января 1954 года. А днем ранее, 7 января, научный компьютер IBM 701 принял участие в знаменитом Джорджтаунском эксперименте, переведя около шестидесяти русских фраз на английский. «Семьсот-первый» использовал словарь из 250 слов и шесть синтаксических правил. И, конечно же, очень тщательно подобранный набор предложений, на которых проводилось тестирование. Вышло настолько убедительно, что восторженные журналисты со ссылками на ученых заявляли о том, что через несколько лет машинный перевод почти полностью заменит классический «ручной».

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

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



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

Реализация алгоритма минимакс на примере игры «Собери 4» очень увлекательное занятия и, в связи с этим, появилось желание рассказать об этом увлечении еще кому-нибудь, что и сделал. Игра доступна по данному адресу.

Поле игры можно варьровать, устанавливая константы, я принял 7 на 6 как в примере по ссылке. Смысл игры заключается в том, чтобы, совершая ходы, выстроить 4 своих фигуры (крестики или нолики) в один ряд: по горизонтали, вертикали, диагонали. Для создания игры (видимо любой) необходимы две вещи: генератор ходов и анализатор ходов (позиций).

Сегодня речь пойдет о том, какую роль в Интернет-поиске играет лингвистика. Чтобы поместить это в контекст, начну с того, как связаны между собой лингвисты и большая поисковая компания, например, «Яндекс» (более 5000 чел.), «Гугл» (более 50 000 чел.), «Байду» (более 20 000). От трети до половины этих людей работают непосредственно на поиск. Лингвисты внутри этих компаний примерно поровну делятся между поиском и остальными направлениями — новостями, переводом и т.д.



Я сегодня буду говорить о той части лингвистов, которая пересекается с поиском. На диаграмме она обозначена штриховкой. Возможно, в Google и других компаниях все устроено немножко иначе, чем у нас, тем не менее, общая картина примерно такая: лингвистика является важным, но не определяющим направлением работы поисковых компаний. Еще одно важное дополнение: в жизни, конечно, границы расплывчаты – невозможно сказать, например, где заканчивается лингвистика и начинается машинное обучение. Каждый лингвист, работающий в поиске, немного занимается программированием, немного — машинным обучением.

Идея

1. Игровое пространство — клетчатое поле ограниченное рамкой
2. Существующие типы клеток:
   • Пустая клетка — белый
   • Стена — чёрный
   • Зверь — красный
   • След — коричневый
   • Дом — зелёный
3. Перемещение зверя оставляет неисчезающий след
4. При запуске генерируется лабиринт
5. Зверь знает состояние соседних клеток и на основании этого строит карту при перемещении
6. При перемещении зверь расходует силы, которые восстанавливаются в доме(+5) или на любой клетке(+1)
7. При столкновении звери объединяются в стаи(дома переносятся в соседние точки), если несколько зверей одновременно отдыхают в доме их карты объединяются
8. (Не реализовано)Разные «кланы» случайным образом объединяются или воюют
9. (Не реализовано)Генетический алгоритм для различных поведений зверей, случайно перемешивающиеся при размножении(+мутации), более перспективный вид выживет в войнах

Думаю многие из нас, хотя бы однажды интересовались искусственным интеллектом и нейронными сетями. В теории нейронных сетей далеко не последнее место занимает факторный анализ. Он призван выделить так называемые скрытые факторы. У этого анализа есть много методов. Особняком стоит метод главных компонент, отличительной особенностью которого является полное математическое обоснование. Признаться честно, когда я начал читать статьи по приведенным выше ссылкам — стало не по себе от того, что я ничего не понимал. Мой интерес поутих, но, как это обычно бывает, понимание пришло само по себе, нежданно-негаданно.

Реализацию порядко-независимой прозрачности (order-independent transparency, OIT), наверное, можно считать классической задачей программирования компьютерной графики. По сути, алгоритмы OIT решают одну простую прикладную задачу – как нарисовать набор полупрозрачных объектов так, чтобы не беспокоиться о порядке их рисования. Правила смешивания цветов при рендеринге требуют он нас, чтобы полупрозрачные объекты рисовались в порядке от дальнего к ближнему, однако этого сложно добиться в случае протяженных объектов или объектов сложной формы. Реализация одного из самых современных алгоритмов, OIT с использованием связных списков, была представлена AMD для Direct3D 11 еще в 2010 году. Скажу откровенно, производительность алгоритма на широко доступных графических картах тех лет не произвела на меня должного впечатления. Прошло 4 года, я откопал презентацию AMD и решил реализовать алгоритм не только на Direct3D 11, но и на OpenGL 4.3. Тех, кому интересно, что получилось из этой затеи, прошу под кат.

Реми Кулом (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото Ёды

В 1994 году компьютер обыграл чемпиона мира по шашкам, в 1997 году — по шахматам. Сегодня компьютеры превосходят людей абсолютно во всех популярных играх с полной информацией, кроме одной — го.

У классической игры с 2500-летней историей очень простые правила, но компьютерные программы даже близко не могут подобраться к победе над лучшими гроссмейстерами, пишет Wired.

Языки, на которых пользователи интернет-поиска составляют свои поисковые запросы, появились на наших глазах. Лексически они слабо отличимы от более привычных нам языков, например, русского или английского, и в начале своего существования совпадали с родительскими языками. Но языки поисковых запросов быстро отошли от родительских и обзавелись собственными наборами идиом, синтаксисом и даже особыми «частями речи». Небольшой размер и простота их грамматик, а также возможность изучать полное множество высказываний, порожденных на таких языках, делают их идеальными модельными объектами для тестирования моделей усвоения языка.

Я провел небольшое исследование того языка запросов, на котором пользователи обращаются к поиску Яндекса, и на его основе подготовил доклад. Как это часто бывает, вопросов осталось больше чем ответов. Однако результаты получились достаточно интересными.



Хотелось бы также поблагодарить Елену Грунтову за одну из основных идей для исследования и помощь в подготовке доклада.

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи — 2010 г.) эвристический метод под названием «Метод прямого и обратного следования» ( Forward and Backward Reaching Inverse Kinematics, далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.

Этот пост про относительно новый метод обработки сигналов, описанный в статье Adaptive data analysis via sparse time-frequency representation, а также про крохотную, но сбившую лично меня с толку, ошибку. Сию статью опубликовали в 2011 году профессора прикладной математики Калифорнийского Технологического института Томас И. Хоу и Ши Цзоцян, и, вероятно, к моменту, как вы это читаете, они уже её поправили.
На эту статью я наткнулся в поиске различных методов частотно-временного анализа нелинейных и нестационарных сигналов — в моем случае ультразвуковых сигналов от передвигающихся форменных элементов крови в сосудах человека. Суть такого анализа состоит в отслеживании изменений характеристик сигнала, иначе говоря, мы хотим знать зависимость составляющих сигнал частот от времени. За исключением широко распространенных методов — спектрального и вейвлет-анализа, были найдены такие методы как EMD (разложение на эмпирические моды) и синусоидальное моделирование, о котором далее пойдет здесь речь.
Метод эмпирических мод довольно прост в применении, однако не особо развит с точки зрения обоснованности полученных результатов. Томас Хоу и Ши Цзоцян пошли дальше в развитии математического аппарата и предложили свой метод синусоидального моделирования сигнала. Его идея заключается в разреженной декомпозиции сигнала на гармоники с гладкими амплитудами. Какой результат мы ожидаем получить — на картинке выше. В данном случае раскладывался сигнал, полученный функцией f(t) = 6t + cos(8πt) + 0.5 cos(40πt). Разложение сигнала, естественно, не уникально, поэтому был введен критерий минимума составляющих гармоник, и задача сформировалась следующим образом:

В данной статье мы рассмотрим процесс разработки методики контроля предвыборной агитации в Ростовском региональном сегменте Интернет-СМИ с использованием обработки естественного языка и машинного обучения.
Также я остановлюсь на особенностях и нюансах, ведь задача стояла довольно специализированная: необходимо было выделять агитацию, и, если она может нарушать закон — оперативно уведомлять Избирком. Забегая вперед скажу, что с задачей я успешно справился.

В задаче разработки методики контроля предвыборной агитации в Ростовском региональном сегменте Интернет-СМИ применяются наработки из нескольких смежных областей знаний:

• автоматизированная обработка текстов (текстмайнинг),
• обработка естественного языка,
• машинное обучение.

Время бежит очень быстро, и такой популярной игрушке (и не только игрушке!), как Кубик Рубика, исполнилось уже 40 лет. Эта головоломка была создана Эрне Рубиком в 1974 году, а запатентована, им же — в 1975.



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

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

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

Анализ неявных предпочтений пользователей, выраженных в переходах по ссылкам и длительности просмотра страниц, — важнейший фактор в ранжировании документов в результатах поиска или, например, показе рекламы и рекомендации новостей. Алгоритмы анализа кликов хорошо изучены. Но можно ли узнать что-то ещё об индивидуальных предпочтениях человека, используя больше информации о его поведении на сайте? Оказывается, траектория движения мыши позволяет узнать, какие фрагменты просматриваемого документа заинтересовали пользователя.

Этому вопросу и было посвящено исследование, проведенное мной, Михаилом Агеевым, совместно с Дмитрием Лагуном и Евгением Агиштейном в Emory Intelligent Information Access Lab Университета Эмори.




Мы изучали методы сбора данных и алгоритмы анализа поведения пользователя по движениям мыши, а также возможности применения этих методов на практике. Они позволяют существенно улучшить формирование сниппетов (аннотаций) документов в результатах поиска. Работа с описанием этих алгоритмов была отмечена дипломом «Best Paper Shortlisted Nominee» на международной конференции ACM SIGIR в 2013 году. Позже я представил доклад о результатах проделанной работы в рамках научно-технических семинаров в Яндексе. Его конспект вы найдете под катом.

Если у вас или у ваших клиентов почтовый ящик на mail.ru, будьте готовы к неприятностям.

Немного истории

Исторически сложилось так что почта mail.ru особо не пользовалась популярностью среди ИТ-шников и технарей, как и сама компания в целом. Но в последнее время компания изменилась в лучшую сторону, ребята собрались и сделали отличный почтовый сервис, перешли на HTTPS, даже успешно перевели почту на UTF-8. Недавно вот еще «Облако» сделали бесплатное на 1ТБ, и даже изменили к нему лицензионное соглашение. Ну и много всего у них происходит хорошего. Но

«не будем говорить о плохом, а лучше сделаем»

 цитаты великих людей :)

Вернемся в настоящее

Все администраторы у кого есть «сайт / блог / форум» наслышаны о проблемах с доставками писем в ящики для пользователей mail.ru, я их не оправдываю, ведь в большинстве случаев у них плохо настроен MTA, нет DKIM подписей, нет правильной PTR-записи, и все их письма «успешно» валятся в спам. («успешно» без сарказма). Но команда антиспама решила не останавливаться на таких примитивных проверках как валидные цифровые подписи DKIM, обратные записи PTR, «трастовость» домена и исходящего сервера и многое другое что используют бесплатные сервисы с устаревшей антиспам системой (eg. Yandex, Google, Yahoo), команда антиспама отказалась от этих проверок, и начала использовать настоящую магию!

Иногда возникает необходимость ускорить вычисления, причем желательно сразу в разы. При этом приходится отказываться от удобных, но медленных инструментов и прибегать к чему-то более низкоуровневому и быстрому. R имеет довольно развитые возможности для работы с динамическими бибиотеками, написанными на С/С++, Fortran или даже Java. Я по привычке предпочитаю С/С++.