- Агностическое PAC-обучение k-юнт с использованием L2-полиномиальной регрессии (arXiv)
Автор: Мохсен Хейдари, Войцех Шпанковский.
Аннотация: Многие традиционные алгоритмы обучения полагаются на функции потерь, отличные от естественных потерь 0–1, для обеспечения вычислительной эффективности и теоретической управляемости. Среди них есть подходы, основанные на абсолютных потерях (регрессия L1) и квадратичных потерях (регрессия L2). Доказано, что первый является \textit{агностиком} учащимся PAC для различных важных классов понятий, таких как \textit{juntas} и \textit{полупространства}. С другой стороны, второй вариант предпочтительнее из-за его вычислительной эффективности, которая линейно зависит от размера выборки. Однако обучаемость PAC до сих пор неизвестна, поскольку гарантии были доказаны только при ограничениях на распространение. Вопрос о том, является ли регрессия L2 независимым методом обучения PAC для потерь 0–1, был открыт с 1993 года, и на него еще предстоит ответить. Эта статья решает эту проблему для класса хунты на булевом кубе — доказывая независимое PAC-обучение k-хунты с использованием полиномиальной регрессии L2. Кроме того, мы представляем новый алгоритм обучения PAC, основанный на булевом разложении Фурье с меньшей вычислительной сложностью. Алгоритмы на основе Фурье, такие как Linial et al. (1993), использовались в условиях ограничений распределения, таких как равномерное распределение. Мы показываем, что при соответствующих изменениях эти алгоритмы можно применять в агностических условиях без каких-либо предположений о распределении. Мы доказываем наши результаты, соединяя обучение PAC с потерями 0–1 с задачей оценки минимального среднеквадратического значения (MMSE). Мы получаем элегантную верхнюю границу потерь 0–1 с точки зрения ошибки MMSE и показываем, что признак MMSE является обучаемым PAC для любого концептуального класса, содержащего его.
2. О сложности обучения PAC в гильбертовых пространствах (arXiv)
Автор : Сергей Чубанов
Аннотация: Мы изучаем проблему бинарной классификации с точки зрения изучения выпуклых многогранников в гильбертовых пространствах, к которым можно свести любую задачу бинарной классификации. Проблема обучения выпуклых многогранников в конечномерных пространствах достаточно хорошо изучена в литературе. Мы обобщаем эту проблему на задачу в гильбертовом пространстве и предлагаем алгоритм обучения многогранника, который правильно классифицирует не менее 1−ε распределения с вероятностью не менее 1−δ, где ε и δ — заданные параметры. Кроме того, как следствие, мы улучшаем некоторые предыдущие оценки полиэдральной классификации в конечномерных пространствах.
