Почему функция потерь 0-1 неразрешима?

12

В книге глубокого обучения Яна Гудфеллоу написано, что

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

Почему потери 0-1 неразрешимы или как они экспоненциальны во входных измерениях?

Самра Иршад
источник

Ответы:

18

β1(YяβИкся0)я2NNобщее количество точек выборки. Известно, что это NP-хард. Знание текущего значения вашей функции потерь не дает никакой подсказки о том, как вы, возможно, должны изменить свое текущее решение для улучшения, как вы могли бы получить, если бы были доступны градиентные методы для выпуклых или непрерывных функций.

Дон валпола
источник
1
Очень хороший момент - на практике случайный поиск или исчерпывающий поиск - единственные методы, которые можно использовать для определения минимума такой функции потерь, верно?
DeltaIV
2
^^ или эволюционные / роевые методы разведки, может быть?
Самра Иршад
@samrairshad Да, на самом деле проигрыш 0-1 не так уж редко встречается в эволюционных методах.
Джон Дусетт
Прежде чем перейти от случайного поиска к сложным эволюционным / роевым алгоритмам, я бы попробовал метод кросс-энтропии (CEM).
Maxy
1

Ошибка классификации на самом деле иногда поддается устранению. Его можно оптимизировать эффективно, хотя и не совсем точно, используя метод Nelder-Mead, как показано в этой статье:

https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html

«Уменьшение размеров - это процесс преобразования многомерных векторов в низкоразмерное пространство. При распознавании образов часто желательно, чтобы эта задача выполнялась без значительной потери классификационной информации. Ошибка Байеса является идеальным критерием для этой цели; однако известно, что он чрезвычайно сложен для математической обработки. Следовательно, на практике используются субоптимальные критерии. Мы предлагаем альтернативный критерий, основанный на оценке ошибки Байеса, который, как мы надеемся, ближе к оптимальному критерию, чем критерии, используемые в настоящее время. . Алгоритм линейного уменьшения размера, основанный на этом критерии, задуман и реализован. Эксперименты демонстрируют его превосходную производительность по сравнению с обычными алгоритмами ».

Упомянутая здесь ошибка Байеса - это в основном проигрыш 0-1.

Эта работа была проделана в контексте сокращения линейных размеров. Я не знаю, насколько это было бы эффективно для обучения сетей глубокого обучения. Но дело в том, и ответ на вопрос: 0-1 потеря не всегда трудно поддается решению. Это может быть относительно хорошо оптимизировано, по крайней мере, для некоторых типов моделей.

любомир
источник