03 сентября 2003 - Shelwien

[...]
...я недавно получил кое-какие забавные результаты. Решил вдруг попробовать хранить вероятности в int вместо float. Чего б хорошего из этого вышло...

1. Приемлемая точность (+/-50 байт) при 16-битных fixedpoint вероятностях получилась только после

2. Скорость упала в 1.5-2 раза даже без вышеуказанных дополнений;

3. Экономия памяти составила ~3M на book1 (25M->22M).

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

И еще по поводу SSE. У меня тут случилось очередное "озарение" (не знаю уж, насколько "велосипедное" ;) и я собирался под это дело выкатить ash с SSE, но что-то пока не срастается. Короче, расскажу пока так. Кажется, я упоминал о введении "внутриконтекстных order-(-1)" при переходе от ash01 к ash02, а позже о возможной избыточности в geopack из-за такой штуки? Так вот, я разобрался с логикой этого эффекта. Дело в том, что обычный апдейт (типа p=p*(1-wr)+wr), а также аналогичный ему обычный BFA-апдейт в результате дают оптимальное значение на текущий момент. Т.е. мы добавляем элемент к последовательности и получаем оптимальное для дополненной последовательности значение параметра. А это полностью правильно только для стационарных последовательностей - где чем дальше, тем вероятней, что оптимальное на данный момент значение останется оптимальным навсегда. Для реальных же, нестационарных, требуется дополнительная экстраполяция. Оптимальной для текущего символа статистика станет только после апдейта - вот и надо для моделирования символа экстраполировать эту статистику-после-апдейта по текущей. Смешивание с order-(-1) в этом смысле является линейной экстраполяцией без учета любой дополнительной информации о текущем символе. Способом же использования такой информации является, кто бы мог подумать, SSE ;) Еще один имхо интересный момент заключается в том, что унарным SSE невозможно проэмулировать это-самое смешивание с order-(-1), которое, все-таки, может быть полезным достаточно часто (ну, без одновременного использования унарных и полных вероятностей в качестве контекста). Поэтому и оказывается полезным смешивание исходных вероятностей с их SSE.

Вывод: экстраполяцию распределений имеет смысл применять сознательно. Простейшими ее видами являются "временные апдейты" в расчете на то, что текущий символ будет равен LES или MPC. Ну, и прочие линейные аппроксимации (хотя ими никто не заставляет ограничиваться). В общем, важно помнить, что любое предсказание само по себе оптимально только постфактум, либо для стационарных данных - иначе его нужно экстраполировать. Это относится к любым распределениям, SSE, BFA и вообще к чему угодно.

Пытаюсь на основе этой теории прикрутить к ash внутриконтекстный не унарный SSE, но пока ничего хорошего. Сильно многого сразу хочу, видать ;)