Форум программистов, компьютерный форум, киберфорум
Наши страницы
Искусственный интеллект
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
1

Об эвристиках

02.04.2016, 19:05. Просмотров 1722. Ответов 18
Метки нет (Все метки)

Я сам не специалист по ИИ, но по своей первой специальности поверхностно изучал адаптивные системы управления (упирались больше на неадаптивные СУ).

Со временем у меня выработалась следующая мысль: для успешного исследования и понимания основ ИИ нужно знать основные эвристики. Эвристика - это алгоритм, который позволяет с удовлетворительной успешностью угадывать неизвестные данные (как правило, неизвестные исходы событий или значения случайной величины).

Вот некоторые из эвристик, сформулированных мною (самые крутые, самые базовые):
1) Эвристика вероятности: вероятность события равна частоте события (для случайной величины: распределение вероятностей совпадает с распределением частот).
2) Уточненная эвристика вероятности: вероятность события равна частоте события за релевантный период. Релевантный период - это такой период времени, который наиболее близок к неизвестному событию по времени.
3) Статистические эвристики: метод максимального правдоподобия, метод моментов и т.д.
4) Эвристика постоянства: данный параметр не меняется во времени (константа).
5) Эвристика стабильности: если связанные параметры не меняются, значит и неизвестный параметр также не изменится.
6) Эвристика гладкости: если связанные параметры изменились незначительно, значит и неизвестный параметр изменится незначительно.
7) Эвристика нестабильности: если хотя бы один связанный параметр изменился значительно, значит и неизвестный параметр изменится значительно.
8) Вэйвлет-эвристика: при незначительном изменении связанного параметра неизвестный параметр либо практически не изменится, либо изменится значительно.
9) Эвристика ассоциативности: если неизвестный и связанный параметры однородны, то информацию о связанном параметре можно применить к неизвестному параметру.

Эвристика считается хорошей, если она часто срабатывает. В том случае, когда эвристика не срабатывает, то можно говорить, что имеет место "антиэвристика". Для различных данных применимы различные наборы эвристик, критерием успешности сильного искусственного интеллекта является определение оптимального набора эвристик в конкретной среде.

Цель этой темы - выяснить, где в литературе можно почитать о научных достижениях по этой проблематике.
0
rrr3
99 / 33 / 1
Регистрация: 13.10.2015
Сообщений: 395
02.04.2016, 22:25 2
"Самой базовой" эвристикой можно считать эвристику (саму идею создания разных (!) "эвристик") генерации разных, не(!) строго предопределенных эвристик.
В биологии одним(!) из вариантов реализации такой эвристики является мутагенез ДНК. Результатом (одним из многих) этой эвристики является человек, правда из-за иных особенностей биологических процессов для этого потребовался не один год. В науке одним из результатов такой эвристики является прогулка человека по Луне.
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
03.04.2016, 06:09  [ТС] 3
В принципе согласен. Так и назвать "эвристика нашего мира" - в нашем мире есть несколько десятков успешных эвристик [и список приложить].
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
04.04.2016, 19:17  [ТС] 4
Каюсь, некоторые мои сентенции могут быть недостаточно понятны моим потенциальным собеседникам. Поэтому добавлю по нескольку примеров для разъяснения каждой эвристики.
Цитата Сообщение от Mikhaylo Посмотреть сообщение
4) Эвристика постоянства: данный параметр не меняется во времени (константа).
Эта эвристика, пожалуй, должна стоять на первом месте. Константы формируют неизменный базис нашего мира. Когда мы просыпаемся утром, мы выполняем одни и те же действия: делаем зарядку, чистим зубы, готовим завтрак, гладим галстук-рубашку - все в нашем мире определенно и постоянно.
Может возникнуть нестандартная ситуация, когда почувствовалась боль в горле (ангина), тогда наш утренний распорядок серьезно меняется - нужно, допустим, вызвать врача. В этом случае эвристика постоянства нарушается, что допустимо.
Эвристика постоянства - это очень важный фактор для сохранения нашей интеллектуальной энергии, она позволяет выполнять действия на автоматизме.
Роботу важно применять эвристику постоянства при перемещении в условиях отсутствия информации с визуальных сенсоров (как будто человек перемещается в темноте). Также человек выполняет некоторые действия, не глядя на объект, например, быстро спускается по лестнице, не глядя под ноги. Применение эвристики постоянства здесь неизбежно!
Надо, конечно, понимать, что при определенных условиях эвристика постоянства не применима. Тут все очень просто: эта эвристика неудачна в том случае, когда наблюдается изменчивость, непостоянство. В нашем реальном мире есть феномен постоянства, поэтому эта эвристика заведомо выгодна!

