АРМАДА
Генераторы текста по цепям маркова.
Новая тема Написать ответ

Mauzer
Banned
Зарегистрирован: 17.09.2005
Сообщений: 20
Обратиться по нику
# Добавлено:Ср Сен 21, 2005 11:40 pmДобавить в избранноеОтветить с цитатой
Народ, объясните плиз что за цепи маркова и с чем их едят?
Почему их так любят генераторы доров?

Exploy
Грозный Модератор
Зарегистрирован: 01.09.2005
Сообщений: 2131
Обратиться по нику
# Добавлено:Чт Сен 22, 2005 5:08 amОтветить с цитатой
да...ты не тот маузер Laughing
нечего серьезный форум в непонять что позволять превращать (c) Rabbit

admin
Admin
Зарегистрирован: 02.07.2005
Сообщений: 1792
Star (Сумма: 2)
Обратиться по нику
# Добавлено:Чт Сен 22, 2005 8:08 amОтветить с цитатой
У того маузера ник вроде по другому пишется Smile



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

Max
Just max
Зарегистрирован: 22.09.2005
Сообщений: 3327
Обратиться по нику
# Добавлено:Чт Сен 22, 2005 8:35 amОтветить с цитатой
Посмотрите на умаксе, там наверняка это обсуждали не раз.
WESTCASH - Мы работаем для вас

Rabbit
Кролики - это не только ценный мех
Зарегистрирован: 01.08.2005
Сообщений: 19788
Star (Сумма: 1)
Обратиться по нику
# Добавлено:Сб Сен 24, 2005 12:31 pmОтветить с цитатой
Что такое «цепи Маркова»?

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

Через некоторое время он начинает прилично угадывать. Даже удивительно. А алгоритм основан на том, что датчик случайных мыслей (цифирок Smile) в человеке не случаен, а берет на вход предыдущие сгенеренные цифирки. И то, что следующим ходом человек сгенерит, определяется тем, какие цифры он сгенерил до того. И как ему компьютер отвечал (как вариант игры - он может угадывать втихую и не отвечать сразу, а отвечать потом).

Короче говоря, вся ситуация отслеживается на N ходов назад, и данные аккумулируются в таком виде: для каждой последовательности из N введенных ранее [0,1] считаем число введенных ПОСЛЕ этой последовательности единичек и число нулей. И считаем вероятность того, что человек введет следующим ходом. Если статистика по единичкам сильно больше, значит, «угадываем» единичку. Наоборот – ноль. Примерно одинаково – генерим случайно. А еще есть вариант игры с ответом «не знаю» в виде двойки, только тогда для эффективного угадывания данные накапливать дольше надо.

Вот такая простая скотина этот человек Smile. Сложным натурам можно на 3 хода назад отслеживать, простым – на 2.

Так вот цепи Маркова – это цепи событий. Они используются в жизни таких вариантах:

- когда надо посчитать некое стационарное состояние (распределение) при наличии ограниченного набора событий. Например, перескоки электронов по энергетическим уровням. Или перескоки юзера по матрице ссылок при расчете PageRank: http://www.yandex.ru/yandsearch?text=цепи маркова pagerank&stype=www
- Или когда надо предсказать поведение системы на основе ее нынешнего состояния. Тут используется понятно какая гипотеза - что развитие ситуации определяется тем, как она развивалась раньше на N ходов. Например, тот же текст может быть описан как последовательность и по ней выбрано слово, появление которого в тексте «следующим ходом» наиболее вероятно.
Так вот про текст и говорим. Слов, однако, гораздо больше, чем 2 (ноль и единица), поэтому эффективно угадать следующее слово не выйдет. А неэффективно, но грамматически связно – пожалуйста! Это и есть генерация по цепям Маркова.
***

Короче говоря, вероятности в случае генерации связного текста можно выбросить за ненадобностью… Алгоритм получается такой:

0) берем текст, разбиваем его по предложениям, а внутри каждого предложения выделяем последовательности из N (допустим, 2-х) слов и пишем в таблицу

1) Берем случайно одно из «первых» слов в предложении, и ставим эту пару как первую.

2) По второму слову в паре выбираем все те пары, в которых это слово идет первым и дополняем текст вторым словом

3) Идем к предыдущему пункту 2, не забывая иногда закрывать предложение (например, парами, которые встречаются в концах предложений)

Вот примерно так. Это дает грамматически связный текст в любых количествах. Для размножения можно использовать и вероятности появления той или иной последовательности, и увеличивать N, выбирая одно следующее слово по предыдущим N-1. И все цепочки слов (здесь: пары) встречаются в реальной жизни, а на пробивку по тройкам и N-кам слов никаких ресурсов у поисковика не хватит.

Источник: blog.promosite.ru
Новое. Прибыльное. Скоро!

V O V A N
Профессионал
Зарегистрирован: 06.08.2005
Сообщений: 610
Обратиться по нику
# Добавлено:Сб Сен 24, 2005 8:10 pmОтветить с цитатой
Rabbit, спасибо Smile
беплатный качественный хостинг для ЛЛ постеров. все вопросы в ICQ (272467978)

admin
Admin
Зарегистрирован: 02.07.2005
Сообщений: 1792
Star (Сумма: 2)
Обратиться по нику
# Добавлено:Сб Сен 24, 2005 10:19 pmОтветить с цитатой
Интересная статья.

amazon
Ломщик
Зарегистрирован: 31.07.2005
Сообщений: 623
Обратиться по нику
# Добавлено:Ср Сен 28, 2005 1:11 pmОтветить с цитатой
а, спасибо за статью, как раз в тему. Smile
No comments
Новая тема Написать ответ    ГЛАВНАЯ ~ АДАЛТ

Перейти:  





Генеральный спонсор



Партнеры