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

В этом посте я расскажу об основах «обучения» и, в частности, о структуре обучения PAC на интуитивном уровне. После этого поста я напишу о VC-измерении, и мы обсудим, как решить, можно чему-то научиться или нет. Кроме того, мы дадим некоторые теоретические сведения об известном факте: если вы хотите обучить сложную модель, вам нужно много данных.

PAC-обучение

Что такое обучение? В обычном контексте алгоритм обучения — это алгоритм, который на основе некоторых данных обучает функцию, способную правильно их классифицировать (для простоты давайте сосредоточимся только на задаче классификации). PAC-обучение — это фреймворк, в котором мы допускаем, вероятно, приблизительно правильное обучение, то есть наш алгоритм обучения, вероятно, является приблизительно правильным (что звучит не очень красиво, не так ли?). Теперь я попытаюсь объяснить, почему обучение PAC является чем-то разумным.

Предположим, у нас есть коллекция S из n точек с их метками, и мы хотим «выучить» эти данные. Мы перейдем к нашему алгоритму обучения, и он примет эти точки n в качестве входных данных и вернет классификатор h, который принимает в качестве входных данных некоторую точку и возвращает предсказанную метку. Откуда мы знаем, что классификатор h является хорошим классификатором? Первое, что мы можем потребовать, это чтобы классификатор правильно классифицировал каждую точку S… но это не очень разумно, не так ли? Как бы вы себя чувствовали, если бы кто-то сказал, что ваша модель плоха, потому что она не имеет 100% точности на тренировочном наборе?

Вот где возникают концепции PAC:

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

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

Теперь, когда у нас есть интуиция, давайте перейдем к формальному определению. Сначала я введу некоторые обозначения: классом C классификаторов будет, например, класс деревьев решений фиксированных гиперпараметров или класс линейных регрессий типа y = mx+b, и т. д. Классификатор — это любая функция, которая присваивает метку точке. Кроме того, ошибкой между двумя классификаторами f и h будет вероятность того, что данная точка xиз распределения Dмы имеем, что f(x)≠h(x)

Определение: PAC — обучение. Класс логических классификаторов C является PAC-обучаемым, если существует алгоритм L такой, что для всех f в C, для всех распределений вероятностей D, для любыхε иδ в [0, 0,5] алгоритм L на входных эпсилон и дельта и случайная выборка, выбранная из D, выведет классификатор h с вероятностью не менее 1-δ, такой что h отличается от h не более чем заε

Подводя итог, можно сказать, что алгоритм обучения в рамках PAC — это алгоритм, который с учетом набора данных S и целевого классификатора f с высокой вероятностью выдает классификатор h, который мало отличается из f.

В следующем посте мы поймем, как эти параметры вероятности ε иδ, а также сложность модели повлияют на количество данных, необходимых для гарантии обучения PAC.