Контекстное моделирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= '''''Контекстное моделирование''''' — ''оценка вероятности появления с…»)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(нет различий)

Версия 19:04, 31 декабря 2018

Определение:
Контекстное моделированиеоценка вероятности появления символа (элемента, пиксела, сэмпла и даже набора качественно разных объектов) в зависимости от непосредственно ему предыдущих, или контекста.


Определение:
Если длина контекста ограничена, то такой подход будем называть контекстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых контекстов [math]N[/math].

Оценка вероятности

Оценки вероятностей при контекстном моделировании строятся на основании обычных счетчиков частот, связанных с текущим контекстом. Если мы обработали строку [math]“кускувукус”[/math], то для контекста [math]“ку”[/math] счетчик символа [math]c[/math] равен двум, символ [math]в[/math]единице. На основании этого статистики можно утверждать, что вероятность появления [math]c[/math] после [math]“ку”[/math] равна [math] \dfrac{2}{3}[/math] , а вероятность появления [math]в[/math] равна [math] \dfrac{1}{3}[/math], т.е. Оценки формируются на основе уже просмотренной части потока.

Определение:
Порядок контекстной модели — длина соответствующего этой модели контекста . Если порядок [math]КМ[/math] равен [math]o[/math], то будем обозначать такую [math]КМ[/math] как [math]“КМ(o)”[/math]

Пример

Рассмотрим процесс оценки отмеченного на рисунке стрелочкой символа [math]л[/math], встречающегося в блоке [math]“молочное[/math]_[math]молоко”[/math]

рис. 1

Пусть мы используем контекстное моделирование порядка [math]2[/math] и делаем полное смешивание оценок распределений вероятностей в [math]КМ[/math] второго первого и нулевого порядка с весами [math]0.6[/math], [math]0.3[/math] и [math]0.1[/math]. Считаем, что в начале кодирования в [math]КМ(o)[/math] создаются счетчики для всех символов алфавита [math]\{“м”, “о”, “л”, “ч”, “н”, “е”,“\_”, “к”\}[/math] и инициализируются единицей; счетчик символа после его обработки увеличивается на единицу. Для текущего символа [math]л[/math] имеются контексты [math]“мо”[/math], [math]“о”[/math] и [math]“”[/math] (0-го порядка). К данному моменту для них накоплена статистика, показанная в таблице

Порядок [math]“м”[/math] [math]“о”[/math] [math]“л”[/math] [math]“ч”[/math] [math]“н”[/math] [math]“е”[/math] [math]“[/math]_[math]”[/math] [math]“к”[/math]
[math]КМ(0)[/math] Частоты [math]3[/math] [math]5[/math] [math]2[/math] [math]2[/math] [math]2[/math] [math]2[/math] [math]2[/math] [math]1[/math]
[math]КМ(0)[/math] Накопленные Частоты [math]3[/math] [math]8[/math] [math]10[/math] [math]12[/math] [math]14[/math] [math]16[/math] [math]18[/math] [math]19[/math]
[math]КМ(1)[/math] Частоты [math] — [/math] [math] — [/math] [math]1[/math] [math]1[/math] [math] — [/math] [math]1[/math] [math] — [/math] [math] — [/math]
[math]КМ(1)[/math] Накопленные Частоты [math] — [/math] [math] — [/math] [math]1[/math] [math]2[/math] [math] — [/math] [math]3[/math] [math] — [/math] [math] — [/math]
[math]КМ(2)[/math] Частоты [math] — [/math] [math] — [/math] [math]1[/math] [math] — [/math] [math] — [/math] [math] — [/math] [math] — [/math] [math] — [/math]
[math]КМ(2)[/math] Накопленные Частоты [math] — [/math] [math] — [/math] [math]1[/math] [math] — [/math] [math] — [/math] [math] — [/math] [math] — [/math] [math] — [/math]

Оценка вероятности для символа [math]л[/math] будет равна [math] q(л) = 0.1*\dfrac{2}{19}+0.3*\dfrac{1}{3}+0.6*\dfrac{1}{1} = 0.71 [/math]

Метод PPM

Описание

[math]РРМ[/math] относится к адаптивным методам моделирования. Исходно кодеру и декодеру поставлена в соответствие начальная модель источника данных. Будем считать, что она состоит из [math]КМ(-1)[/math], присваивающей одинаковую вероятность всем символам алфавита входной последовательности. После обработки текущего символа кодер и декодер изменяют свои модели одинаковым образом, в частности наращивая величину оценки вероятности рас­сматриваемого символа. Следующий символ кодируется (декодируется) на основании новой, измененной модели, после чего модель снова модифици­руется и т. д. На каждом шаге обеспечивается идентичность модели кодера и декодера за счет применения одинакового механизма ее обновления.

