Есть ли работа, сочетающая в себе машинное обучение и более экзотические формы теории сложности?

13

Мне кажется, что специалисты по машинному обучению / интеллектуальному анализу данных знакомы с P и NP, но редко говорят о некоторых более тонких классах сложности (например, NC, BPP или IP) и их последствиях для эффективного анализа данных. Есть ли какой-нибудь обзор работы, выполняющей это?

cc.complexity-theory reference-request machine-learning Майк Избицкий
источник
2
Никакого опроса, о котором я знаю, но посмотрите на этот указатель на «квантовое обучение» (# 5) из этого поста: blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Суреш Венкат
Машинное обучение регулярно атакует очень сложные проблемы, которые, вероятно, находятся за пределами NP для «глобальной» оптимизации, но внутри NP или менее сложные, чем для «локальной» оптимизации. так что вся концепция класса сложности становится расплывчатой, когда кто-то оптимизирует для «достаточно хороших» результатов, которые измеряются в большей степени с помощью измерений качества, зависящих от приложения, и в некотором смысле не являются действительно известными априори к запуску алгоритма (ов) ....
vzn
@vzn Для меня эта тонкость кажется еще одной причиной, чтобы обратить внимание на сложность! Это может дать некоторые очень интересные идеи.
Майк Избицкий
безусловно, есть связь между теорией обучения, сложностью схемы и криптографией. но это угол теории обучения, который немного удален от практики машинного обучения. если вам интересно, я могу придумать несколько советов
Сашо Николов
да, еще один пример, BDD (двоичные диаграммы принятия решений) использовались в алгоритмах баз данных / интеллектуального анализа данных и имеют сильную связь со сложностью схемы. но мне кажется, что весь вопрос может быть немного хитрой предпосылкой, потому что большая часть машинного обучения прагматична, а сложность прикладного ML часто изучается косвенно / эмпирически, анализируя реальные реализации алгоритмов, а не пытаясь теоретически предсказать или строго классифицировать его.
vzn

Ответы:

3

Существует некоторое врожденное различие или несходство подходов между двумя областями прикладного машинного обучения и теории TCS / сложности.

Вот недавний семинар на эту тему в Центре вычислительной сложности, Принстон, с большим количеством видео.

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

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

ВЗН
источник
5
"Википедия называет" ... Вы действительно знаете что-нибудь об этом предмете? 1) в вики для машинного обучения есть раздел «Теория раздела», который связан со страницей «Теория компьютерного обучения». 2) работа «Valiant», «Vapnik», «Schapire» по теории обучения оказала огромное влияние на практику машинного обучения.
Сашо Николов