Немного предыстории: Я заинтересован в поиске «менее известных» нижних границ (или результатов твердости) для задачи «Обучение с ошибками» (LWE) и их обобщений, таких как «Обучение с ошибками над кольцами». Для конкретных определений и т. Д., Вот хороший обзор Регева:...
Хорошо известно, что для концептуального класса с размерностью VC достаточно получить помеченные примеры для PAC learn . Мне не ясно, является ли алгоритм обучения PAC (который использует эти многочисленные образцы) правильным или неправильным? В учебниках Кернса и Вазирани, а также Энтони и Биггса...
Вот проблема с похожим вкусом к изучению хунт: Входные данные: функция f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , представленная оракулом членства, то есть оракулом, который дал xxx , возвращает f(x)f(x)f(x) . Цель: Найти вложенный куб SSS из {0,1}n{0,1}n\{0,1\}^n с объемом...
DDD{0,1}d×{0,1}{0,1}d×{0,1}\{0,1\}^d\times \{0,1\}CCCf:{0,1}d→{0,1}f:{0,1}d→{0,1}f:\{0,1\}^d\rightarrow\{0,1\}f∈Cf∈Cf \in Cerr(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]OPT(C,D)=minf∈C err(f,D)OPT(C,D)=minf∈C err(f,D)OPT(C,D) = \min_{f \in C}\...
Мой вопрос немного общий, поэтому я придумываю хорошую историю, чтобы оправдать его. Терпите меня, если это не реально ;-) Сказка Г-н Х, глава отдела компьютерной безопасности крупной компании, немного параноик: он требует, чтобы все сотрудники меняли свои пароли раз в месяц, чтобы минимизировать...
Данные реального мира иногда имеют естественное количество кластеров (попытка сгруппировать их в число кластеров, меньших, чем какое-либо волшебство k, приведет к значительному увеличению стоимости кластеризации). Сегодня я посетил лекцию доктора Адама Мейерсона, и он назвал этот тип данных...
Дана Англюин ( 1987 ; pdf ) определяет модель обучения с помощью запросов на членство и теоретических запросов (контрпримеры к предложенной функции). Она показывает, что регулярный язык, представленный минимальным DFA из состояний, может быть изучен за полиномиальное время (где предложенные функции...
Angluin и Laird ('88) формализовали обучение со случайно искаженными данными в модели «PAC со случайным классификационным шумом» (или с шумным PAC). Эта модель аналогична обучению PAC , за исключением того, что метки примеров, данных учащемуся, искажены (перевернуты) независимо друг от друга...
Недавно я прочитал приличное количество статей CoLT. Хотя я не борюсь с отдельными статьями (по крайней мере, не больше, чем я обычно борюсь с другими теоретическими работами), я не чувствую, что у меня есть хорошее широкое понимание области в целом. Существуют ли стандартные тексты, обзоры или...
Во-первых, я до сих пор не уверен, хорошо ли подходит этот вопрос для этого вопроса, поэтому я не буду обижаться, если толпа думает, что это не так ... В поисковом маркетинге несколько проблем интересны. Разработка справедливых (и прибыльных) аукционных механизмов и расчет оптимальных стратегий...
Какие классификаторы машинного обучения являются наиболее распараллеливаемыми? Если бы у вас была трудная проблема классификации, ограниченное время, но приличная сеть компьютеров для работы, с какими классификаторами вы бы попробовали? С моей стороны это выглядит как некоторые стандартные...
Каков современный уровень сложности запросов для правильных формул PAC, изучающих 2-DNF с типовыми запросами и при равномерном распределении ? Или какие-нибудь нетривиальные ограничения на это? Поскольку я совсем не знаком с теорией обучения, и этот вопрос мотивирован другой областью, ответ может...
Определим класс функций для набора из битов. Исправьте два распределения , которые «разумно» отличаются друг от друга (если хотите, их вариационное расстояние составляет не менее , или что-то подобное).p , q ϵNnnр , дp,qp, qεϵ\epsilon Теперь каждая функция в этом классе определяется набором из...
Я довольно хорошо знаком с теорией, лежащей в основе VC-Dimension, но сейчас я смотрю на последние (последние 10 лет) достижения в теории статистического обучения: (локально) средние Радемахера, лемма о конечных классах Массарта, Покрывающие числа, Цепочки, Дадли Теорема, псевдоразмерность,...
Хорошо известно, что для классического обучения PAC необходимы примеры , чтобы получить границу ошибки ε whp, где d - это VC-размерность концептуального класса.Ω(d/ε)Ω(d/ε)\Omega(d/\varepsilon)εε\varepsilonddd Известно ли, что примеры нужны в агностическом...
В частности, я прошу ресурсы, чтобы узнать о системах машинного обучения, которые могут обновлять свои соответствующие сети убеждений (или эквивалент) во время работы. Я даже сталкивался с несколькими, хотя не смог их добавить в закладки. Как вы можете себе представить, это довольно сложная тема...
Предположим, у меня есть Кkk указывает на RdRd\mathbb{R}^d, Они вызывают диаграмму Вороного. Если я назначу каждому изkkk указывает ±±\pm метка, они вызывают двоичную функцию на RdRd\mathbb{R}^d, Вопрос: какова VC-размерность всех таких возможных бинарных функций, вызванных некоторымиkkk очки и...
Я имею в виду языковые семейства, которые допускают произвольно длинные строки, а не соединения по n битам или спискам решений или любому другому «простому» языку, содержащемуся в {0,1} ^ n. Я спрашиваю об «теоретико-автоматных» регулярных языках, в отличие от «теоретико-логических»: что-то вроде...
Случайные леса имеют репутацию среди самых эффективных методов классификации. Тем не менее, мы не сталкиваемся с ними в учебно-теоретической литературе, из которой я предполагаю отсутствие глубоких теоретических результатов. Если бы кто-то хотел вникнуть в эту теорию, с чего бы...