Я имею в виду языковые семейства, которые допускают произвольно длинные строки, а не соединения по n битам или спискам решений или любому другому «простому» языку, содержащемуся в {0,1} ^ n.
Я спрашиваю об «теоретико-автоматных» регулярных языках, в отличие от «теоретико-логических»: что-то вроде кусочно тестируемых языков, языков с нулевой начальной высотой, локально тестируемых языков и тому подобное. Соответствующим параметром сложности n является размер минимального принимающего DFA. Итак, вкратце: есть ли интересное семейство DFA из n-состояний, которое, как известно, эффективно усваивается PAC?
Ответы:
Недавно на LICS 2010 были получены результаты о полиномиальной обучаемости полулинейных множеств: парикские образы регулярных языков: сложность и приложения . Я думаю, это не то, что вы ищете.
Вам также следует взглянуть на статью Кларка и Толларда: PAC-обучаемость вероятностных детерминированных конечных автоматов
источник
Эта статья дает хороший совет о результатах PAC-обучения для кусочных языков: изучение линейно разделимых языков
Работа Кларка и Толларда была усовершенствована Кастро и Гавальдой таким образом, чтобы соответствовать тому, что вы ищете: На пути к возможному PAC-обучению, вероятностным детерминированным конечным автоматам
И эта работа является хорошим ответом на первый вопрос: « Об обучаемости случайных идеалов» . Один из авторов, вероятно, будет тем же человеком, который ранее задавал вопрос здесь, но я нашел эту страницу, работая над этой проблемой, и только что нашел эту статью: это может помочь другим получить эту ссылку.
источник