IMLE: неявное оценивание максимального правдоподобия

[ToxaBes]

Спасибо за статью! Интересно почитать такое.

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

Моя интуиция говорит, что это расстояние Левенштейна в первом приближении.

[MMKuz]

Спасибо! Интуиция близкая в том смысле, что здесь действительно можно думать о некоторой мере того, насколько два объекта отличаются.

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

Но для IMLE есть ещё более важный момент: после выбора ближайшего сэмпла нужно оптимизировать параметры генератора, уменьшая расстояние до объекта данных. Обычное расстояние Левенштейна дискретно и недифференцируемо, поэтому напрямую использовать его как функцию потерь для градиентного шага неудобно. Теоретически можно рассматривать его обобщения или дифференцируемые релаксации.

Уточните тогда, пожалуйста, что именно Вы имели в виду под расстоянием Левенштейна в первом приближении - возможно, я Вас не до конца понял.

[ToxaBes]

Уточните тогда, пожалуйста, что именно Вы имели в виду под расстоянием Левенштейна в первом приближении - возможно, я Вас не до конца понял.

Вы абсолютно правильно поняли.

Идея была разделить два места, где в алгоритме вообще участвует расстояние. На шаге сопоставления, где ищется ближайший сэмпл, градиент не нужен, там просто выбирается индекс, поэтому расстояние Левенштейна можно использовать напрямую, посчитав попарные расстояния между реальными и сгенерированными строками.

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

Но тут я сам уже вижу слабое место в своей идее.

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

Т.е напрямую методы не заменяют один другого, но какое-то сходство (не в реализации) у них есть.

[castraman]

Спасибо за разбор - редко встретишь настолько честные эксперименты, с прямым признанием, где метод проигрывает GAN по чистоте сэмплов.

Отдельно понравился вывод в "Одноточечном случае": по сути это ровно классическая k-NN оценка плотности (Лофтсгаарден -Квезнберри, 1965), только развёрнутая в обратную сторону. Там плотность оценивают по расстоянию до соседа в готовой выборке, а здесь наоборот параметры генератора настраивают так, чтобы это расстояние минимизировать. Красиво, что получилась MLE оценка без единого явного вычисления плотности.

По эксперименту с шахматкой: в разделе "Что осталось за кадром" вы упоминаете возможность заменить L2 на расстояние в пространстве эмбеддингов. Любопытно, помогло бы это с мостами между несвязными клетками, или дело не в метрике, а в том, что непрерывный генератор в принципе не может дать несвязный образ и любая метрика тут упрётся в топологию?

[MMKuz]

Спасибо! Аналогия с kNN действительно близкая: и там, и здесь расстояние до ближайших сэмплов несёт информацию о локальной плотности. Но IMLE не буквально обращает kNN-оценку плотности - в многоточечном случае связь с MLE требует дополнительных условий, а в общем случае возникает взвешенная целевая функция. Тут, конечно, интересно было бы отдельно аккуратно вывести эту связь.

А с шахматкой, думаю, основное ограничение действительно топологическое. Если латентное пространство имеет связный носитель, то непрерывный генератор отображает его в связное множество, поэтому точно получить восемь несвязных клеток он не может - между ними неизбежно останутся какие-то соединения. Замена или другой нормы расстояния на perceptual/embedding distance может изменить геометрию ошибки и сделать эти мосты менее выраженными, но сама связность от этого не исчезнет.

При этом мне видится, что топология требует существования таких “мостов”, но не большой вероятностной массы на них - хороший генератор теоретически может сделать их очень тонкими и практически незаметными. Тут действительно можно снова посмотреть в сторону гипотезы о многообразии: если данные лежат на нескольких несвязных компонентах низкоразмерного многообразия, то непрерывный генератор из связного латентного пространства всё равно вынужден каким-то образом соединить эти компоненты в своём образе.