Vowpal Wabbit возможное столкновение хеша

Question

У меня есть модель, сгенерированная в VW, и я также сгенерировал две читаемые модели на одних и тех же данных (первая с аргументом '--readable_model', а вторая с '--invert_hash').Когда я запускаю свою модель в своем тестовом наборе данных и использую опцию --audit, сообщаемые веса для некоторых функций немного отличаются по сравнению с весами, указанными в читаемых моделях, упомянутых выше.Например, вот часть читаемой модели, обученной на train.data:

213006:-0.19007
213008:-0.692261
213009:-0.203193

Как вы можете видеть, функция с индексом 213008 имеет вес -0.692261 Но когда я запускаю свою модель с параметром -t для test.dataи с параметром --audit, некоторые веса различаются в результатах аудита:

-3.962444   q^featureXY:213008:1:-0.756017

Что может вызвать это?У меня более 300 тыс. Функций, возможно, это вызвано каким-то хеш-конфликтом?Но если есть коллизия хешей, не должен ли Vowpal Wabbit сообщать об этом?Как видите, при тестировании использовалась опция -t, поэтому модель должна быть «стабильной».

Answer 1

vw допускает коллизию хешей (специально)

В литературе это называется "хеш-трюк" .

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

В чем преимущество игнорирования столкновений?

Поскольку нет необходимости обрабатывать столкновения особым образом, очевидный фактпреимущество хеш-трюка гораздо быстрее в обучении.

Разве коллизии не ухудшают процесс обучения?

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

Что если у меня слишком маленькое хеш-пространство (слишком много коллизий)?

Если у вас более 300 тыс. Функций, это действительно крайний случай.300k больше размера хеш-пространства по умолчанию (2^18 = 262144), поэтому сталкивающаяся часть больше не мала.В этом случае вам следует увеличить хеш-пространство, увеличив -b <bits>, где <bits> выше значения по умолчанию 18.

Как узнать, слишком много коллизий?

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

Вы также можете попробовать поискатьоптимальное значение, используя vw-hypersearch, например:

    # find the best average loss when using between 19 and 26 bits hash-space
    vw-hypersearch 19 26 vw -b % [other-vw-options...] -d data-set