Очевидно, простой интеллект, который не будет использовать эвристику постоянства, будет проигрывать эвристическому интеллекту. Для простого интеллекта потребуется датчик положения объекта, в то же время эвристический интеллект будет находить объект, основываясь на своем предшествующем опыте. Самое замечательное, что наш опыт подтверждает успешность нахождения объектов даже в условии устаревания информации. Мы легко добираемся до работы, до дома, до магазина и т.п., не используя GPS или другие датчики. Эвристический интеллект явно выигрывает - ему не нужны датчики и значит он конструктивно проще!

Иногда интуитивно кажется, что все эвристики сводятся к эвристике постоянства. Но это не умаляет достоинства других эвристик. Имеется уверенность, что алгоритм ИИ должен безусловно и в первую очередь проверять гипотезу постоянства и такой алгоритм будет успешнее других.
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
10.05.2016, 18:51  [ТС] 5
Наткнулся на курс "Машинное обучение" Воронцова К.В. и понял, что это именно то, что нужно мне!
Прослушал почти 4 лекции и уже идентифицировал часть эвристик, которые я приводил выше.
1. Гипотеза компактности (сравнить с эвристикой постоянства, стабильности и гладкости)
2. Логическая эвристика (эту эвристику я не перечислял)
3. Линейный классификатор (это тоже не приводил, но она лежит в основе нейронных сетей; пока еще не дослушал до конца эту лекцию)

Добавлено через 3 минуты
Возможно лектор хорошо понимает роль эвристик в данной сфере, но почему-то он очень туманно обошел этот вопрос, иногда сетует, что часто приходится некоторые параметры подбирать эвристически, а не научно. Эвристическую часть считает ненаучным направлением, а "инженерным искусством", "талантом", "даром видения" и т.п.
0
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
11.05.2016, 18:13 6
Mikhaylo
Мне не совсем понятно, что эвристика должна быть величиной
постоянной. Вероятно одного этого мало. Допустим живут два
человека. Один в лесу, другой в столице. Кто из них умнее?
Другой пример
Жизнь на крайнем севере требует от человека много сил и времени.
Поэтому цивилизации возникли там, где теплый климат. То есть
постоянная зима....?
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
22.06.2016, 05:54  [ТС] 7
С 4-й по 7-ю лекцию был достаточно тяжелый материал, его нужно закреплять практикумом, к тому же там не попадались значимые эвристики. Потом прослушал достаточно легковесную 8-ю лекцию (про временные ряды): и вот новые эвристики - стационарные процессы (сезонность), нестационарные процессы (сезонность + тренд). Это почти соответствует:
Цитата Сообщение от Mikhaylo Посмотреть сообщение
4) Эвристика постоянства: данный параметр не меняется во времени (константа).
5) Эвристика стабильности: если связанные параметры не меняются, значит и неизвестный параметр также не изменится.
если стационарность и нестационарность смешать с эвристикой периодичности, которую я не приводил.
Также в лекции рассматривается эвристика квазистационарности (термин в лекции не дан), это фактически:
Цитата Сообщение от Mikhaylo Посмотреть сообщение
8) Вэйвлет-эвристика: при незначительном изменении связанного параметра неизвестный параметр либо практически не изменится, либо изменится значительно.
Рассматривается следующий квазистационарный процесс: взяты несколько алгоритмов оценки неизвестного значения, из них выбирается тот лучший, который в предыдущие моменты времени выдавал наиболее точный результат, результат лучшего алгоритма берется для определения общей оценки. Квазистационарность данного процесса означает, что через определенные промежутки времени следует ожидать, что возможно лучшим алгоритмом оценки станет другой алгоритм. Таким образом общая оценка берется от одного алгоритма, но иногда этот алгоритм меняется на другой.

