Гарантии обобщения при обучении в условиях шума массара

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

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