Информационная энтропия слова

[Kors123]

Задача стоит определить по значению энтропии это набор хаотичных букв или слова алфавита. Как понимаю если значение энтропии набора букв большое то это хаотичный набор букв а если небольшой то это слово. Непонятно как рассчитать информационную энтропию слова английского алфавита. Не могу понять как рассчитать по формуле Шеннона энтропию конкретного слова. Сумма произведения логарифма вероятности буквы на вероятность буквы это и есть энтропия слова или это общее значение для алфавита или надо брать рамки суммы только буквы используемые в слове!?

[Евгений Машеров]

Если это практическая задача - как минимум, опираться на вероятности биграмм, иначе случайные перестановки распространённых букв будут приниматься за слова.

[ozheredov]

Энтропия Шеннона это энтропия распределения. Даже если абстрагироваться от того что распределение должно быть именно теоретическим, а не выборочным, и считать возможным пихать в формулу энтропии гистограмму, вас ждет фейл, т.к. по одному слову гистограмму не построить - мало букафф.

Предлагаемый подход: понятно, что слово (обозначаем за W) отличается от хаотического набора символов (обозначаем за S) тем, что случайно набрать слово сложно, а абракадабру просто. Т.е. энтропия у вас должна показывать различия в вероятностях набрать W и S, попрыгав попой по клавиатуре. Теперь рассмотрим частный случай. Для простоты моими символами будут 1 и 0 (у вас это 26 букв англ. алфавита).

Итак, пусть есть все возможные 3-хсимвольные комбинации и все они образуют слова, наделенные смыслом

000
001
010
011
100
101
110
111.

Тогда любая 3-хсимвольная комбинация будет словом, независимо от того, каким местом она набрана. Из чего следует, что энтропию слова невозможно определить, ориентируясь просто на его буквенный состав.

[mihaild]

Если задача прикладная, и язык известен - надо смотреть не на частоты, а на редакционное расстояние (с правильными весами) до слов из словаря.

Если задача теоретическая - то она недостаточно точно сформулирована.

[Евгений Машеров]

Необходимо знать распределение букв (а для практически полезной оценки как минимум биграмм) английского языка. Для каждого символа известна вероятность (для би-, три- и т.п. грамм - вероятность условная, при условии, что ранее были именно эти символы). Информация символа i, вероятность которого $p_i$ (условная вероятность, соответственно) равна $I=p_i\log_2p_i$. Суммарная информация по слову сравнивается со средней энтропией буквы. Если разница выше порога - это не слово, а шум.

[Kors123]

правильно ли я понял что для каждой буквы помимо вероятности необходимо рассчитать ее энтропию по формуле $I=p_i\log_2p_i$ после чего необходимо посчитать среднюю энтропию буквы в англ алфавите после чего для слова рассчитывается суммарная энтропия по той же формуле и сравнивается с средней энтропией буквы!?но сумма будет больше средней энтропии буквы примерно на количество символов слова или нет?!

[ozheredov]

Евгений Машеров
Проиллюстрируйте пожалуйста ваши рассуждения на примере слова FEAR

[Mihaylo]

ozheredov в сообщении #1218728 писал(а):

Проиллюстрируйте пожалуйста ваши рассуждения на примере слова FEAR

Энтропия - это текущее состояние незнания, мера неопределенности. Соответственно, если известно слово, то энтропия равна нулю, т.е. энтропия слова FEAR равна нулю. Правильнее говорить об энтропии неизвестного слова.
Когда речь идет об энтропии слова, то следует зафиксировать длину слова, например, слово из 4 букв. Иначе незнание длины слова увеличивает энтропию и слегка усложняет расчет.

Если вы не знаете распределение букв, то энтропия 4-буквенного слова равна $4 \cdot \log_2(1/26)$
Если вы знаете распределение букв, то энтропия 4-буквенного слова равна $4\cdot \sum_{i=1}^{26} (-p_i \log_2(p_i))$

Ну следует еще понимать, что это формулы усредненного количества информации (так как математическое ожидание).

[ozheredov]

