Что делает задачу сложной или «сложной» для машинного обучения? Что касается сложности шаблона, а не вычислительного

Question

Как многие, меня интересует машинное обучение. Я занял класс по этой теме и читал несколько работ. Мне интересно узнать, что затрудняет задачу с машинным обучением. В идеале я хочу узнать о том, как сложность проблемы машинного обучения может быть определена или выражена.

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

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

Answer 1

В Thery обучения машины, VC dimension домена обычно используется для классификации «Как трудно узнать его», сказал

домен иметь VC размер k если существует множество k, так что, независимо от их метки, предлагаемая модель может «разбить их» (разделить их идеально, используя некоторую конфигурацию модели).

страница википедии предлагает 2D пример как область, с линейной разделитель в качестве модели:

Вышеприведенные пытается продемонстрировать, что есть установка точек в 2D, так что один может поместиться в линейный разделитель, чтобы разделить их, какими бы ни были метки. Тем не менее, за каждые 4 очка в 2D, есть некоторое назначение меток таким образом, что линейный Seperator не может разделить их:

Таким образом, VC Размерность 2D пространства с линейным разделённых символом 3.

также , если VC размер домена и модели infinty, говорят, что проблема не изучаемым

Если у вас есть достаточно сильный математический фон, и заинтересован в теории машинного обучения, вы можете попробовать после the lecture of Amnon Shashua about PAC