Сейчас слушаю лекцию №9 (про применение байесовской формулы в машинном обучении). Здесь используется что-то вроде эвристики ассоциативности. Ну и применена эвристика вероятности, конечно же.
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
28.06.2016, 17:34  [ТС] 8
Как-то незаметно для моего внимания прошли мимо две очень важные эвристики, хотя они красной нитью проходят через каждую лекцию машинного обучения:
- эвристика зашумленности данных (прежде всего аддитивная или мультипликативная помеха)
- эвристики неполности и переизбыточности информации (неполность информации - это отсутствие некоторых объектов в обучающей выборке, переизбыточность - это присутствие некоторых объектов в обучающей выборке в виде ненужных дублей, в том числе в зашумленном виде, поэтому встает задача идентификации и отброса дублей для избежания переобучения)
0
VTsaregorodtsev
578 / 531 / 77
Регистрация: 19.02.2010
Сообщений: 1,934
29.06.2016, 22:02 9
Цитата Сообщение от Mikhaylo Посмотреть сообщение
переизбыточность - это присутствие некоторых объектов в обучающей выборке в виде ненужных дублей, в том числе в зашумленном виде, поэтому встает задача идентификации и отброса дублей для избежания переобучения
А то, что при отбрасывании дублей изменятся законы распределения (как "одномерные", по каждому признаку, так и многомерный единый) и станут не похожи на те, которые соответствуют генеральной совокупности - это не настораживает?

Т.е. моделировать (учить) будем реал (ген.совокупность) - или сферического коня в вакууме (тенденциозно кастрированную выборку)? Если второе - то почему/зачем? Почему/откуда у Вас возникает гипотеза, что кастрированный мерин сможет породить что-то полезное?
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
30.06.2016, 05:42  [ТС] 10
Да, Вы правы. Я имел в виду не избыточность отдельных объектов в выборке, а избыточность признаков-параметров. Например, в задачах регрессии они могут приводить к переобучению из-за того, что образуют линейную комбинацию с другими признаками. То есть существуют условия, когда избыточные данные можно обнаружить, но не всегда.
0
VTsaregorodtsev
578 / 531 / 77
Регистрация: 19.02.2010
Сообщений: 1,934
03.07.2016, 21:25 11
Цитата Сообщение от Mikhaylo Посмотреть сообщение
избыточность признаков-параметров
Совершенно надуманная проблема.
При нормальном регуляризаторе - ни на что не влияет.
Более того, иногда чем больше скоррелированных признаков - тем лучше, т.к. аддитивный (к каждому признаку) шум будет всё-таки отдельным для каждого признака. А раз шум в признаках не скоррелирован - то простым усреднением даже сильный по амлитуде шум хорошо чистится.

Методов отбора информативных признаков - тоже вагон и маленькая тележка. Как работающих только с выборкой данных (т.е. model free) - так и работающих с какой-то обученной/идентифицированной/синтезированной моделью=зависимостью и вычисляющих информативность "с точки зрения" этой модели.
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
04.07.2016, 08:34  [ТС] 12
Я тоже поначалу не заметил этой эвристики - эвристики избыточности.
Получил обучающую выборку - первая мысль - выявить несущественные признаки (расставить нулевые веса). Это эвристика, хорошо работающая в большинстве случаев.

Добавлено через 1 минуту
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Совершенно надуманная проблема.
Да, речь идет не о проблеме, а об эвристике.

Добавлено через 9 часов 58 минут
Хотелось бы немного разъяснить, почему я привязался к этим эвристикам.
На мой взгляд, эвристика является философским основанием теории машинного обучения. Почему зачастую, не вникая в природу числовых и нечисловых данных, удается почти с первого раза подобрать некоторый удачный алгоритм и потом его подстроить? Ответ - эвристика. После прослушивания лекций Воронцова К.В. "Машинное обучение" у меня сложилось впечатление, что специалисты внутренне предпочитают либо какой-либо теоретически обоснованный алгоритм типа оптимального байесовского классификатора, либо утвержденную экспертом точную модель, либо непараметрический алгоритм. Любые сугубо эвристические алгоритмы - это, якобы, нехорошо, неправильно.
Но ведь именно эвристики в алгоритме - это та самая находка, которую требуется сделать, чтобы определить закономерности в данных. Трудно представить данные, в которых не работает какая-либо известная эвристика. Между тем, если данные подготовить искусственно, то наверняка можно добиться отсутствия каких-либо легко обнаружимых закономерностей. И тут встает вопрос, а как эти эвристики работают-то? Как они открываются?
0
buddismdotru
22 / 3 / 0
Регистрация: 24.05.2016
Сообщений: 61
04.08.2016, 16:52 13
Mikhaylo, День добрый.
Тема которую вы подняли, очень важна. Необходимо приложить все усилия чтобы эвристические алгоритмы были доступны в открытом коде. Мы пока протестировали два алгоритма - генетический и ассоциативный.
конечно для оформления их в бибиотеку необходимо еще много работы - стандартизация подачи данных и документация.
Возможно всем вместе удастся найти еще примеры открытого кода эвристических алгоритмов и свести их в бибиотеку?
Материалы по реализации генетического алгоритма https://www.youtube.com/watch?v=qv6UVOQ0F44
По ассоциативному алгориту
Э. Кнут "Искусство программирования" 2005г. 2е издание Т3 стр 611
В версии pdf, распространенной в сети, тоже 2005г 2е издание Т3 стр 350
Malcolm C. Harrison [CACM 14 (1971) 777-779]

