Несколько слов о "новых алгоритмах"

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

Несколько слов о "новых алгоритмах"

Сообщение pomidoroff Вт май 05, 2009 1:39 pm

Прочитал статью в любимом журнале (Без права на ошибку, Евгений Золотов, Компьютерра №781).

Классный парень Дмитрий Асонов выдумал новый алгоритм для борьбы с опечатками. Основан, насколько я понял, на статистике, получаемой из частоты встречаемости взаиморасположения слов, причем слова рассматриваются парами, то есть префикс - одно слово, суффикс - следующее за ним слово.

Ладно, журналисты не обязаны знать математику и понимать, что алгоритм не нов. Но в статье есть отзывы экспертов. Например: "алгоритм Дмитрия основан на так называемой взаимной информации (ВИ). Представьте, прошел мимо вас человек в военной форме, а потом человек с барабаном. ... Если ситуация повторяется много раз, они, к примеру, состоят в одном военном оркестре. ... Академик Мексиканской Академии наук, профессор Александ Гельбух".

Здорово! Ничего не знаю о том, существует ли действительно разработанная теория Взаимной Информации, однако знаю, что речь идет отнюдь не о новом подходе, и называется этот подход цепями Маркова. Данный подход часто используется для изучения внутренней связности рядов, являющихся дискретной реализацией какого-либо случайного процесса. Юмор состоит в том, что Марков, объясняя на пальцах теорию своих цепей, приводил в пример мексиканца Педро, который делает прогноз продаж в своем ларьке на завтра. В ларьке он торгует игрушками. Каких игрушек и сколько следует заготовить на завтра? Академия Мексиканских наук знает ответ!

Итак, цепи Маркова за авторством А.А. Маркова - младшего это, так сказать, исходники. Реализация же описана в книге Кернигана и Пайка "Практика программирования". Чтобы не быть голословным, приведу пространную цитату.

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

Элегантный способ выполнить подобную обработку - использовать технику, известную как алгоритм цепей Маркова. Ввод можно представить себе как последовательность перекрывающихся фраз; алгоритм разделяет каждую фразу на две части: префикс, состоящий из нескольких слов, и следующее за ним слово — суффикс (или окончание). Алгоритм цепей Маркова создает выходные фразы, выбирая случайным образом суффикс, следующий за префиксом; все это в соответствии со статистикой текста-оригинала (в нашем случае). Хорошо выглядят фразы из трех слов, когда префикс из двух слов используется для подбора слова-суффикса:
присвоить w1 и w2 значения двух первых слов текста
печатать w1 и w2
цикл:
случайным образом выбрать w3 из слов,
следующих за префиксом w1 w2 в тексте
печатать w3
заменить w1 и w2 на w2 и w3
повторить цикл

Наша программа прочтет отрывок английского текста и использует алгоритм markov для генерации нового текста, основываясь на частотах вхождения фраз фиксированной длины. Количество слов в префиксе, которое в разобранном примере равно двум, в нашей программе будет параметром. Если префикс укоротить, текст будет менее логичным, если длину префикса увеличить, наше творение будет походить на дословный пересказ вводимого текста. Для английского текста использование двух слов для выбора третьего дает разумный компромисс: сохраняется стиль прототипа и привносится достаточно своеобразия.


Далее в главе реализуется данный подход на нескольких языках программирования. Причем эти реализации умеют генерировать вполне внятный текст.

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

Вот некоторые говорят, мол, постепенно происходит выхолащивание всего: образования, инженерных знаний и прочего всякого такого. Но вот же человек, прочитал Кернигана и Пайка!

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

Не понятно мне только одно. Почему не называть вещи своими именами? А?
pomidoroff
 
Сообщения: 305
Зарегистрирован: Пт окт 19, 2007 11:11 am
Откуда: Москва

Вернуться в Общение

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron