Вероятностные алгоритмы.

[swizard]

Введение.

Традиционным образом (то есть, в самые последние сутки дедлайна) я поучаствовал в конкурсе, организованном ребятами из конторы Hola.

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

1. Имеет практическую ценность.
2. Не подразумевает одного единственного верного решения, до которого

Comments

[p2004r]

Да, когда у сквида появился дигест, то на тонких каналах стало значительно легче жить. Тогда я впервые прочитал про топик, помню очень горд собой был собой :)

[swizard]

Ага :) Я впервые узнал про MinHash из книжки "Mining Massive Data Sets", помнится, тоже очень впечатлён был, и по мотивам написал потоковый кластеризатор документов, который смог твиттер в рантайме обрабатывать.

[qvz]

Гляда на графики равномерного и неравномерного распределений подумалось - а нельзя ли, пусть не афинно, преобразовать неравномерное распределение, например натянуть на гиперболоид, и спроецировать на плоскость, чтобы оно стало более равномерным, и затем вероятностными алгоритмами фигачить?

[swizard]

В принципе, если чётко известен закон распределения выбранной случайной величины (и оно непрерывное, например, это нормальное распределение), то уже можно пробовать использовать вероятностный алгоритм. Достаточно научиться понимать, какие значения и с какой вероятностью может принимать эта величина, и как эти значения можно генерировать из модели задачи.

Просто в случае с равномерным распределением всё это достаточно очевидно и прямолинейно.

[quadium]

Интересно.
А известен лучший результат?

[swizard]

Вроде на днях должны объявить результаты.

Согласно комментам участников, это должны быть числа порядка ~85%.

Там ещё есть статистические варианты решения, основанные на том, что с ростом объёма тестовых данных "слова" начинают встречаться чаще, чем "не слова", потому что первые берутся из конечного словаря, а вторые генерятся на лету. Этот подход может показать сильно больше 90%, но результат зависит от того, сколько конкретно тестов прогонят организаторы. На низких объёмах он не сильно лучше подбрасывания монетки :)

[quadium]

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

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

[swizard]

> Такое уже кто-нибудь делал?

Я, честно говоря, такого решения не припомню. Можешь попробовать полистать комменты здесь, здесь, здесь, или здесь :)

[wizzard0]

супер, я вот копал в похожую сторону, но поленился пост написать

[swizard]

а у вас какой итоговый процент верных ответов получился? :)