Это то что пишет Э. Кнут
Малькольм Ч. Харрисон [CACM, 14 (1971), 777–779] заметил, что кодирование наложением можно использовать для ускорения поиска текста.
Предположим, что нам нужно определить все вхождения некоторой цепочки символов (словарной фразы) в большой текст,
без построения громоздкого дерева Патриции.
Предположим, кроме того, что текст поделен на строки c1 c2 . . . c50 по 50 символов в каждой.
Харрисон предлагает кодировать каждую из 49 пар символов c1 c2, c2 c3, . . . , c49 c50 путем отображения ее в число от 0 до, скажем, 127.
Затем подсчитать ”ключ” строки c1 c2 . . . c50 — цепочку из 128 битов b0 b1 . . . b127, где bi=1 тогда и только тогда,
когда h(cj,cj+1)=i при некотором j (т.е. заполнить единицами битовый массив размером [128,0]). Выборка пар символов происходит внахлест,
а не встык.
Если нам нужно найти все вхождения слова ИГОЛКА (словарной фразы) в большой текстовой файл СТОГСЕНА, мы просто отыскиваем все строки,
ключи (массив) которых содержат 1 в позициях h(ИГ), h(ГО), h(ОЛ), h(ЛК), h(KA). При случайной хеш-функции вероятность того,
что некоторая случайная строка содержит в ключе (массиве) все эти единицы, равна всего лишь 0.00341 (ср. с упр. 4);
следовательно, пересечение пяти инвертированных списков цепочек битов позволит быстро найти все строки, содержащие слово ИГОЛКА
(хотя, вероятно, будет и несколько ложных выпадений).

Добавлено через 15 минут
Эвристика гладкости: если связанные параметры изменились незначительно, значит и неизвестный параметр изменится незначительно.
Так же написана. По сути это метод ловли льва вв пустыне - делим пустыню пополам и смотрим в какой половине лев.

Добавлено через 10 минут
по сути задачу можно свести к задаче оптимальности Белла, ее также называют функцией Беллмана
http://www.buddism.ru///___SANGHA___...9_lecture6.pdf
Эта задача хорошо решается при условии что известны все данные. При недостатке или переизбытке данных необходимо применение эвристических алгоритмов.
Метод максимального правдоподобия это наверное наивный Бейсовский клаччификатор?
В реальных задачах (равновесие, ориентирование, подбор ассоциаций)
необходимо решить задачу динамической классификации. Теоретическое решение этой задачи известно и предлагается решать ее методом интеллектуальных агентов. На практике такое решение практически не поддается строгому математическому анализу и поэтому практически не обсуждается.
Как основу для такой системы можно рассмотреть язык Эрланг. Эрганг использубт в телекоммуникации для организации распределенных систем. На рланге можно реализовать ассинзронное выполнение тысяч распределенных процессов с разделенным доступом к памяти, дазе данных и доступных для связи с пользователем.
https://habrahabr.ru/post/50028/
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
04.08.2016, 20:25  [ТС] 14
Цитата Сообщение от buddismdotru Посмотреть сообщение
Эвристика гладкости: если связанные параметры изменились незначительно, значит и неизвестный параметр изменится незначительно.
Так же написана. По сути это метод ловли льва вв пустыне - делим пустыню пополам и смотрим в какой половине лев.
Вы считаете, что это слабая/неэффективная эвристика? Ну Вы когда возвращаетесь на работу после небольшого периода отсутствия (например, после отпуска), ожидаете ли, что обстановка в офисе изменится кардинально?
0
buddismdotru
22 / 3 / 0
Регистрация: 24.05.2016
Сообщений: 61
04.08.2016, 21:20 15
Mikhaylo, день добрый.
Лев в пустыне это замечательный алгоритм. Мы его используем для поиска максимума срабатывания битовой маски признака буквы. Он в 32 раза сокращает количество проверок.
Необходимость в динамической классификации возникает тогда, когда распознаваемая функция не гладкая.
В вашем примере это соответствует ситуации когда за время вашего отпуска компания переехала в новое здание.

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

