Исправляем опечатки с учётом контекста

Недавно мне понадобилась библиотека для исправления опечаток. Большинство открытых спелл-чекеров (к примеру hunspell) не учитывают контекст, а без него сложно получить хорошую точность. Я взял за основу спеллчекер Питера Норвига, прикрутил к нему языковую модель (на базе N-грамм), ускорил его (используя подход SymSpell), поборол сильное потребление памяти (через bloom filter и perfect hash) а затем оформил всё это в виде библиотеки на C++ со swig биндингами для других языков.

Читать дальше →

Турнир ИИ для промышленных роботов по Аэрохоккею

Всем известны соревновании двух ИИ в игре Go. А как на счет состязания ИИ в более динамичной игре требующей не столько вдумчивой стратегии, сколько тактики, оперативной реакции и скорости?

К примеру Аэрохоккей! Простая декартовая система перемещений 3 координаты + 1 угол, всего один орган влияния на игру (бита), следовательно нужна всего 1 рука. Берем 6-ти осевых промышленных роботов, ставим вместо игроков с двух сторон…


Читать дальше →

[Из песочницы] Автоматическая оценка качества статей Википедии на разных языках

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

Читать дальше →

[Перевод] Что общего у собеседования кодера и игры «Змейка»?

Если вы родились в 80-х или 90-х, то наверняка слышали о Snake. То есть, скорее всего, вы потратили безумное количество времени на своём Nokia 3310, выращивая огромную змею на мелком экранчике. Что ещё мы помним о телефонах Nokia? Их неразряжающийся аккумулятор, правда? Как такой «примитивный» телефон выдерживал долгие часы игры в «Змейку» без разрядки аккумулятора? Короткий (и неполный) ответ: всё дело в методе скользящего окна. Мы бы с радостью написали целую статью о Snake, но в этом посте мы всё-таки рассмотрим менее зрелищный, но тем не менее очень важный метод, и ответим на вопросы типа:
  • Почему мы и другие программисты считаем его фундаментальным алгоритмом?
  • Почему он так часто используется на технических собеседованиях?
  • Как он использовался в Snake и других «реальных» областях применения?
  • На какие самые популярные вопросы собеседований можно (лучше) ответить с помощью метода скользящего окна?
Если вы готовитесь к собеседованию, читаете статью из интереса, или хотите узнать что-то новое, то продолжайте читать. При этом вы можете спокойно пропускать лишнее и переходить к самым интересным разделам. NB: Если вас волнует только «Змейка» (и мы вас вполне понимаем), то можете перейти к самому концу поста. ...Далее...

[Из песочницы] Максимально просто про перебор комбинаций в реальных бизнес-задачах

Если начать искать материал про перебор комбинаций, возникает масса примеров как перебрать все сочетания всех букв или всех цифр. Но как создать все сочетания элементов матрицы, в которой заранее неизвестна размерность, не углубляясь в Иосифа Романовского и его «Дискретный Анализ», такого материала я не нашел, поэтому и решил написать его здесь. Вдруг кому-то понадобится.
Читать дальше →

[Перевод] Мой любимый алгоритм: нахождение медианы за линейное время

image

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

Amazon MTurk и Emotion Miner: краудсорсинг, большие данные, эмоциональные технологии

Давайте зададимся вопросом: в какой мере краудсорсинговые инструменты востребованы в сфере эмоциональных (и нейрокогнитивных) технологий? Каким образом можно собирать, размечать и предварительно обрабатывать большие объемы данных, опираясь на ресурсы толпы? В качестве показательных кейсов обсудим платформу Amazon MTurk и, в приложении к эмоциональной проблематике, проект лаборатории Neurodata Lab — Emotion Miner.

image
Читать дальше →

Micro-UART для МикроКонтроллера (ATtiny13A)

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


Речь пойдет о программной реализации UART, для микроконтроллеров AVR компании Atmel, интеллектуальной собственностью которой с некоторых пор владеет компания Microchip.
Читать дальше →

Как обучть мдль пнмть упртые скрщня

Недавно я натолкнулся на вопрос на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из wtrbtl получать water bottle, а из bsktballbasketball. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.


Вопрос меня заинтриговал, и я полез разбираться, какие алгоритмы и математика лежат в основе современных опечаточников (spell-checkers). Оказалось, что хороший опечаточник можно собрать из n-граммной языковой модели, модели вероятности искажений слов, и жадного алгоритма поиска по лучу (beam search). Вся конструкция вместе называется модель зашумлённого канала (noisy channel).


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


Читать дальше →


Последние посты