Что происходило до изучения PAC

Я изучаю PAC обучение (вычислительную теорию обучения) как новичка без каких-либо предварительных знаний о машинном обучении / искусственном интеллекте. Я исследую модель в основном с исторической точки зрения.

Для этого, конечно, важнее всего результаты, основанные на модели. Есть достаточно документов, которые документируют эти результаты. Но я также хочу написать кое-что о том, что происходило до изучения PAC, как обрисовать в общих чертах исторический контекст, до которого Valiant пришел с понятием модели PAC.

Никакие документы / опросы, которые я нашел, пока не документируют это, и как человеку, не имеющему реального знания о машинном обучении, это трудно выяснить. Поэтому я задаю этот мягкий вопрос здесь, потому что я считаю, что есть достаточно экспертов, которые могут помочь мне в этом. Рекомендации высоко ценятся.

Когда я смогу исследовать и изучать то, что происходило до PAC, я мог бы лучше понять, почему академический мир с таким энтузиазмом относится к модели PAC, что также является интересным документом для моей исторической работы!

Рекомендации высоко ценятся.

Предполагается, что автор рассмотрит вопрос о контексте и актуальности своих результатов в начале своей публикации. Я только что рассмотрел введение "Л. Валиант. Теория обучения. Сообщения ACM, 27, 1984 г." еще раз, и обнаружил, что Valiant действительно хорошо охватил ваш вопрос.

Оригинальная статья Valiant доступна в свободном доступе и не слишком сложна для чтения. (За исключением раздела 7, который только доказывает, что автор также может решать сложные математические проблемы, но не вносит большой вклад в реальное содержание статьи.) Чтение хотя бы его введения будет более полезным, чем чтение моего слишком длинного ответа на этот вопрос. вопрос, поэтому я предлагаю действительно попробовать.

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

... такая система, по крайней мере, была бы очень хорошим началом. Во-первых, когда рассматриваются наиболее известные примеры систем, которые воплощают запрограммированные знания, а именно, экспертные системы, такие как DENDRAL и MYCIN , по существу, никакие логические обозначения, кроме исчисления высказываний, не используются.

Это интересная информация для контекста, потому что исчисление высказываний значительно слабее исчисления предикатов или различных систем теории типов, которые иногда используются сегодня. (Как ни странно, Prolog (1972) и ML (1973) были, среди прочего, мета-языками для «таких» экспертных систем, и, насколько я вижу, выходят за рамки простой логики высказываний. Кроме того, реляционная модель ( 1969) для управления базами данных, как утверждается, основаны на логике предикатов.)

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

Я полностью согласен здесь. Важно уметь объяснить, как ваше решение способно решить данную проблему, и в каком смысле это решение. В противном случае вы просто получите теоремы о том, что «бесплатный обед» не позволяет отличить ошибочную реализацию сомнительной эвристики от правильной реализации соответствующей эвристики.

Таким образом, в этой статье предпринята попытка исследовать пределы того, что можно изучить, что допускается алгоритмической сложностью. Результаты отличаются от множества предыдущих работ по обучению, потому что они пытаются согласовать три свойства ((1) - (3)), упомянутых ранее. Наиболее строгим в нашем подходе является литература по индуктивному выводу [...]. Существует большая часть работ по распознаванию и классификации образов с использованием статистических и других инструментов [...]. Обучение, в различных менее формальных смыслах, широко изучалось как раздел искусственного интеллекта.

Свойства ((1) - (3)) заключались в том, что (1) «машины могут достоверно изучать целые характеризуемые классы понятий», (2) «подходящие и нетривиальные для знаний общего назначения» и (3) «вычислительные Процесс требует только допустимого (т. е. полиномиального) количества шагов ».

Определение языка в пределе является первой известной попыткой охватить понятие обучаемости. Он был введен Голдом в 1967 году и представляет собой модель для индуктивного вывода, касающуюся изучения языков.