Метод интеллектуальных агентов это также эвристический метод. Его мало упоминают потому что он является по сути стратегией и нейросети или другие вычислительные алгоритмы используются в нем как детекторы при работе каждого агента.
Это требует параллельного асинхронного вычисления тысяч, а лучше миллионов агентов. Очевидно что доступное железо для этого появилось только недавно - CUDA, системы кластерных вычислений на процессорах ARM
В России этой проблемой занимается профессор Богданов
http://www.apmath.spbu.ru/ru/staff/bogdanov/index.html
0
osvald
-28 / 5 / 0
Регистрация: 26.02.2015
Сообщений: 253
09.08.2016, 15:49 16
Под эвристиками вы похоже понимаете набор аксиом, но так как он у вас переменный то нужно нечто неизменное - метаэвристика, по которой вы будете определять какие эвристики работают. Иначе они ничем не отличаются друг от друга.
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
09.08.2016, 16:13  [ТС] 17
Выдвижение гипотезы и проверка - вот и вся метаэвристика. Порядок выдвижения эвристик-гипотез определяется типом входных объектов и т.д. и т.п. Я не считаю, что это сложно.
0
echs
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
09.08.2016, 17:35 18
Mikhaylo
Вы не могли бы привести небольшой пример.
Лучше один раз увидеть, чем ....
0
Mikhaylo
205 / 192 / 24
Регистрация: 20.09.2014
Сообщений: 1,384
23.10.2016, 10:13  [ТС] 19
А вот, наконец-то, нашел ответ на собственный вопрос!
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Цель этой темы - выяснить, где в литературе можно почитать о научных достижениях по этой проблематике.
В статье
Как сейчас используют нейросети: от научных проектов до развлекательных сервисов
говорится:
Вселенная только кажется необъятной
Математических функций на порядок больше, чем возможных сетей для их аппроксимации. Но глубокие нейронные сети каким-то образом находят правильный ответ. Генри Лин (Henry Lin) из Гарварда и Макс Тегмарк (Max Tegmark) из Массачусетского технологического института пытаются понять, почему так происходит.
Учёные пришли к выводу, что Вселенная управляется только небольшой частью всех возможных функций: законы физики можно описать функциями с простым набором свойств. Вот почему глубоким нейронным сетям не нужно аппроксимировать все возможные математические функций, а только небольшую их часть.
«По непонятным до конца причинам, наша Вселенная может быть точно описана полиномиальными гамильтонианами низкого порядка», — говорят Лин и Тегмарк. Обычно многочлены, описывающие законы физики, имеют степени от 2 до 4. Поэтому Лин и Тегмарк считают, что глубинное обучение уникальным образом подходит для построения «физических» моделей.
У законов физики есть несколько важных свойств — они обычно симметричны по отношению к вращению и перемещению. Эти свойства также упрощают работу нейронных сетей – например, аппроксимацию процесса распознавания объекта. Нейронным сетям не нужно аппроксимировать бесконечное число возможных математических функций, а только небольшое количество самых простых.
Ещё одно свойство Вселенной, которое могут использовать нейронные сети — это иерархия её структуры. Искусственные нейронные сети часто создаются по подобию биологических, поэтому идеи учёных объясняют не только успешную работу глубинного обучения машин, но способность человеческого мозга понимать Вселенную. Эволюция привела к появлению структуры мозга человека, которая идеально подходит для разбора сложной Вселенной на понятные составляющие.
Работа учёных из Гарварда и МТИ должна помочь существенно ускорить процесс развития искусственного интеллекта. Математики могут улучшать аналитическое понимание работы нейронных сетей, физики и биологи – разбираться в том, как взаимосвязаны явления природы, нейронные сети и наш мозг, что приведёт к переходу на новый уровень работы с ИИ.
0
23.10.2016, 10:13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru