По первому вопросу — упрощение иногда используется (оператор edit) но обычно неэффективно.
Его есть смысл использовать когда результат уже получен и его надо упростить.
Кроме того часто используется parsimony pressure — добавление в фитнесс-функцию пенальти на сложность.
Ну и есть еще методы, прямо учитывающие MDL.
Отдельный вопрос — добро или зло code bloat
Иногда специально вставляют в исходный набор функций возможность формирования интронов.
Считается (но обоснований я не встречал), что в интронах накапливается генетический материал для скачкообразной макроэволюции.
Т.е. там хранятся последовательности, которые где-то когда-то пригодились, но пока не нужны и могут выстрелить позже.
По второму вопросу — даже введение дополнительных функций начинает сильно тормозить процесс, например если мы ищем полином, но добавили тригонометрию — сходимость падает, за счет ложных приближенных решений.
Но тут зависит от ландшафта.
Нам надо найти один единственный пример из многих классов эквивалентности.
И чем больше этот класс — тем больше вероятность его нахождения по разным траекториям.
Вообще попытки задать однозначное представление и свести классы эквивалентности к одному единственному экземпляру сразу снижают сходимость.
Это все однако не теория, а просто мой личный опыт использования таких систем.
Следует еще понимать, что для сложных задач ГП не проводит разделения пространства на независимые компоненты (хотя было много попыток в этом направлении, те же ADF или применение eCGA из ГА-мира).
И потому сходимость на очень сложных задачах плохая и сами задачи решать крайне затратно.
Кто сможет обойти это ограничение — получит большой приз.
в 90-х был любопытный вариант теста Тьюринга обладающий намного большей практической ценностью.
Сравнивали использование патентов, часть из которых были человеческие, часть — сгенерированные ИИ (в частности ГП).
ИИ кстати повторил многие человеческие решения.
Статейку писать сложно, у меня тут уже лежит недописанная статейка по искусственным иммунным системам, добавлять еще сверху в очередь задач бессмысленно.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Работаю, деньги за это получаю.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Nonlinear Dynamics of Crime and Violence in Urban Settings jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
PUSH достаточно серьезно проработан под эти задачи.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Выбор родителей для скрещивания делается так.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Есть смысл примерить на эту задачу язык PUSH (видел реализацию на sf.net), он придуман как раз для таких вещей. И обязательно вставить кроссовер, обычный или двухточечный, организмы смогут обмениваться информацией, сходимость к фитнессу резко повышается. В некоторых вариантах мутации становятся вообще ненужными, т.к. имитируются кроссовером со случайным геномом.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Лично я (лет десять назад) когда требовалась шаблонизация на С делал макросы на m4.
Этот пример выглядел бы так.
sums.h.m4:
dnl $Id$
m4_divert(0)
#pragma GCC dependency "sums.c.m4"
m4_divert(-1)
m4_define([sums_template],[
//! computes a:=a+b where a and b are two $1 arrays of length n
void sums_$1(int n, $1 *a, $1 *b);
])
m4_divert(0)
m4_include(sums.list)
sums.c.m4:
dnl $Id$
m4_divert(0)
#pragma GCC dependency "sums.c.m4"
m4_divert(-1)
m4_define([sums_template],[
void sums_$1(int n, $1 *a, $1 *b)
{
/* computes a:=a+b where a and b are two $1 arrays of length n */
int i;
for(i=0;i<n;i++) a[[i]]+=b[[i]];
}
])
m4_divert(0)
m4_include(sums.list)
Собственно я и сейчас так часто делаю, когда надо.
Имхо препроцессор С уж очень малофункционален, приходится делать так.
С другой стороны возможностей у такого подхода намного больше чем у темплайтов.
В конце концов, почему код должны писать программисты а не роботы-кодогенераторы?
:-)
А в сочетании с FCBF фильтром — вообще вещь классная.
Можно тупо брать случайные паттерны — все равно работает.
Причем далеко не только в sentiment analysis, практически любая классификация относительно длинных текстов.
Это эволюция до ГП.
Вместо кроссовера используется аггломерация.
Т.е. если программа находит паттерн в другой программе, то она инкорпорирует найденную в себя или выполняет ее в своем контексте.
Это намного менее жесткие требования чем кроссовер.
И более похожие на биологию и полимеризацию в химии.
А по ограничениям ГП, все верно.
В ГП много чего нет, инкрементное обучение или даже простой дрейф концепции для него практически не работает.
Но при этом работает в природе, где есть много не учитываемого ГП — тот же горизонтальный перенос генов.
С кроссовером кстати есь такой момент, что он нужен как дополнительная эвристика.
Стартуя с МонтеКарло можно получить на выходе репликатор.
Что при обеспечении передачи информации с шумом ниже шенноновского порога гарантирует мутации.
И стартует примитивную дарвиновскую динамику, дающую лучшую сходимость чем Монте-Карло.
Т.е. дарвиновская динамика получается с вероятностью 100%, если шум не нулевой и меньше порога.
Следующий этап — кроссовер или его аналоги связанные с взаимодействием экземпляров.
До него каждый был сам за себя и никак не взаимодействовал с соседями, разве что борясь за ресурс.
После — популяция меняет динамику.
И вот насколько закономерно возникает прямое взаимодействие геномов в дарвиновской системе без кроссовера — это вопрос.
И насколько закономерно это взаимодействие переходит в кроссовер, вообще насколько кроссовер является универсальным методом или частным случаем.
В живой системе есть ведь и восстановление поврежденных участков ДНК, а в ГП — нету таких аналогов.
На практике я часто использую ГП (точнее уже давно GE — grammatical evolution), как генератор гипотез.
До определенного предела он работает очень хорошо.
Дальше — надо про него забывать.
По поводу тьюринговской полноты агентов (безотносительно ГП) — тут вот такая штука.
Если мы ставим задачу оптимального агента в дискретном времени,, то получается что
1. Он должен рассчитать оптимальную стратегию за один тик смены внешних условий (хотя оптимальная стратегия может быть просто ожиданием завершения расчета с переносом действий в будущее).
2. Процесс расчета не должен занять памяти/ресурсов больше определенного конечного значения.
Т.е. по крайней мере эта часть агента (расчет стратегии) уже не может являеться алгоритмически полной просто в силу условий задачи.
Тут есть лазейка в том, что конечный автомат может выдавать на выходе текст, представляющий собой алгоритмически полную программу для UTM.
Но я бы ее не переоценивал.
Разумным кажется искать решение не в области алгоритмически полных программ а в области автоматов.
Но есть и промежуточное решение.
Вероятностные автоматы, недетерминированные языки и прочий вивариум, не вспоминаемый в приличном обществе. Причем вероятностные программы зачастую имеют лучшую эффективность в среднем, чем детерминированные.
А теорема Туракайнена об эквивалентности имеет место похоже не для всех объектов подобного класса, тут надо смотреть подробнее.
Я встречал точку зрения, что вероятностные автоматы и их аналоги не являются конструктивными объектами. Не то чтобы я понимал почему так, в споры интуиционистов и конструктивистов эмпирику лучше не лезть — побьют представители обоих партий.
:-)
Но я бы искал решение задачи именно в этой области — недетерминированных конечных вычислительных структур с гарантированным временем выполнения — автоматов, языков, каких-либо других объектов.
Да, разумеется, ГП этоне ГА.
Но насчет полноты — как сделать.
Язык PUSH, насколько я понимаю, полный — циклы там заменены на проход по списку.
И на практике он часто дает очень неплохое качество, например на небольших объемах он выводил мне деревья решений намного лучше чем C4.5 или CART.
Мне сложно представить себе нейронную сеть, которая вывела бы в символьной форме корни квадратного уравнения.
ГП это может.
Разумеется в ГП может быть получен любой алгоритм, так же как и любой алгоритм может быть получен методом Монте-Карло за бесконечное время.
:-)
Проблема в цене вопроса.
И сложностей там хватает, да.
Практически со всем согласен, на уровне интуиции, без доказательств, дедукция мне тоже кажется неэффективной.
Да и пробовали ее по всякому, ранний ИИ ее включал в разных вариантах, а результат не очень-то соответствовал.
Нельзя сказать что там проверили все, но чтобы найти новое придется перелопатить много.
В следующем году я планирую вернутся к генетическому программированию.
В этом подходе есть несколько позитивных моментов.
1. Тьюриговская полнота модели.
2. Не очень хорошее покрытие теорией, что дает возможность найти что-то новое, теоремы шим не хвататет для полного понимания процесса.
3. Тот простой факт, что природа со всеми ее ресурсами так же пошла по этому пути. И что даже живые нейронные сети появились из генома, не говоря уде об естественом интеллекте (что бы этот термин не означал).
4. Ряд интересных наблюдений в биологии.
Вот с последним пунктом достаточно весело получается.
Как ни странно, биологи знают то, что не учитывают математики.
В математической и инженерной литературе например рекомендуют параметры ГП просто подбирать (!).
А в биологических моделях предполагается что
1. Передача информации от родителя к потомку формирует канал связи с Шенноновским ограничением (если учитывать мутации как шум). Если частота мутаций перекрывает ширину канала, то популяция теряет информацию.
2. В живых системах практически всегда реальный объем передаваемой информации лежит очень близко к шенноновскому порогу, на уровне выше 99%.
Достаточно интересная точка зрения с частичным математическим анализом может быть найдена еще в одной старой книжке лауреата Нобелевки по химии: lib.mexmat.ru/books/9491
Причем там он показывает вариант решения самоорганизации с другой стороны, непривычной математикам, хотя и пользуясь матаппаратом в полной мере и решая проблему потенциально неограниченного накопления информации в живых системах.
А ведь проблема модулярности и неограниченного накопления информации в ГА и ГП есть, и стоит очень остро, реально ГП отлично создает структуры, а ГП с локальной оптимизацией — законченные модели.
Но — на относительно небольших объемах данных, уменьшая сходимость по мере приближения к оптимуму.
Если же заставить его выделять общие крупноблочные структуры, доказывать что эти структуры составляют полный базис и разрешить системе расти вверх, укрупняя блоки и накапливая информацию, то проблема «серебряной пули» может быть и решена.
Может быть и нет.
Но то, что есть сегодня в публикациях (eCGA, CGP, ADF и многие другие) работает на отдельных задачах. А более общего метода нет.
PS
В любом случае хочу пожелать вам удачи в вашем поиске.
Как эмпирик, я хорошо представляют какие задачи можно будет решать подобными инструментами, созданными теоретиками.
Это серьезная работа, которая стоит хорошего приза.
Генетическое программирование является тьюринговски полным.
Другой вопрос, что там своих проблем хватает.
Однако сам факт что природа основывается на них привлекает к ним внимание.
Я считаю что логика (т.е. логика первого порядка на ZFC базе) мягко говоря непрактична.
Однако Ленатовские программы были относительно успешны.
Он соединял логически непротиворечивые островки знаний (микротеории).
И мне кажется что конечная система могла бы иметь вид набора таких микротеорий плюс статистическая функция выбора и сшивки таких теорий.
Человек, кстати тоже имеет такую «кусочно-непрерывную» организацию знаний. В детстве мама говорит нам что драться не хорошо, а в школе наоборот доказывают экспериментом полезность агрессии.
В результате дома и в школе ребенок применяет разные стратегии, гарантирующие ему вознаграждение, продолжая эту линию во взрослом состоянии.
Но если говорить о машине Геделя, то я бы смотрел немного шире.
В описании используются термины «доказательство». Но если мы, например, работаем с вероятностями, то можно доказывать что данная стратегия работает не всегда, а в большинстве случаев (статистические кванторы, если вы читали такую древность как lib.mexmat.ru/books/55118).
И доказательство может выглядеть не как абсолютная гарантия полезности (как в машине Геделя), а как более высокая вероятность.
Разумеется такое направление не соответствует определению машины Геделя в точности.
Но мне кажется полезным развитием концепции — использование статистических техник в условиях нехватки ресурсов и времени, и использовании логики для систематизации полученных знаний.
Еще один плюс машины Геделя — ее рефлексивность.
Живые системы имеют гораздо большую степень свободы в области самомодификации и самонаблюдения чем искусственные.
Как я писал в комментах ранее, я занимался искусственными иммунными системами, там рефлексия практически абсолютна, вплоть до скоростной подстройки генома на лету.
Рефлексивные системы относительно плохо исследованы, а в практическом программировании прямо запрещены.
Но мне кажется, что искать надо именно в этой области.
Поэтому я, кстати и упоминал Learning Classifiers System — это очень ранняя разработка, современник генетики, однако обладающая высокой степенью рефлексии.
Имхо проблема агентов в меняющейся среде не сильно коррелирует с универсальным решением задач.
Здесь речь идет скорее об оптимальном использовании ресурсов, критичных для агентов.
Например система с поддержкой дрейфа концепции может иметь разное характерное время реакции, и, следовательно, адаптируясь к медленным изменениям среды не сможет быстро перестроится при резких изменениях, будет более точной и глубокой, но и более инерционной.
Т.е. мы получаем дополнительную степень свободы, которая впрочем тоже может быть оптимально определена из наблюдений этой окружающей среды.
Вообще когда мы говорим о доказательствах в области теории алогитмов, надо понимать, что большинство из них — это подсчет количества ангелов на кончике иглы. Фундаментальные вопросы связаны с бесконечностью языков, неограниченностью времени вычисления и приводят в большинстве случаев к канторовским множествам.
Пример — супер-тьюринговская машина, реализующая парадокс Зенона.
:-)
В реальном мире не существует бесконечных языков. Есть только конечные способы их конструкции.
Более того, не существует парсеров бесконечных языков, везде ограничение по глубине рекурсии.
Работая же в поле ограниченных конечных данных, мы уходим от многих проблем, порожденных трансфинитной аксиоматикой, например проблема останова Тьюринг-машины с конечной памятью и конечным временем вычисления — в принципе не стоит, нет такой проблемы.
Это тоже надо принимать во внимание.
Чем мне нравится подход в машине Геделя — изначальная ориентация на ограниченность ресурсов.
Я не считаю, что это конечная точка развития, но направление достаточно интересное.
И имхо если заменить поиск доказательства на статистику и расслабить требования к доказанному — эта штука будет намного полезнее на практике.
Достаточно сложно описать не раскрывая сущность данных и аналитики.
Как показательный пример подобного поведения я могу привести такую вещь из химии как реакция Белоусова-Жаботинского.
Авторы этой работы не могли опубликовать ее 8 лет, просто потому что эксперты в журналах не могли поверить в автоколебательные процессы на практике.
И смотрели на авторов как на Петриков.
Я отнесся к экспертам как к черному ящику. Т.е. для измерения функции отклика сначала пропустил через них небольшой массив случайных данные.
И сделал обычные измерения качества на реальном датасете, на рынок не выпускал, слишком дорого было бы.
На случайных данных большинство вердиктов лежали в красной зоне, что было вполне ожидаемо, так я прикинул ошибку экспертов.
Цвет вердикта (не данных) я определял просто — опросом и наблюдением за действиями эксперта.
Красная зона считалась если эксперт давал быстрый негативный вердикт без глубокого анализа.
В таких случаях он обосновывал вердикт одним единственным критерием — вот здесь так, а так нельзя.
Причем на вопрос — а почему нельзя? — следовал недоуменный взгляд и попытки обоснования типа
1. Потому что так нельзя
2. Потому что и так видно
3. Потому что так принято у нас
4. Здравый смысл подсказывает
5. Ты не специалист, не понимаешь
Если эксперт смотрел на данные, и начинал полную процедуру проверки, грузил инструментарий и вообще обрабатывал данные более часа — его вердикт считался из зеленой зоны. Независимо от того был он позитивным или негативным.
Существует область быстрых вердиктов.
И область негативных вердиктов.
В той задаче они пересакались не менее чем на 95%.
Я вообще не вспомню ни одного быстрого позитивного вердикта, максимум что я мог получить — «интересно, надо посмотреть поглубже». И вердикт переходил в зеленую зону.
Пересечение двух областей и давало красную зону для отдельно взятого эксперта.
А объединение красных зон всей экспертной группы создавало непробиваемую стену.
Это вполне понятный результат, цена ошибки была достаточно высока в той задаче.
Однако даже в случае с симметричной функцией потерь быстрые вердикты в большинстве случаем негативные.
Интересно провести нормальный человеческий эксперимент с замером, контрольной группой и оценкой пересечения.
Заготовка есть, но не хочется сырую статью кидать. А между заказами надо быть внимательным, иначе непонятно где буду кормиться следующий год.
Кроме того там тоже много философии — меня как раз интересовала теория опасности, алгоритмы — это сырое.
Полностью рефлексивный взгляд на систему, которая обеспечивает целостность себя и защищает от любой внешней угрозы — он очень интересен.
Но там кроме философии пока ничего нет.
Увы.
Как я писал в исходной публикации — это точка зрения технаря. Т.е. человека которому платят за конкретный законченный продукт.
Соответственно оплата производится за определенные характеристики продукта — вполне себе объективные.
Именно поэтому разделение на слабый и сильный ИИ мне кажется очень непрактичным. Когда дело доходит до рынка — никто не будет платить за холодильник, охлаждающий ниже температуры тела человека. Никто не купит машину, разгоняющуюся выше скорости человека.
Везде где техника наступала — человек переставал быть мерилом всех вещей.
Именно поэтому я считаю что «сильный» или «слабый» ИИ — это вопросы философов.
Не производителей и инженеров.
И если заказчик хочет от меня антивирус — то я должен обеспечить ему допустим XX% детекции при 0.XX% false positive rate на стандартном тестовом сете.
Если заказчик хочет детектор дорожных знаков, то мы берем стандартизированный датасет и получаем YY% детекции при 0.YY% FP.
Т.е. любая задача в технологии должна быть сведена к числам на стандартных данных.
Просто чтобы любой мог взять моего конкурента и увидеть там меньше или больше.
Просто чтобы клиент знал что его не надувают.
Нужна точка отсчета. И точка отсчета должна быть объективная и воспроизводимая.
Иначе каждый конкурент будет подбирать свои выгодные себе условия.
И каждый производитель будет показывать свои цифры, которые на самом деле ничего не значат.
И вот получается что ни для какого ИИ таких показателей нет.
Тест Тьюринга — субъективен по определению, более того, я не уверен, что он вообще может называться ИИ. Т.е. для Тьюринговского ИИ такая тестовая оценка в принципе невозможна.
Для Геделевского ИИ можно наработать достаточно плотный массив данных для проверки.
Но его пока нет.
И даже Шмидхуберовской машине Гёделя (которая отчасти сомнительна) потребуются многие миллиарды лет, чтобы научиться решать даже не очень сложные задачи.
А сколько лет потребуется машине Тьюринга с бумажной лентой для расчета корня уравнения четвертой степени?
Мы говорим о концепции и классах эквивалентности.
Реализации могут быть разные и совсем не совпадающие с классической.
Learning classifier systems в теории были не сильно хуже машины Геделя. И даже на практике работали кое-где. Но для них не было такого математического обоснования, это просто подсмотренное у природы.
Любой универсальный решатель имеет индуктивное смещение
Хм, а можно ссылку на это?
Я всегда считал что Колмогоровская сложность наблюдаемой среды однозначно определяет такие вещи.
Или вы имеете в виду чисто логические средства, без статистических?
Если какой-то решатель чуть лучше в одной среде, то он будет чуть хуже в другой среде.
NFL теорема, не всегда правда применимая.
Ни один решатель не обладает преимуществом над другими на классе всех возможных сред.
А я вот думаю что С4.5 будет по крайней мере не хуже подбрасывания монетки в любой среде.
И индуктивного смещения, что характерно, не требует.
PS
Я обязательно посмотрю сайт вашей группы, достаточно интересно пообщаться с людьми занимающимися этим вопросом с другой стороны.
Я просто не уверен что успею, я сейчас заканчиваю одну работу и начинаю новую, поэтому могу что-то писать.
И как только начнется работа — мне будет сложно продолжать коммуникации или писать статьи, просто по нехватке времени.
В AIS действительно значимых алгоритмов мало. Но зато там есть Danger Theory. И вот эта концепция мне кажется важнее всех алгоритмов.
Его есть смысл использовать когда результат уже получен и его надо упростить.
Кроме того часто используется parsimony pressure — добавление в фитнесс-функцию пенальти на сложность.
Ну и есть еще методы, прямо учитывающие MDL.
Отдельный вопрос — добро или зло code bloat
Иногда специально вставляют в исходный набор функций возможность формирования интронов.
Считается (но обоснований я не встречал), что в интронах накапливается генетический материал для скачкообразной макроэволюции.
Т.е. там хранятся последовательности, которые где-то когда-то пригодились, но пока не нужны и могут выстрелить позже.
По второму вопросу — даже введение дополнительных функций начинает сильно тормозить процесс, например если мы ищем полином, но добавили тригонометрию — сходимость падает, за счет ложных приближенных решений.
Но тут зависит от ландшафта.
Нам надо найти один единственный пример из многих классов эквивалентности.
И чем больше этот класс — тем больше вероятность его нахождения по разным траекториям.
Вообще попытки задать однозначное представление и свести классы эквивалентности к одному единственному экземпляру сразу снижают сходимость.
Это все однако не теория, а просто мой личный опыт использования таких систем.
Следует еще понимать, что для сложных задач ГП не проводит разделения пространства на независимые компоненты (хотя было много попыток в этом направлении, те же ADF или применение eCGA из ГА-мира).
И потому сходимость на очень сложных задачах плохая и сами задачи решать крайне затратно.
Кто сможет обойти это ограничение — получит большой приз.
Сравнивали использование патентов, часть из которых были человеческие, часть — сгенерированные ИИ (в частности ГП).
ИИ кстати повторил многие человеческие решения.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Сам я его изучал по вот этой книжке.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Хотя вот есть например такое издание как jasss.soc.surrey.ac.uk/JASSS.html специализирующееся на Agent Based Modeling (ABM)
Со своими фреймворками и симуляторами.
Например вас наверное заинтересует вот такая публикация jasss.soc.surrey.ac.uk/14/2/5.html
Названия статей там говорят сами за себя
Nonlinear Dynamics of Crime and Violence in Urban Settings
jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
A Virtual Laboratory for the Study of History and Cultural Dynamics
jasss.soc.surrey.ac.uk/14/4/19.html
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game
jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
A Computational Model of Worker Protest
jasss.soc.surrey.ac.uk/14/3/1.html
В общем интересный такой журнальчик, после его статей можно свой оккупай начинать.
:-)
Тоже рекомендую.
Это я к тому привел, чтобы вы не думали, что то, что вы написали — просто игрушка.
На похожих игрушках просчитываются многие реальные серьезные вещи.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией
www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Этот пример выглядел бы так.
sums.h.m4:
sums.c.m4:
А вот строка для мейкфайла:
Ну и файл с определениями:
sums_template(float)
sums_template(double)
sums_template(int)
Собственно я и сейчас так часто делаю, когда надо.
Имхо препроцессор С уж очень малофункционален, приходится делать так.
С другой стороны возможностей у такого подхода намного больше чем у темплайтов.
В конце концов, почему код должны писать программисты а не роботы-кодогенераторы?
:-)
Поменьше халоймеса в коде и побольше гешефта с проектов!
Можно тупо брать случайные паттерны — все равно работает.
Причем далеко не только в sentiment analysis, практически любая классификация относительно длинных текстов.
citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.7571
Это эволюция до ГП.
Вместо кроссовера используется аггломерация.
Т.е. если программа находит паттерн в другой программе, то она инкорпорирует найденную в себя или выполняет ее в своем контексте.
Это намного менее жесткие требования чем кроссовер.
И более похожие на биологию и полимеризацию в химии.
А по ограничениям ГП, все верно.
В ГП много чего нет, инкрементное обучение или даже простой дрейф концепции для него практически не работает.
Но при этом работает в природе, где есть много не учитываемого ГП — тот же горизонтальный перенос генов.
С кроссовером кстати есь такой момент, что он нужен как дополнительная эвристика.
Стартуя с МонтеКарло можно получить на выходе репликатор.
Что при обеспечении передачи информации с шумом ниже шенноновского порога гарантирует мутации.
И стартует примитивную дарвиновскую динамику, дающую лучшую сходимость чем Монте-Карло.
Т.е. дарвиновская динамика получается с вероятностью 100%, если шум не нулевой и меньше порога.
Следующий этап — кроссовер или его аналоги связанные с взаимодействием экземпляров.
До него каждый был сам за себя и никак не взаимодействовал с соседями, разве что борясь за ресурс.
После — популяция меняет динамику.
И вот насколько закономерно возникает прямое взаимодействие геномов в дарвиновской системе без кроссовера — это вопрос.
И насколько закономерно это взаимодействие переходит в кроссовер, вообще насколько кроссовер является универсальным методом или частным случаем.
В живой системе есть ведь и восстановление поврежденных участков ДНК, а в ГП — нету таких аналогов.
На практике я часто использую ГП (точнее уже давно GE — grammatical evolution), как генератор гипотез.
До определенного предела он работает очень хорошо.
Дальше — надо про него забывать.
По поводу тьюринговской полноты агентов (безотносительно ГП) — тут вот такая штука.
Если мы ставим задачу оптимального агента в дискретном времени,, то получается что
1. Он должен рассчитать оптимальную стратегию за один тик смены внешних условий (хотя оптимальная стратегия может быть просто ожиданием завершения расчета с переносом действий в будущее).
2. Процесс расчета не должен занять памяти/ресурсов больше определенного конечного значения.
Т.е. по крайней мере эта часть агента (расчет стратегии) уже не может являеться алгоритмически полной просто в силу условий задачи.
Тут есть лазейка в том, что конечный автомат может выдавать на выходе текст, представляющий собой алгоритмически полную программу для UTM.
Но я бы ее не переоценивал.
Разумным кажется искать решение не в области алгоритмически полных программ а в области автоматов.
Но есть и промежуточное решение.
Вероятностные автоматы, недетерминированные языки и прочий вивариум, не вспоминаемый в приличном обществе. Причем вероятностные программы зачастую имеют лучшую эффективность в среднем, чем детерминированные.
А теорема Туракайнена об эквивалентности имеет место похоже не для всех объектов подобного класса, тут надо смотреть подробнее.
Я встречал точку зрения, что вероятностные автоматы и их аналоги не являются конструктивными объектами. Не то чтобы я понимал почему так, в споры интуиционистов и конструктивистов эмпирику лучше не лезть — побьют представители обоих партий.
:-)
Но я бы искал решение задачи именно в этой области — недетерминированных конечных вычислительных структур с гарантированным временем выполнения — автоматов, языков, каких-либо других объектов.
Но насчет полноты — как сделать.
Язык PUSH, насколько я понимаю, полный — циклы там заменены на проход по списку.
И на практике он часто дает очень неплохое качество, например на небольших объемах он выводил мне деревья решений намного лучше чем C4.5 или CART.
Мне сложно представить себе нейронную сеть, которая вывела бы в символьной форме корни квадратного уравнения.
ГП это может.
Разумеется в ГП может быть получен любой алгоритм, так же как и любой алгоритм может быть получен методом Монте-Карло за бесконечное время.
:-)
Проблема в цене вопроса.
И сложностей там хватает, да.
Да и пробовали ее по всякому, ранний ИИ ее включал в разных вариантах, а результат не очень-то соответствовал.
Нельзя сказать что там проверили все, но чтобы найти новое придется перелопатить много.
В следующем году я планирую вернутся к генетическому программированию.
В этом подходе есть несколько позитивных моментов.
1. Тьюриговская полнота модели.
2. Не очень хорошее покрытие теорией, что дает возможность найти что-то новое, теоремы шим не хвататет для полного понимания процесса.
3. Тот простой факт, что природа со всеми ее ресурсами так же пошла по этому пути. И что даже живые нейронные сети появились из генома, не говоря уде об естественом интеллекте (что бы этот термин не означал).
4. Ряд интересных наблюдений в биологии.
Вот с последним пунктом достаточно весело получается.
Как ни странно, биологи знают то, что не учитывают математики.
В математической и инженерной литературе например рекомендуют параметры ГП просто подбирать (!).
А в биологических моделях предполагается что
1. Передача информации от родителя к потомку формирует канал связи с Шенноновским ограничением (если учитывать мутации как шум). Если частота мутаций перекрывает ширину канала, то популяция теряет информацию.
2. В живых системах практически всегда реальный объем передаваемой информации лежит очень близко к шенноновскому порогу, на уровне выше 99%.
Достаточно интересная точка зрения с частичным математическим анализом может быть найдена еще в одной старой книжке лауреата Нобелевки по химии: lib.mexmat.ru/books/9491
Причем там он показывает вариант решения самоорганизации с другой стороны, непривычной математикам, хотя и пользуясь матаппаратом в полной мере и решая проблему потенциально неограниченного накопления информации в живых системах.
А ведь проблема модулярности и неограниченного накопления информации в ГА и ГП есть, и стоит очень остро, реально ГП отлично создает структуры, а ГП с локальной оптимизацией — законченные модели.
Но — на относительно небольших объемах данных, уменьшая сходимость по мере приближения к оптимуму.
Если же заставить его выделять общие крупноблочные структуры, доказывать что эти структуры составляют полный базис и разрешить системе расти вверх, укрупняя блоки и накапливая информацию, то проблема «серебряной пули» может быть и решена.
Может быть и нет.
Но то, что есть сегодня в публикациях (eCGA, CGP, ADF и многие другие) работает на отдельных задачах. А более общего метода нет.
PS
В любом случае хочу пожелать вам удачи в вашем поиске.
Как эмпирик, я хорошо представляют какие задачи можно будет решать подобными инструментами, созданными теоретиками.
Это серьезная работа, которая стоит хорошего приза.
Другой вопрос, что там своих проблем хватает.
Однако сам факт что природа основывается на них привлекает к ним внимание.
Я считаю что логика (т.е. логика первого порядка на ZFC базе) мягко говоря непрактична.
Однако Ленатовские программы были относительно успешны.
Он соединял логически непротиворечивые островки знаний (микротеории).
И мне кажется что конечная система могла бы иметь вид набора таких микротеорий плюс статистическая функция выбора и сшивки таких теорий.
Человек, кстати тоже имеет такую «кусочно-непрерывную» организацию знаний. В детстве мама говорит нам что драться не хорошо, а в школе наоборот доказывают экспериментом полезность агрессии.
В результате дома и в школе ребенок применяет разные стратегии, гарантирующие ему вознаграждение, продолжая эту линию во взрослом состоянии.
Но если говорить о машине Геделя, то я бы смотрел немного шире.
В описании используются термины «доказательство». Но если мы, например, работаем с вероятностями, то можно доказывать что данная стратегия работает не всегда, а в большинстве случаев (статистические кванторы, если вы читали такую древность как lib.mexmat.ru/books/55118).
И доказательство может выглядеть не как абсолютная гарантия полезности (как в машине Геделя), а как более высокая вероятность.
Разумеется такое направление не соответствует определению машины Геделя в точности.
Но мне кажется полезным развитием концепции — использование статистических техник в условиях нехватки ресурсов и времени, и использовании логики для систематизации полученных знаний.
Еще один плюс машины Геделя — ее рефлексивность.
Живые системы имеют гораздо большую степень свободы в области самомодификации и самонаблюдения чем искусственные.
Как я писал в комментах ранее, я занимался искусственными иммунными системами, там рефлексия практически абсолютна, вплоть до скоростной подстройки генома на лету.
Рефлексивные системы относительно плохо исследованы, а в практическом программировании прямо запрещены.
Но мне кажется, что искать надо именно в этой области.
Поэтому я, кстати и упоминал Learning Classifiers System — это очень ранняя разработка, современник генетики, однако обладающая высокой степенью рефлексии.
Имхо проблема агентов в меняющейся среде не сильно коррелирует с универсальным решением задач.
Здесь речь идет скорее об оптимальном использовании ресурсов, критичных для агентов.
Например система с поддержкой дрейфа концепции может иметь разное характерное время реакции, и, следовательно, адаптируясь к медленным изменениям среды не сможет быстро перестроится при резких изменениях, будет более точной и глубокой, но и более инерционной.
Т.е. мы получаем дополнительную степень свободы, которая впрочем тоже может быть оптимально определена из наблюдений этой окружающей среды.
Вообще когда мы говорим о доказательствах в области теории алогитмов, надо понимать, что большинство из них — это подсчет количества ангелов на кончике иглы. Фундаментальные вопросы связаны с бесконечностью языков, неограниченностью времени вычисления и приводят в большинстве случаев к канторовским множествам.
Пример — супер-тьюринговская машина, реализующая парадокс Зенона.
:-)
В реальном мире не существует бесконечных языков. Есть только конечные способы их конструкции.
Более того, не существует парсеров бесконечных языков, везде ограничение по глубине рекурсии.
Работая же в поле ограниченных конечных данных, мы уходим от многих проблем, порожденных трансфинитной аксиоматикой, например проблема останова Тьюринг-машины с конечной памятью и конечным временем вычисления — в принципе не стоит, нет такой проблемы.
Это тоже надо принимать во внимание.
Чем мне нравится подход в машине Геделя — изначальная ориентация на ограниченность ресурсов.
Я не считаю, что это конечная точка развития, но направление достаточно интересное.
И имхо если заменить поиск доказательства на статистику и расслабить требования к доказанному — эта штука будет намного полезнее на практике.
Как показательный пример подобного поведения я могу привести такую вещь из химии как реакция Белоусова-Жаботинского.
Авторы этой работы не могли опубликовать ее 8 лет, просто потому что эксперты в журналах не могли поверить в автоколебательные процессы на практике.
И смотрели на авторов как на Петриков.
Я отнесся к экспертам как к черному ящику. Т.е. для измерения функции отклика сначала пропустил через них небольшой массив случайных данные.
И сделал обычные измерения качества на реальном датасете, на рынок не выпускал, слишком дорого было бы.
На случайных данных большинство вердиктов лежали в красной зоне, что было вполне ожидаемо, так я прикинул ошибку экспертов.
Цвет вердикта (не данных) я определял просто — опросом и наблюдением за действиями эксперта.
Красная зона считалась если эксперт давал быстрый негативный вердикт без глубокого анализа.
В таких случаях он обосновывал вердикт одним единственным критерием — вот здесь так, а так нельзя.
Причем на вопрос — а почему нельзя? — следовал недоуменный взгляд и попытки обоснования типа
1. Потому что так нельзя
2. Потому что и так видно
3. Потому что так принято у нас
4. Здравый смысл подсказывает
5. Ты не специалист, не понимаешь
Если эксперт смотрел на данные, и начинал полную процедуру проверки, грузил инструментарий и вообще обрабатывал данные более часа — его вердикт считался из зеленой зоны. Независимо от того был он позитивным или негативным.
Существует область быстрых вердиктов.
И область негативных вердиктов.
В той задаче они пересакались не менее чем на 95%.
Я вообще не вспомню ни одного быстрого позитивного вердикта, максимум что я мог получить — «интересно, надо посмотреть поглубже». И вердикт переходил в зеленую зону.
Пересечение двух областей и давало красную зону для отдельно взятого эксперта.
А объединение красных зон всей экспертной группы создавало непробиваемую стену.
Это вполне понятный результат, цена ошибки была достаточно высока в той задаче.
Однако даже в случае с симметричной функцией потерь быстрые вердикты в большинстве случаем негативные.
Интересно провести нормальный человеческий эксперимент с замером, контрольной группой и оценкой пересечения.
habrahabr.ru/post/149291/#comment_5065050
Кроме того там тоже много философии — меня как раз интересовала теория опасности, алгоритмы — это сырое.
Полностью рефлексивный взгляд на систему, которая обеспечивает целостность себя и защищает от любой внешней угрозы — он очень интересен.
Но там кроме философии пока ничего нет.
Увы.
Вот ряд ссылок, но они как раз на алгоритмы.
web.ist.utl.pt/~gdgp/VA/ais.htm
www.dangertheory.com/
Здесь libtissue
www.cs.nott.ac.uk/~jpt/software.html
Вроде некоторые алгоритмы уже в weka попали.
Книжка по иммунокомпьютингу.
lib.mexmat.ru/books/9203
Но это все пена, т.е. работы было проделано очень много, не вопрос, но рабочих продуктов очень мало и в основном в очень узкой сфере.
Соответственно оплата производится за определенные характеристики продукта — вполне себе объективные.
Именно поэтому разделение на слабый и сильный ИИ мне кажется очень непрактичным. Когда дело доходит до рынка — никто не будет платить за холодильник, охлаждающий ниже температуры тела человека. Никто не купит машину, разгоняющуюся выше скорости человека.
Везде где техника наступала — человек переставал быть мерилом всех вещей.
Именно поэтому я считаю что «сильный» или «слабый» ИИ — это вопросы философов.
Не производителей и инженеров.
И если заказчик хочет от меня антивирус — то я должен обеспечить ему допустим XX% детекции при 0.XX% false positive rate на стандартном тестовом сете.
Если заказчик хочет детектор дорожных знаков, то мы берем стандартизированный датасет и получаем YY% детекции при 0.YY% FP.
Т.е. любая задача в технологии должна быть сведена к числам на стандартных данных.
Просто чтобы любой мог взять моего конкурента и увидеть там меньше или больше.
Просто чтобы клиент знал что его не надувают.
Нужна точка отсчета. И точка отсчета должна быть объективная и воспроизводимая.
Иначе каждый конкурент будет подбирать свои выгодные себе условия.
И каждый производитель будет показывать свои цифры, которые на самом деле ничего не значат.
И вот получается что ни для какого ИИ таких показателей нет.
Тест Тьюринга — субъективен по определению, более того, я не уверен, что он вообще может называться ИИ. Т.е. для Тьюринговского ИИ такая тестовая оценка в принципе невозможна.
Для Геделевского ИИ можно наработать достаточно плотный массив данных для проверки.
Но его пока нет.
А сколько лет потребуется машине Тьюринга с бумажной лентой для расчета корня уравнения четвертой степени?
Мы говорим о концепции и классах эквивалентности.
Реализации могут быть разные и совсем не совпадающие с классической.
Learning classifier systems в теории были не сильно хуже машины Геделя. И даже на практике работали кое-где. Но для них не было такого математического обоснования, это просто подсмотренное у природы.
Хм, а можно ссылку на это?
Я всегда считал что Колмогоровская сложность наблюдаемой среды однозначно определяет такие вещи.
Или вы имеете в виду чисто логические средства, без статистических?
NFL теорема, не всегда правда применимая.
А я вот думаю что С4.5 будет по крайней мере не хуже подбрасывания монетки в любой среде.
И индуктивного смещения, что характерно, не требует.
PS
Я обязательно посмотрю сайт вашей группы, достаточно интересно пообщаться с людьми занимающимися этим вопросом с другой стороны.
И как только начнется работа — мне будет сложно продолжать коммуникации или писать статьи, просто по нехватке времени.
В AIS действительно значимых алгоритмов мало. Но зато там есть Danger Theory. И вот эта концепция мне кажется важнее всех алгоритмов.