Компьютер не может приобретать знания, поскольку никто в мире ещё не придумал формат хранения знаний.
Если не мистифицировать понятие «знания», то способов представления знаний придумано множество, и они давно и успешно используются в экспертных системах и т.д. Другой вопрос, что представления эти неуниверсальны, но об этом, собственно, и речь в статье.
А программу сам компьютер без вмешательства человека не способен изменить.
Извините, но это откровенная ложь. Никаких принципиальных ограничений на изменение программ самим компьютером нет. Можно лишь согласиться, что методы «слабого» обучения такого изменения не осуществляют, и «сильное» обучение без него обойтись не может.
Что ещё более сомнительно, поскольку для прогнозирования необходимо получать знания, а они пока машине не подвластны.
Для прогнозирования надо строить модели, а это машине вполне подвластно. Знания — это особая форма моделей, построенных в рамках определенных представлений…
Ну, или как вы интерпретируете то, что машина выполняет прогноз погоды?
Вот я и спросил, чему же в Вашем случае обучается компьютер?
Ответ прежний: система учится предсказывать результат отображения между некоторым входом и выходом. Можно добавить — путем построения моделей.
Для большей конкретики нужно разбирать вопрос о структуре этих моделей.
Какой архитектуры сети Вы используете, для решения каких задач, и как выбираете число нейронов?
В примере обучение с учителем. Добавлять точки инкрементно или нет — дело вкуса. ИНС при правильном добавлении/удалении нейронов эту задачу могут решать без переобучения, но обобщение и предсказание у них будет плохим, если закон формирования данных в рамках выбранного типа ИНС оказывается непредставимым.
К сожалению, в явном виде они не сохранились, так как получались при использовании рандома (да и точные значения параметров самой функции сейчас не восстановить). Но, во-первых, аналогичный пример построить очень легко (взять некую регулярную функцию и добавить шум); во-вторых, если нужны именно эти точки, можно их координаты по картинке измерить — дело пяти минут.
Говоря именно о перцептроне Розенблатта, вероятно, можно сказать следующее. Если не ограничиваться числом А-элементов, то при желании от перцептрона можно добиться переобучения. Но в целом из-за ступенчатой активационной функции и особенностей обучения перцептрон не склонен к переобучению (просто в силу того, что ступенька нивелирует сложность модели) в отличие от сетей прямого распространения. Однако это не спасает.
Вообще, переобучение — это смешной эффект, имеющий чисто учебно-методическое значение. Основная же проблема — в отсутствии адекватного обобщения, которое может и не усугубляться переобучением. А отсутствие обобщения для тех же перцептронов очень даже характерно.
Это вопрос типа: «Куда едет езда?» ))
Согласитесь, на него затруднительно что-то вразумительное ответить.
Но все же, если пытаться на него ответить, то ответ можно также найти в статье: в конечном итоге интеллектуальная система учится предсказывать результат отображения между некоторым входом и выходом.
В статье, в общем-то, на первые вопросы ответы есть: универсальное обучение — это обучение, в котором нет ограничений на то, какого вида закономерности могут быть сформированы. Последний вопрос не очень понятен. Машинное обучение отличается от «простого» тем, что подразумевает обучение машины, а не человека. От «универсального» оно отличается тем, что может быть (и сейчас является) не универсальным, хотя (как мы надеемся) может быть и универсальным.
Учебники разные бывают. Никто не спорит, что прикладное машинное обучение чрезвычайно полезно, и о нем надо писать в учебниках. Но бывают учебники и с описанием фундаментальной науки, например математики или физики, где про приложения почти ничего не говорится. Машинное обучение отнюдь не сводится к одним только приложениям. И чтобы не застрять «в локальном экстремуме» исследований, нужно отказаться от руководства критерием локальной практической полезности.
Если бы Вы Гёделя, Тьюринга, Чёрча или еще кого в 1930-х годах спросили, а как их абстрактные математические изыскания непосредственно использовать на практике, вряд ли бы получили удовлетворительный ответ. А ведь именно они и привели к созданию компьютеров. С сильным ИИ ситуация аналогичная (если не еще более выраженная). И универсальное обучение — лишь один из аспектов. Сейчас напрямую использовать колмогоровскую сложность для решения практических задач нельзя (но ее упрощенные производные типа принципа минимальной длины описания — очень даже можно, о чем есть соответствующие книжки, если не читали). Но речь, как и в случае с созданием компьютеров, не о непосредственном прикладном использовании сейчас, а о разработке решения для создания сильного ИИ в будущем.
Что касается Воронцова, то, да, он начал направлять по-немногу Журавлевскую школу распознавания образов в нужное русло, но пока смена курса там не слишком значительная.
Насчет поиска алгоритмов. В базовых абстрактных методах универсального обучения, да, подразумевается перебор всех машин Тьюринга. Но всем понятно, что за реалистичное время можно перебрать только «экспоненциально малое» число программ. В простых практических реализациях этого подхода вместо прямого перебора используются генетические алгоритмы или что-то похожее. Но как было сказано в другом комменте, это тоже не то. Реальное решение этой задачи — это «ИИ-полная» проблема, но фишка в том, что и обратное верно. То есть нельзя построить универсальную систему обучения без создания реального сильного ИИ, как и нельзя построить реальный сильный ИИ без построения универсальной системы обучения. Здесь нужно выходить за рамки чистого машинного обучения и рассматривать проблему сильного ИИ в комплексе, только тогда вывод нужной алгоритмической модели среды можно будет организовать не как какой-то простой универсальный (но, естественно, неэффективный) переборный метод, а как направленное конструирование. Однако в паре абзацев описать идею решения этой проблемы не получится.
Верно, поэтому должны вводиться эвристики, которые не обрезают пространство моделей, а смещают их сложности/вероятности.
К примеру, у нас есть некий универсальный язык программирования. Сложности моделей, выраженные на этом языке, будут пропорциональны 2^-L, где L — длина соответствующей программы. Но если создаем некую библиотеку функций, то те программы, которые этими функциями будут пользоваться, окажутся существенно короче (вероятнее), чем если бы их писали с нуля. При этом библиотека никак не сужает универсальность в целом. Также работает и человеческий язык: на основе элементарных блоков создаются более высокоуровневые блоки, отвечающие за некие полезные фрагменты моделей (которые, к тому же, как вы правильно заметили, можно передавать от одного агента другому).
Но это лишь один из простейших (важных, но недостаточных) механизмов того, как без ущерба для универсальности можно повышать эффективность обучения.
То, что «Само по себе требование бесконечных ресурсов не делает теорию бесперспективной» — об этом, собственно, и речь. Или, точнее, речь о том, что проблему универсального обучения все равно нужно решать, и то, что известные универсальные методы требуют бесконечных ресурсов, не делает задачу неактуальной и не означает, что саму проблему можно игнорировать, занимаясь лишь «слабыми» методами обучения.
А вот то, что «если работа программы не ограничена во времени и нужно получить не абсолютный результат, а всего лишь улучшить имеющийся» — уже не совсем так. Действительно, следующей же идеей по развитию универсального метода обучения является организация перебора моделей в условиях ограниченных вычислительных ресурсов путем параллельного выполнения всех алгоритмических моделей, на каждую из которых выделяется доля ресурсов, пропорциональная ее алгоритмической вероятности. Это так называемые поиск Левина (LSearch). Кстати, из него следует интересное определение сложности по Левину, которое расширяет сложность по Колмогорову (но это отдельная тема). Собственно, Соломонов (а также Хаттер) и опирались на LSearch, оптимальность которого доказана с точностью до мультипликативной константы. К сожалению, для реальных задач эта константа может быть огромной. Как говорил сам Левин, только фрики-математики могут считать число 2^500 конечным.
Короче, для реального сильного ИИ полный перебор, пусть даже и хорошо организованный, явно не подходит. Здесь нужна самооптимизация, чтобы превратить мультипликативную константу в аддитивную (по Шмидхуберу), а также набор априорных метаэвристик, чтобы от эту аддитивную константу тоже максимально уменьшить.
Да, и в статье об этом сказано :)
Имеем чисто парадоксальную ситуацию. С одной стороны, есть абсолютно очевидный тезис (хотя, не исключено, не все с ним согласятся). А с другой стороны, когда доходит до дела, этот тезис усиленно игнорируется. За деревьями становится не видно леса. В частности, за огромной кучей частных результатов в области машинного обучения напрочь теряется ее конечная цель.
Книжка Бишопа — это как раз очень хороший пример того, о чем говорится. Это обширный современный учебник по машинному обучению и распознаванию образов, и в нем ни слова не сказано ни про Колмогоровскую сложность, ни про принцип минимальной длины описания, ни про универсальную индукцию по Соломонову. Байесовские приоры — да. Но сами они без всего указанного превращаются лишь в эвристики, относительно которых даются практические рекомендации по созданию слабых (неуниверсальных) методов машинного обучения.
А Вы говорите, не скрывают :)
За ссылку на лекцию спасибо, послушаю, хотя есть подозрение, что там будет про классические результаты.
Публикации Соломонова есть здесь: world.std.com/~rjs/pubs.html
Хотя им, конечно, в этой области все не ограничивается.
Об этом, в общем, и речь. Под «использованием» подразумевалось такое использование, которое будет работать на практике, то есть не полный перебор и не рандом. Сам Соломонов в начале 2000-х как раз пытался использовать генетические алгоритмы. Но это, скорее, от безысходности. ГА не универсальны как метод поиска/оптимизации примерно в том же смысле, в котором ИНС не универсальны как метод обучения. Но это в статье не обсуждалось, и вся эта проблематика скрыта в последней фразе: «Как приблизиться к решению проблемы – тема для отдельного непростого разговора. „
На самом деле (хотя в статье об этом не говорится) универсальный метод предсказания по Соломонову и подразумевает усреднение по всем корректным моделям с определенными весами. В этом смысле Ваша идея может быть вполне работоспособной (если она уже кем-то не используется), однако, в статье речь шла о том, что сам метод перекрестной проверки несколько ущербен.
Да, про Колмогоровскую сложность знают многие (но, вероятно, на хабре далеко не все). И принцип минимальной длины описания тоже довольно известен, хотя по прежнему его значение сильно недооценивается (если судить по тому, что в лучших учебниках по ИИ ему уделяют от силы 1 страницу, а то и абзац). Но знать о том, что такое есть, и правильно интерпретировать в рамках проблем машинного обучения — две разные вещи. Второго сильно недостает, из-за чего многие думают, что современное машинное обучение может иметь какое-то отношение к сильному ИИ. Главный же тезис статьи заключается в том, что нужно (для тех, кто заинтересован в сильном ИИ) целенаправленно заниматься универсальными методами обучения.
Т.е. Вы хотите по программе определить, существует ли вход, на котором она зависает.
Нет. Ставится вопрос, существует ли алгоритм, который может проверить для любого данного входа, зависает или останавливается другой алгоритм на данном входе.
Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
Три раза прочитал, так и не понял разницы в этих двух задачах. Действительно, эквивалентные задачи…
Последний раз хочется спросить: когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает? Вы же сами написали, что для любой программы и для любого входа существует алгоритм, который правильно отвечает на вопрос о том, зависает ли данный алгоритм на данном входе.
Короче, вообще непонятно, о чем весь этот разговор, кроме как о неоднозначности естественного языка.
Второй раз разговариваем, и второй раз Вы воюете с ветряными мельницами, превратно интерпретируя слова (или это банальный троллинг?).
В формулировке: «Задача останова заключается в том, что необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается» (работает бесконечно долго)» — написано «в некоторых случаях», а не «по крайней мере в одном». Надеюсь, Вы не будете придираться еще к тому, что если в этой фразе «ИЛИ» считать логическим, то в такой формулировке задача станет очевидно разрешимой? ))
Вроде, достаточно очевидно, что нас интересует не то, что для всех m f(n,m)==1, а то, что его можно определить для всех m. Для практике же важно установить не просто вычислимость f, но и то, какие именно значения она принимает, поэтому здесь и есть некий уклон в сторону останавливаемости при любых исходных данных. Так что в этой формулировке (с точностью до ее нестрогости, вытекающей из неопределенности естественного языка) ошибки нет.
О, это уже ближе к правде. Только с чего Вы взяли, что «Сформулированная Вами проблема — задача о вычислении g.». Откуда там пустой вход-то взялся?
Или Вы не про фразу «Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы.» (создавалось впечатление, что про нее), а про описанную на пальцах идею доказательства? Так она и не претендует на строгость, но саму идею-то передает верно. Еще нигде не встречалось популярное изложение какой-то проблемы, которое не было бы упрощено до некорректности, как выразился Fahrenheit.
Хорошо, в тексте статьи написано немного неаккуратно. Но суть-то в том, что неразрешимой является данная проблема в общем виде, то есть когда необходимо построить алгоритм, который для любого T и для любого Y позволяет определить существование X. Поскольку «для любого Y» при постановке этой проблемы все равно появляется, то абсолютно не важно, трактовать ли задачу останова для конкретного Y или сразу для любого. Вы же вообще не формулирует ту проблему, которая является неразрешимой. В формулировке «останавливается ли данный алгоритм на данном входе» не подразумевается, что «данный алгоритм» и «данный вход» могут быть любыми. Для «данного алгоритма и данного входа» может существовать такой алгоритм, который правильно отвечает на поставленный вопрос.
Если не мистифицировать понятие «знания», то способов представления знаний придумано множество, и они давно и успешно используются в экспертных системах и т.д. Другой вопрос, что представления эти неуниверсальны, но об этом, собственно, и речь в статье.
А программу сам компьютер без вмешательства человека не способен изменить.
Извините, но это откровенная ложь. Никаких принципиальных ограничений на изменение программ самим компьютером нет. Можно лишь согласиться, что методы «слабого» обучения такого изменения не осуществляют, и «сильное» обучение без него обойтись не может.
Что ещё более сомнительно, поскольку для прогнозирования необходимо получать знания, а они пока машине не подвластны.
Для прогнозирования надо строить модели, а это машине вполне подвластно. Знания — это особая форма моделей, построенных в рамках определенных представлений…
Ну, или как вы интерпретируете то, что машина выполняет прогноз погоды?
Вот я и спросил, чему же в Вашем случае обучается компьютер?
Ответ прежний: система учится предсказывать результат отображения между некоторым входом и выходом. Можно добавить — путем построения моделей.
Для большей конкретики нужно разбирать вопрос о структуре этих моделей.
В примере обучение с учителем. Добавлять точки инкрементно или нет — дело вкуса. ИНС при правильном добавлении/удалении нейронов эту задачу могут решать без переобучения, но обобщение и предсказание у них будет плохим, если закон формирования данных в рамках выбранного типа ИНС оказывается непредставимым.
Вообще, переобучение — это смешной эффект, имеющий чисто учебно-методическое значение. Основная же проблема — в отсутствии адекватного обобщения, которое может и не усугубляться переобучением. А отсутствие обобщения для тех же перцептронов очень даже характерно.
Согласитесь, на него затруднительно что-то вразумительное ответить.
Но все же, если пытаться на него ответить, то ответ можно также найти в статье: в конечном итоге интеллектуальная система учится предсказывать результат отображения между некоторым входом и выходом.
Если бы Вы Гёделя, Тьюринга, Чёрча или еще кого в 1930-х годах спросили, а как их абстрактные математические изыскания непосредственно использовать на практике, вряд ли бы получили удовлетворительный ответ. А ведь именно они и привели к созданию компьютеров. С сильным ИИ ситуация аналогичная (если не еще более выраженная). И универсальное обучение — лишь один из аспектов. Сейчас напрямую использовать колмогоровскую сложность для решения практических задач нельзя (но ее упрощенные производные типа принципа минимальной длины описания — очень даже можно, о чем есть соответствующие книжки, если не читали). Но речь, как и в случае с созданием компьютеров, не о непосредственном прикладном использовании сейчас, а о разработке решения для создания сильного ИИ в будущем.
Что касается Воронцова, то, да, он начал направлять по-немногу Журавлевскую школу распознавания образов в нужное русло, но пока смена курса там не слишком значительная.
Насчет поиска алгоритмов. В базовых абстрактных методах универсального обучения, да, подразумевается перебор всех машин Тьюринга. Но всем понятно, что за реалистичное время можно перебрать только «экспоненциально малое» число программ. В простых практических реализациях этого подхода вместо прямого перебора используются генетические алгоритмы или что-то похожее. Но как было сказано в другом комменте, это тоже не то. Реальное решение этой задачи — это «ИИ-полная» проблема, но фишка в том, что и обратное верно. То есть нельзя построить универсальную систему обучения без создания реального сильного ИИ, как и нельзя построить реальный сильный ИИ без построения универсальной системы обучения. Здесь нужно выходить за рамки чистого машинного обучения и рассматривать проблему сильного ИИ в комплексе, только тогда вывод нужной алгоритмической модели среды можно будет организовать не как какой-то простой универсальный (но, естественно, неэффективный) переборный метод, а как направленное конструирование. Однако в паре абзацев описать идею решения этой проблемы не получится.
К примеру, у нас есть некий универсальный язык программирования. Сложности моделей, выраженные на этом языке, будут пропорциональны 2^-L, где L — длина соответствующей программы. Но если создаем некую библиотеку функций, то те программы, которые этими функциями будут пользоваться, окажутся существенно короче (вероятнее), чем если бы их писали с нуля. При этом библиотека никак не сужает универсальность в целом. Также работает и человеческий язык: на основе элементарных блоков создаются более высокоуровневые блоки, отвечающие за некие полезные фрагменты моделей (которые, к тому же, как вы правильно заметили, можно передавать от одного агента другому).
Но это лишь один из простейших (важных, но недостаточных) механизмов того, как без ущерба для универсальности можно повышать эффективность обучения.
А вот то, что «если работа программы не ограничена во времени и нужно получить не абсолютный результат, а всего лишь улучшить имеющийся» — уже не совсем так. Действительно, следующей же идеей по развитию универсального метода обучения является организация перебора моделей в условиях ограниченных вычислительных ресурсов путем параллельного выполнения всех алгоритмических моделей, на каждую из которых выделяется доля ресурсов, пропорциональная ее алгоритмической вероятности. Это так называемые поиск Левина (LSearch). Кстати, из него следует интересное определение сложности по Левину, которое расширяет сложность по Колмогорову (но это отдельная тема). Собственно, Соломонов (а также Хаттер) и опирались на LSearch, оптимальность которого доказана с точностью до мультипликативной константы. К сожалению, для реальных задач эта константа может быть огромной. Как говорил сам Левин, только фрики-математики могут считать число 2^500 конечным.
Короче, для реального сильного ИИ полный перебор, пусть даже и хорошо организованный, явно не подходит. Здесь нужна самооптимизация, чтобы превратить мультипликативную константу в аддитивную (по Шмидхуберу), а также набор априорных метаэвристик, чтобы от эту аддитивную константу тоже максимально уменьшить.
Имеем чисто парадоксальную ситуацию. С одной стороны, есть абсолютно очевидный тезис (хотя, не исключено, не все с ним согласятся). А с другой стороны, когда доходит до дела, этот тезис усиленно игнорируется. За деревьями становится не видно леса. В частности, за огромной кучей частных результатов в области машинного обучения напрочь теряется ее конечная цель.
А Вы говорите, не скрывают :)
За ссылку на лекцию спасибо, послушаю, хотя есть подозрение, что там будет про классические результаты.
Публикации Соломонова есть здесь:
world.std.com/~rjs/pubs.html
Хотя им, конечно, в этой области все не ограничивается.
Значит, мы все-таки одинаково понимаем проблему останова.
Нет. Ставится вопрос, существует ли алгоритм, который может проверить для любого данного входа, зависает или останавливается другой алгоритм на данном входе.
Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
Три раза прочитал, так и не понял разницы в этих двух задачах. Действительно, эквивалентные задачи…
Последний раз хочется спросить: когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает? Вы же сами написали, что для любой программы и для любого входа существует алгоритм, который правильно отвечает на вопрос о том, зависает ли данный алгоритм на данном входе.
Короче, вообще непонятно, о чем весь этот разговор, кроме как о неоднозначности естественного языка.
Второй раз разговариваем, и второй раз Вы воюете с ветряными мельницами, превратно интерпретируя слова (или это банальный троллинг?).
Вроде, достаточно очевидно, что нас интересует не то, что для всех m f(n,m)==1, а то, что его можно определить для всех m. Для практике же важно установить не просто вычислимость f, но и то, какие именно значения она принимает, поэтому здесь и есть некий уклон в сторону останавливаемости при любых исходных данных. Так что в этой формулировке (с точностью до ее нестрогости, вытекающей из неопределенности естественного языка) ошибки нет.
Или Вы не про фразу «Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы.» (создавалось впечатление, что про нее), а про описанную на пальцах идею доказательства? Так она и не претендует на строгость, но саму идею-то передает верно. Еще нигде не встречалось популярное изложение какой-то проблемы, которое не было бы упрощено до некорректности, как выразился Fahrenheit.