Рубрика «Алгоритмы»

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

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

Однако сейчас персональные рекомендации становятся “must have” для классифайдов (и не только) по всему миру. Мы хотим помогать пользователю в поиске того, что ему нужно. Уже сейчас всё более значительная доля просмотров объявлений на Avito производится с рекомендаций на главной странице приложений или рекомендаций похожих объявлений на карточке товара. В этом посте я расскажу, какие именно задачи решает наша команда в Avito.

Рекомендации на Avito - 1

Читать полностью »

Machine Learning: State of the art - 1

В 2015 году в мир искусства вошло новое слово: «инцепционизм» (inceptionism). Машины научились перерисовывать картины, а уже в 2016 Prisma скачали миллионы людей. Сегодня мы поговорим об искусстве, машинном обучении и искусственном интеллекте с Иваном Ямщиковым, автором нашумевшей «Нейронной Обороны».
Читать полностью »

С развитием нейросетей им придумывают всё более разнообразные способы применения. С их помощью обучаются автопилоты Tesla, а распознавание лиц используется не только для обработки фотографий приложениями типа Prisma, но и в системах безопасности. Искусственный интеллект учат диагностировать болезни. В конце концов, с его помощью даже выигрывают выборы.

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

«Человек» искусства: способен ли искусственный интеллект творить? - 1Читать полностью »

Привет, Друзья!

Я написал библиотеку поисков путей на произвольных графах, и хотел бы поделиться ей с вами: http://github.com/anvaka/ngraph.path

Пример использования на огромном графе:

Поиграться с демо можно здесь: https://anvaka.github.io/ngraph.path.demo/

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

Описание разных вариантов A* уже не раз встречалось на хабре. Мне очень понравилось вот это, потому повторяться в этой статье я не буду. Под катом расскажу подробнее почему библиотека работает быстро и о том, как было сделано демо.

Читать полностью »

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

Сложно ли сделать из мухи слона? - 1
Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
Бельгийский Королевский музей изящных искусств (Брюссель).

Читать полностью »

image

В моем школьном детстве одним из развлечений, помню, было заполнить в тетрадке в клеточку ходом коня какой-нибудь прямоугольник m x n. Обычно это был квадрат 10х10 и вот, закусив губу (высунув язык), вписываешь старательно циферки в клеточки. На очередном шаге понимаешь, что зашел в тупик и начинаешь все с начала. Это было давно и неправда, но, изучая язык Haskell, я наткнулся на эту задачу в общем перечне https://wiki.haskell.org/99_questions за номером 91.Читать полностью »

Достижения в глубоком обучении за последний год - 1

Привет. В своей статье я расскажу вам, что интересного произошло в мире машинного обучения за последний год (в основном в Deep Learning). А произошло очень многое, поэтому я остановился на самых, на мой взгляд, зрелищных и/или значимых достижениях. Технические аспекты улучшения архитектур сетей в статье не приводятся. Расширяем кругозор!

Читать полностью »

Padding Oracle Attack: криптография по-прежнему пугает - 1

Эту уязвимость чинят уже пятнадцать лет

В хабрапереводе текста четырёхгодовалой давности «Padding Oracle Attack или почему криптография пугает» была подробно описана атака на режим шифрования CBC. В этом режиме каждый очередной блок открытого текста xor-ится с предыдущим блоком шифротекста: в результате каждый блок шифротекста зависит от каждого блока открытого текста, который был обработан к тому моменту.

Padding Oracle Attack: криптография по-прежнему пугает - 2

Чтобы пропустить исходное сообщение (произвольной длины) через CBC-шифр, к нему дописывается MAC (хеш для проверки целостности, обычно 20-байтный SHA-1) и затем padding, чтобы дополнить открытый текст до целого числа блоков (обычно 16-байтных):

Padding Oracle Attack: криптография по-прежнему пугает - 3

Padding («набивка») состоит из одинаковых байтов, на единицу меньших своей длины: (0) или (1,1) или (2,2,2) или т.п.
Таким образом, получатель шифротекста должен

  1. расшифровать все его блоки;
  2. прочитать последний байт последнего блока, чтобы определить длину набивки и, соответственно, позицию MAC в открытом тексте;
  3. проверить корректность набивки и MAC.

В 2002 г. французский криптограф Серж Воденэ обнаружил в CBC уязвимость к атакам типа «padding oracle»: Читать полностью »

Представьте: вы открываете приложение, чтобы в очередной раз заказать такси в часто посещаемое вами место, и, конечно, в 2017 году вы ожидаете, что все, что нужно сделать – сказать приложению «Вызывай», и такси за вами тут же выедет. А куда вы хотели ехать, через сколько минут и на какой машине — все это приложение узнает благодаря истории заказов и машинному обучению. В общем-то все, как в шутках про идеальный интерфейс с единственной кнопкой «сделать хорошо», лучше которого только экран с надписью «все уже хорошо». Звучит здорово, но как же приблизить эту реальность?

Как мы обучали приложение Яндекс.Такси предсказывать пункт назначения - 1

На днях мы выпустили новое приложение Яндекс.Такси для iOS. В обновленном интерфейсе один из акцентов сделан на выборе конечной точки маршрута («точки Б»). Но новая версия – это не просто новый UI. К запуску обновления мы существенно переработали технологию прогнозирования пункта назначения, заменив старые эвристики на обученный на исторических данных классификатор.

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

Читать полностью »

В этой статье я хочу показать, как с помощью фреймворка Selenium Webdriver можно, исходя из данных Wikipedia, составить генеалогическое древо заданной персоны (например, легендарного основателя первой династии русских правителей Рюрика).

В статье будет рассказано, как определить имя персоны, вычислить ссылки на страницы детей персоны, а также будет построен алгоритм генерации генеалогического древа.Читать полностью »