Mihaylo
Т.е. энтропии слов simultaneously и aoeussllym... (дальше влом переставлять :) ) равны, да?

Не в обиду, но подход Евгений Машеров по крайней мере проистекает из осмысленной постановки задачи. Let's go развивать именно его.

[Mihaylo]

ozheredov в сообщении #1218904 писал(а):

Let's go развивать именно его.

Просто: буквы -> биграммы -> триграммы ->... -> $n$-граммы -> слова -> ... -> буквы + биграммы + триграммы + $n$-граммы + слова. В итоге используете что-то вроде формулы полной вероятности из теорвера, энтропии Шеннона и получите свою многокомпонентную сложную формулу... Потом возникнет желание учесть вероятность устойчивых словосочетаний, потом устойчивых предложений, абзацев, текстов, выкинет Вас на уровень тем, тематик, разделов наук и т.д. - все это влияет на истинную энтропию текста.

[Евгений Машеров]

Частотная таблица для букв английского языка есть, помнится, у Яглома и Яглома, таблицы для биграмм есть в Сети. При этом есть резон учитывать позицию буквы в слове, там распределение разное. Без учёта биграмм, только по вероятностям букв, одинаково правдоподобны с FEAR будут FREA, FARE, AFRE, AREF и вообще все 24 перестановки, а более всего словом будет казаться ЕЕЕЕ.
Выглядеть алгоритм может примерно так:
(слова выделены, например, пробелами)
Для каждой буквы считается условная вероятность. Для первой это вероятность данной буквы быть первой в слове. Для i-той вероятность при условии, что прежде были найденные уже буквы. То есть нужна таблица распределения первой буквы и для каждого номера условные вероятности букв при знании предыдущей (-щих если триграммы и более), при этом "конец-слова" считается ещё одной буквой. Для каждой буквы L вычисляется $I_i(L|l_1,l_2\cdots l_n)=-\log_2 P(L|l_1,l_2\cdots l_n,i)$ и суммируется. Сумма сравнивается с энтропией при случайном наборе букв.

[Mihaylo]

Можно знать очень много разных условных вероятностей, например, что слово начинающееся на "наход" заканчивается на "ка" или на "ить". Знание этих вероятностей ЧРЕЗМЕРНО СИЛЬНО влияет на энтропию (меру неопределенности) и без их учета расчеты крайне неточны. С другой стороны, сбор этих условных вероятностей - сложное и многообразное явление. На самом деле, человек может с полуслова угадать целое предложение, из вырванного контекста строится множество догадок, между строк читается необъятная информация... Это все отражает истинную энтропию, которую сложно рассчитать, эта энтропия намного ниже этих игр с буквами и биграммами.

Цитата:

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

[arseniiv]

Mihaylo в сообщении #1218961 писал(а):

Знание этих вероятностей ЧРЕЗМЕРНО СИЛЬНО влияет на энтропию (меру неопределенности) и без их учета расчеты крайне неточны.

Если рассматривается задача «насколько данное слово соответствует фонотактике и т. п. выбранного языка», всё проще. Если интересуют конкретные слова, которые носители считают существующими, лучше просто взять словарь. ТС нормально задачу, кстати, не поставил, так что ваша интерпретация не самая верная.

[Mihaylo]

arseniiv
Да, ТС просит энтропию слова, а фактически ему требуется вероятность слова. Энтропия равна нулю.

[Dmitriy40]

И всё же такой и множество похожих вопросов возникают например в сугубо практическом случае проверки/сравнения архиваторов, насколько они оптимально по сравнению с идеальным случаем сжимают текст.
А исходный вопрос, "является ли набор букв словом" вообще не решить без полного словаря всех слов (и словоформ если нужно), т.к. далеко не все осмысленные сочетания букв будут реальным словом. И считать вероятности биграмм и прочих составляющих лишь немного поможет отсечь явно неправильные варианты сочетаний букв, но до проверки условной вероятности последней буквы в слове нельзя будет точно сказать что это именно слово. И таблица частот для всех этих условных вероятностей займёт объём сравнимо с самим полным словарём (в виде дерева, по которому кстати её легко восстановить).