Статистические алгоритмы модели запросов?

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

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

Почти каждый алгоритм, который работает в модели PAC (за исключением алгоритмов обучения четности), может быть настроен для работы в модели SQ. Смотрите, например, эту статью Blum et al. в котором несколько популярных алгоритмов переведены в их SQ-эквиваленты ( Practical Privacy: платформа SuLQ ). Документ в принципе касается "конфиденциальности", но вы можете проигнорировать это - на самом деле это просто реализация алгоритмов с SQ-запросами.

Агностическое обучение, с другой стороны, намного сложнее в модели SQ: помимо вычислительных проблем (хотя они важны), сложность выборки, необходимая для агностического обучения, примерно такая же, как и для точного обучения, если у вас действительно есть доступ к данные указывают. С другой стороны, независимое обучение становится намного сложнее в модели SQ - вам, как правило, нужно делать суперполиномиально много запросов, даже для таких простых классов, как монотонные дизъюнкции. См. Эту статью Фельдмана ( Полная характеристика статистического обучения запросов с приложениями к эволюционируемости ) или эту недавнюю работу Gupta et al. ( Частное высвобождение конъюнкций и барьер статистического запроса )

Модель SQ была создана для анализа помехоустойчивого обучения, а именно алгоритм, который работает путем создания статистических запросов, будет работать в условиях классификации шума. Как сказал Аарон, большинство алгоритмов PAC, которые у нас есть, имеют эквиваленты в модели SQ. Единственное исключение - исключение Гаусса, которое используется в паритетах обучения (можно даже использовать его умное применение).изучить log (n) loglog (n) размерных соотношений в модели классификации шума). Мы также знаем, что четности не могут быть изучены с помощью статистических запросов, и оказывается, что наиболее интересные классы, такие как деревья решений, могут моделировать функции четности. Итак, в нашем стремлении получить алгоритмы обучения PAC для многих интересных классов (таких как деревья решений, DNF и т. Д.), Мы знаем, что нам нужны принципиально новые алгоритмы обучения, которые не работают в статистической модели запросов.

Я хотел бы немного уточнить ответ Аарона. Почти каждый агностический алгоритм (опять же, за исключением всего, что использует исключение Гаусса) может быть настроен для работы в модели SQ. Естественно, агностическое обучение сложнее, чем неагностическое, но это самостоятельный вопрос.