Конкурс з програмування на PHP: Класифікатор слів (спеціальні призи)

Ми приносимо найглибші вибачення за довгу затримку при підготовці цього поста. Сьогодні ми публікуємо аналіз самонавчаючих рішень, надісланих на конкурс з програмування, і вручаємо два спеціальні призи.

Англійська версія цього запису на GitHub.

Отже, 9 з надісланих рішень виявилися самообучающимися. Ідея самонавчання така: оскільки всі слова вибираються з кінцевого словника, а не-слова генеруються випадково, то всяка рядок, яка була представлена досліджуваної програмі повторно, з більшою ймовірністю опиниться словом, ніж не-словом. При досить тривалому тестуванні більшість слів зі словника встигнуть повторитися, тоді як для не-слів випадкові повторення зустрічаються набагато рідше.

Щоб спостерігати поведінку самонавчаючих рішень, ми протестували їх на 1 000 000 блоків. Тестувати на такій кількості блоків всі рішення було б нереально, але ці дев'ять виявилися досить швидкими.

На графіку нижче показана залежність відсотка правильних відповідей від кількості оброблених блоків. Зверніть увагу, що горизонтальна шкала — логарифмічна.

image

Деяких рішень при тестуванні на дуже великому числі блоків не вистачило пам'яті, тому їх лінії перериваються, не дійшовши до позначки в мільйон блоків.

На наступному графіку показаний не накопичувальний відсоток правильних відповідей (середній за весь час роботи), а тільки за останні 10 000 блоків в кожній точці. Тут краще видно, як рішення веде себе після певного обсягу навчання.

image
Нижче — графіки частоту псевдонегативних і псевдопозитивних результатів, відповідно. Тут теж враховується поведінка на останніх 10 000 блоках, а не накопичувальне від початку роботи.

image
image
Зверніть увагу, що результати у деяких рішень при тривалому навчанні кілька починають погіршуватися. Очевидно, це відбувається із-за того, що деякі не-слова теж випадково повторюються, і алгоритм приймає їх за слова. На останньому графіку видно, що ростуть саме хибнопозитивні результати.

На спеціальній сторінці на GitHub можна знайти докладні результати дослідження на 1 000 000 блоків.

На підставі проведеного дослідження ми вирішили нагородити спеціальними призами 400 USD учасників під псевдонімами rd.nvkz та AndSDev. Їх вирішення досягли найвищих показників — 93.99% і 93.65% відповідно. Крім того, їхня поведінка не погіршується при тривалому навчанні, а у першого з них — навіть продовжує поліпшуватися. Наші вітання!

Слідкуйте за блогом компанії Hola! Будуть нові конкурси.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.