Пример

Имеется последовательность символов [math]“абвавабввбббв”[/math] алфавита [math] \{“а”, “б”, “в”, “г”\}[/math], которая уже была закодирована.

рис. 2
рис. 3

Пусть счетчик символа ухода равен единице для всех [math]КМ[/math], при обновлении модели счетчики символов увеличиваются на единицу во всех активных [math]КМ[/math], применяется метод исключения и максимальная длина контекста равна трем, т. е. [math]N = 3[/math]. Первоначально модель состоит из [math]КМ(-1)[/math], в которой счетчики всех четырех символов алфавита имеют значение [math]1[/math]. Состояние модели обработки последовательности [math]“абвавабввбббв”[/math] представлено на [math]рис. 3[/math], где прямоугольниками обозначены контекстные модели, при этом для каждой КМ указан курсивом контекст, а также встречавшиеся в контексте символы и их частоты.

[math]Символ[/math] [math]КМ(3)[/math] [math]КМ(2)[/math] [math]КМ(1)[/math] [math]КМ(0)[/math] [math]КМ(-1)[/math] [math]Шанс[/math] [math]Бит[/math]
[math]a[/math] [math] — [/math] [math]\dfrac{1}{2+1}[/math] [math] — [/math] [math] — [/math] [math] — [/math] [math]\dfrac{1}{3}[/math] [math]1.6[/math]
[math]б[/math] [math] — [/math] [math]\dfrac{1}{2+1}[/math] [math] \dfrac{1}{1+1} [/math] [math] — [/math] [math] — [/math] [math]\dfrac{1}{6}[/math] [math]2.6[/math]
[math]в[/math] [math] — [/math] [math]\dfrac{1}{2+1}[/math] [math] — [/math] [math] — [/math] [math] — [/math] [math]\dfrac{1}{3}[/math] [math]1.6[/math]
[math]г[/math] [math] — [/math] [math]\dfrac{1}{2+1}[/math] [math] \dfrac{1}{1+1} [/math] [math] 1 [/math] [math] 1 [/math] [math]\dfrac{1}{6}[/math] [math]2.6[/math]

Пусть текущий символ равен [math]г[/math], т. е. [math]?[/math] = [math]г[/math], тогда процесс его кодирования будет выглядеть следующим образом. Сначала рассматривается контекст [math]3[/math]-го порядка [math]“ббв”[/math]. Ранее он не встре­чался, поэтому кодер, ничего не послав на выход, переходит к анализу ста­тистики для контекста [math]2[/math]-го порядка. В этом контексте ([math]“бв”[/math]) встречались символ [math]а[/math] и символ [math]в[/math], счетчики которых в соответствующей [math]КМ[/math] равны [math]1[/math] каждый, поэтому символ ухода кодируется с вероятностью [math]\dfrac{1}{2+1}[/math], где в знаменателе число [math]2[/math] — наблюдавшаяся частота появления контекста [math]“бв”[/math], [math]1[/math] — значение счетчика символа ухода. В контексте [math]1[/math]-го порядка [math]в[/math] дважды встречался символ [math]а[/math], который исключается (маскируется), один раз также исключаемый [math]в[/math] и один раз [math]б[/math], поэтому оценка вероятности ухода будет равна [math]\dfrac{1}{1+1}[/math]. В [math]КМ(0)[/math] символ [math]г[/math] также оценить нельзя, при­чем все имеющиеся в этой [math]КМ[/math] символы [math]а[/math], [math]б[/math], [math]в[/math] исключаются, так как уже встречались нам в [math]КМ[/math] более высокого порядка. Поэтому вероятность ухода получается равной единице. Цикл оценивания завершается на уровне [math]КМ(-1)[/math], где [math]г[/math] к этому времени остается единственным до сих пор не попавшимся символом, поэтому он получает вероятность [math]1[/math] и кодируется посредством [math]0\ бит[/math]. Таким образом, при использовании хорошего статисти­ческого кодировщика для представления [math]г[/math] потребуется в целом примерно [math]2.6\ бит[/math]. Перед обработкой следующего символа создается [math]КМ[/math] для строки [math]“ббв”[/math] и производится модификация счетчиков символа [math]г[/math] в созданной и во всех просмотренных [math]КМ[/math]. В данном случае требуется изменение [math]КМ[/math] всех порядков от [math]0[/math] до [math]N[/math].