• ↓
  • ↑
  • ⇑
 
Записи с темой: искусственный интеллект (список заголовков)
19:14 

Наконец-то! P?=NP и институт Клэя

Amicus Plato
Простыми словами
В конце прошлой записи мы вплотную подошли к проблеме равенства классов сложности P и NP. Сформулировать ее можно следующим образом:

Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)?

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

16:20 

Еще одна запись об NP-полноте (не обещаю, что последняя)

Amicus Plato
Простыми словами
Тема алгоритмической сложности, даже если пробегать по самым ее верхам (как я и планировала), оказывается такой же неисчерпаемой, как и атом.
Попытаюсь всё-таки продвинуться к логическому завершению.
Почему же столь важны оказались именно булевы формулы?
Напомню, булева формула называется выполнимой, если существует такой набор значений входящих в нее переменных, для которого она принимает значение ИСТИНА.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

16:48 

NP-полнота, NP-полные задачи и булевы формулы

Amicus Plato
Простыми словами
Что же такое NP-полные задачи?
О задачах из класса NP мы уже поговорили, но оказывается, среди них есть особенные. И таких особенных тоже не так уж мало.
NP-полные задачи — это класс задач, лежащих в классе NP, к которым сводятся все задачи класса NP за полиномиальное время. То есть, если найдется быстрый алгоритм (полиномиальный) для решения любой из NP-полных задач, то и любая задача из класса NP тоже может быть решена быстро!

Вот сейчас я прочитала в одном месте удивительную мысль. Не могу не процитировать:
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.
(с)
"В принципе", всё так и есть. Но проблема P=(?)NP так и висит в воздухе. И доказать неравенство тоже ведь никто не может, не только равенство.

О проблеме равенства классов P и NP, надеюсь, я напишу в следующей записи (и тем самым завершу этот цикл), а сейчас перечислю NP-полные задачи (не все, конечно) — для иллюстрации того, что их ведь достаточно много! А стоит решить "быстро" одну, и к ее решению можно будет свести все остальные! Вот где простор для деятельности!

Первое, и основное, что надо знать: к NP-полным задачам принадлежит задача о выполнимости булевых формул.
Я и в прошлый раз, перечисляя задачи класса NP, начинала список именно ею, и в этот раз опять. Сейчас расскажу, почему.
В прошлый раз я описывала эту задачу очень и очень коротко. Потому что всё-таки не представляю, как объяснить, что такое булевы формулы и их выполнимость, на пальцах.
Но делать нечего: похоже, без этого не обойтись.

Небольшой экскурс в теорию и историю
История
Что же такое булева формула?
Булева формула — это формула логики высказываний. Логика высказываний — самая простая из всех логик. Говорят еще, что это классическая логика нулевого порядка.
Про нее я даже могу рассказать, не прибегая ни к каким ухищрениям.
Остановимся на основном определении. "Высказывание". Что это такое?
Под высказыванием понимают любое повествовательное предложение, о котором можно сказать, истинно оно или ложно.
Например (с этого я каждый раз начинаю первое занятие по матлогике) какие из перечисленных предложений являются высказываниями?

0. Который час?
1. 2*2=4
2. 2*2=5
3. Лондон — столица Парижа.
4. Включите свет.
5. 2*х=8
6. a*b = b*a для любых a и b

Ответ:

Продолжение теории

@темы: Поп-математика, Искусственный интеллект, Алгоритмы, Amicus Plato

16:13 

Класс NP

Amicus Plato
Простыми словами
Самые известные задачи, входящие в класс NP, следующие:

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

12:23 

Время работы алгоритмов

Amicus Plato
Простыми словами
Напишу про то, зачем же нам всё-таки нужно понижать алгоритмическую сложность. Казалось бы, машины быстрые, процессоров у них тоже может быть много. Неужели действительно так остро стоит проблема времени?

Давайте посмотрим.
читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

18:34 

Алгоритмическая сложность. Лирическое отступление.

Amicus Plato
Простыми словами
Хочу подробнее остановиться на том примере, который привела в прошлой записи.

Задача формулируется очень просто: определить, является заданное число простым или составным.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

23:49 

Продолжение рассказа про алгоритмическую сложность, классы P, NP и про NP-полноту III

Amicus Plato
Простыми словами
Недетерминированная Машина Тьюринга
Рассматривая детерминированную машину Тьюринга, мы коснулись и недетерминированной тоже.
Еще раз приведу определение:

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

С тем, что означает "существует не более одного правила", мы разобрались в прошлый раз. А что же значит "в противном случае"?

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

22:59 

Продолжение рассказа про алгоритмическую сложность, классы P, NP, и про NP-полноту II

Amicus Plato
Простыми словами
Продолжаю рассказ про алгоритмическую сложность.
С О-нотацией мы разобрались, осталось разобраться еще с некоторыми вещами.
Итак, про то, что такое класс Р, нам уже известно.
Напомню: классом P (polynomial) называется множество алгоритмов, время работы которых не превосходит многочлена от размера данных. То есть сложность таких алгоритмов в терминах О-больших будет О(NC), где N — размер входных данных.
Алгоритмы, принадлежащие классу P, считаются быстрыми. Оттого-то мы и испытываем к ним повышенный интерес.
К классу Р относятся алгоритмы сортировки, поиска в множестве, перемножения матриц, выяснения связности графов и некоторые другие.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

22:51 

Продолжение рассказа про алгоритмическую сложность, классы P и NP и про NP-полноту I

Amicus Plato
Простыми словами
Прежде чем пойти дальше, сделаю еще пару замечаний и расскажу про О-большие и о-малые.
О-нотация пришла в теорию алгоритмов из математического анализа. Кто знаком с рядами даже самым поверхностным, шапочным, знакомством, тот уж наверняка сталкивался и с О-большим, и с о-малым.
А те, кто не сталкивались, столкнутся прямо сейчас.
Если, конечно, щелкнут на кат

@темы: Поп-математика, Искусственный интеллект, Алгоритмы, Amicus Plato

23:48 

Рассказ про алгоритмическую сложность, классы P и NP, и про NP-полноту

Amicus Plato
Простыми словами
(Всё, что я здесь напишу, будет изложено неформально. Постараюсь избежать каких бы то ни было определений, и, тем более, сложных выводов... Хотя это будет совсем не просто)))

Что же такое сложность алгоритма? На самом деле, понять это интуитивно довольно легко.
Алгоритмическая сложность — это зависимость времени исполнения алгоритма от длины входных данных.
То есть, конечно же очевидно, что если нам нужно что-то найти во входных данных или что-то переставить местами, то чем больше количество информации на входе, тем больше времени понадобится, чтобы получить результат.
"Время" здесь величина довольно абстрактная. Естественно, она (эта величина) должна быть универсальной, и не зависеть от типа и производительности компьютера или иного устройства, а также от других частностей. Измеряется она числом элементарных шагов. Сейчас поясню, что это такое.

читать дальше

UPD: В комментариях важное дополнение сделал  Хранитель печати. Он привел основные классы сложности с их описанием.

@темы: Amicus Plato, Искусственный интеллект, Поп-математика, Алгоритмы

15:42 

Приобретение знаний

Amicus Plato
Простыми словами
Дорогие читатели и участники сообщества!
Я сейчас пишу статью, которая посвящена приобретению знаний.
"Приобретение знаний" имеется в виду "интеллектуальными системами", но пока ни о каких конкретных системах речи не идет. Пока тут разговор только о модели человеческой долговременной памяти.
Всё, что будет написано ниже, это не статья, и не черновик статьи, — это, скорее, мысли о том как работает человеческая память.
Я здесь совершеннейший не-специалист.
Поэтому очень прошу: любое ваше мнение для меня важно!
Допускаю с равной вероятностью, что то, что здесь написано:
а) общеизвестно и любой дурак кроме меня об этом знает;
б) полная туфта, и в принципе не содержит рационального зерна;
в) интересно но неверно;
г) верно, но из этого ничего нельзя вывести;
и т.д.
Одним словом, нижайшая просьба прочитать и написать пару слов: не только и не столько выбрать вариант из вышеперечисленных оценок, сколько высказать свое мнение! Просьба как к математикам, так и к психологам и философам, а также ко всем-всем-всем, потому что "проблема", собственно, "общечеловеческая".
Копирайт тут везде мой)))
Стиль ровно такой, какой можно выжать за два часа с чистого листа (то есть будет рихтоваться).
Спасибо!
Warning: текста много.

Приобретение знаний

@темы: Искусственный интеллект, Amicus Plato

15:48 

Китайская комната Серла III

Amicus Plato
Простыми словами
Ну, вот, похоже я дождалась пока все уже потеряют к алгоритмизации мышления всяческий интерес (((
Но всё равно допишу.
Серл предложил такой мысленный эксперимент, в котором роль "понимающего компьютера" поручил сам себе.
Итак, он поместил себя в комнату без окон - без дверей, — только с небольшими прорезями. Для чего они, — сейчас расскажу.
В эти прорези какие-то добрые люди — экспериментаторы, которые хотят от него добиться разумного поведения, — просовывают тексты на китайском языке, в котором Серл не понимает ничего. Т.е. ни единого иероглифа.
Никакой другой информации извне он не получает (ну, форменный компьютер :)).
А "тексты", которые ему подают, — не что иное, как истории, которые фигурировали в описании работы Шенка (про, предположим, клиента ресторана), и вопросы к этим историям, которые он якобы должен понять (И истории И вопросы), чтобы правильно ответить.
Ответы Серла: "да" или "нет" — тоже, естественно, на китайском, — он отдает тоже через эти прорези.
Серл не знает ни слова по-китайски. Но зато у него есть ряд четких инструкций на английском языке, в которых записано, ЧТО он должен сделать, получив из прорези некую последовательность символов. Ему важно только правильно сличить.
В итоге, не понимая ни слова по-китайски, он справляется с этой работой не хуже чем любой китаец, способный понять без труда все эти истории и вопросы к ним.
Таким образом, довод Серла состоит в том, что простое выполнение подходящего алгоритма ничего не говорит о понимании.
Он просовывает раз за разом правильные ответы в щели, не понимая ни текстов, ни вопросов к ним.

А дальше я уже пишу от себя.
Мммм... Не знаю, с одной стороны Пенроуз ОЧЕНЬ УБЕДИТЕЛЬНО говорит, что Серл прав на все сто, и меня как натуру доверчивую так и тянет ему поверить... Но с другой стороны, не может же один такой мысленный эксперимент послужить таким мощным контрпримером, который бы так вот одним махом бы и снял все сомнения.
И сразу доказал: да, мышление не описывается алгоритмом!
Но ведь то, что мышление не описывается каким-то частным алгоритмом, вовсе не значит, что тут же можно поставить квантор всеобщности...
Программа Шенка, пардон, написана в 1977 году. Она не обладает интеллектом. Пока еще никакая программа не обладает.
...
То, что дальше у Пенроуза с "обобщенной квантовой редукцией" тоже меня настораживает...
Кажется мне, не там надо ковырять....

@темы: Amicus Plato, Искусственный интеллект

22:16 

Китайская комната Серла II

Amicus Plato
Простыми словами
Продолжаем разговор )))
Не прошло и года.

Значит, мы остановились на тесте Тьюринга.

(Всё это вольный пересказ пассажей книги Роджера Пенроуза "Новый ум короля").

Существует такая точка зрения в искусственном интеллекте, которая называется "сильный ИИ". Сторонники сильного ИИ утверждают, что всю мыслительную активность человека можно записать с помощью алгоритма. Понятно, что алгоритм этот ОЧЕНЬ, ЧРЕЗВЫЧАЙНО, сложен, но однако же, если это принципиально возможно, то значит рано или поздно станет осуществимо и технически.
Такой алгоритм, уж вне всяких сомнений пройдет тест Тьюринга.
И, более того, сторонники сильного ИИ уверены, что как только этот алгоритм будет запущен, он начнет сам по себе испытывать чувства, обладать сознанием, БЫТЬ РАЗУМОМ.

Но, — говорит Пенроуз, и с ним трудно не согласиться, — "разумные состояния и алгоритмы вряд ли можно считать идентичными в этом контексте".

Наиболее остро критиковал эту точку зрения американский философ Джон Серл.

В качестве примера он рассматривает компьютерную программу, разработанную Роджером Шенком. Задача этой программы состояла не просто в ведении осмысленного диалога, но в "понимании ситуаций".
То есть программе давали простые истории, после чего просили сделать небольшое резюме. Вот, к примеру: "Мужчина вошел в ресторан и заказал гамбургер. Когда гамбургер принесли, оказалось, что он сильно подгорел, и рассерженный мужчина выскочил из ресторана, не заплатив по счету и не оставив чаевых". В качестве другого примера следующая история: "Мужчина вошел в ресторан и заказал гамбургер. Когда гамбургер принесли, мужчина остался им очень доволен. И, покидая ресторан, он дал официанту щедрые чаевые перед тем, как заплатить по счету".
Чтобы проверить «понимание» этих историй компьютером, его попросили определить, съел ли мужчина гамбургер в каждом отдельном случае (факт, который не был упомянут в тексте явным образом). На этот простой вопрос компьютер может дать ответ, совершенно не отличающийся от того, что дал бы человек: «нет» в первом случае и «да» — во втором.
То есть в этом узком смысле машина уже прошла тест Тьюринга.

И вот вопрос: действительно ли подобный положительный результат указывает на истинное понимание, демонстрируемое компьютером, или заложенной в него программой?
Как аргумент в пользу отрицательного ответа Серл и предложил свою концепцию "китайской комнаты".
Скоро я уже до нее доберусь )))

@темы: Amicus Plato, Искусственный интеллект

15:41 

Китайская комната Серла I

Дилетант
На плечах гигантов, на спинах электронов
Всё это относится к вопросу "может (сможет) ли компьютер думать, и как это узнать" )))
Как отличить разумное действие от механического выполнения АЛГОРИТМА?
Именно в этом месте нынешняя тема имеет плотное пересечение с вопросом об алгоритмах.

Так вот (это я от себя) АЛГОРИТМ — ЭТО ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕЙСТВИЙ, КОТОРУЮ МОЖНО ВЫПОЛНЯТЬ АБСОЛЮТНО БЕЗДУМНО. Можно вообще не понимать, что ты делаешь, и для чего. Тем не менее, результат каждого выполнения алгоритма с одними и теми же начальными данными будет один и тот же.

Придется начать издалека. Многие знают про тест Тьюринга.
Тест предназначался для ответа на вопрос: можно ли резонно утверждать, что машина думает.
Тест заключается в том, что проницательного человека сажают в пустой комнате за экран монитора. (Утрирую слегка, но не смысл полностью оставляю в целости).
В соседних комнатах находятся — человек и машина. Точнее "думающий" и "?-думающий" (или "возможно-думающий") субъекты. Кто из них где — не известно. Это и надо выяснить опрашивающему.
Общаются они по сети.
Опрашивающий задает всевозможные вопросы, на которые человек отвечает по возможности максимально честно (пытаясь убедить что именно он живое существо). Но то же самое делает компьютер — он хитрит, пытаясь заставить думать тестирующего, что живое существо — это как раз ОН (компьютер).

Если в серии подобных тестов окажется, что опрашивающий не способен "вычислить", кто из двоих — компьютер, то считается, что компьютер (программа) прошел(ла) тест Тьюринга.

Вот как раз НА ЭТО Тьюрингу и возразил Серл.
Но об этом уже в следующий раз )))

@темы: Amicus Plato, Искусственный интеллект

23:01 

Amicus Plato
Простыми словами
Объявление для старожилов )))

Те, кто застал неоконченные мною публикации книги Дмитрия Александровича Поспелова:

МОДЕЛИРОВАНИЕ РАССУЖДЕНИЙ.
Опыт анализа мыслительных актов.


могут заказать ее у меня ))))
В формате пдф.
Весом (уже окончательным — со всеми почтовыми наворотами) 3 метра.
Упаковке не поддается.

Если кто не застал публикаций, он всё равно может заказать )))
Ибо исходящий трафик у меня бесплатный )))

@темы: Amicus Plato, Искусственный интеллект, Публикации, Техническая запись

22:49 

Кусочек тезисов на конференцию

Дилетант
На плечах гигантов, на спинах электронов
На самом-то деле, доклад — чистой воды профанация. Т.е. это небольшой обзор для неспециалистов. К сожалению, сплошная компиляция. Моего тут ровным счетом ничего.
Только во второй части, которую я не выложила )))


ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ

Термин «искусственный интеллект» имеет несколько интерпретаций.
1. Искусственный интеллект – способность прикладного процесса обнаруживать свойства, ассоциируемые с разумным поведением человека.
2. Искусственный интеллект – раздел информатики, занимающийся вопросами имитации мышления человека с помощью компьютера.
Такое различие в определениях вытекает из широкого разнообразия направлений научных исследований и разработок в рамках науки, имеющей название «искусственный интеллект».
Идея создания механической копии человека для решения сложных задач родилась еще во времена античности. Однако рождение искусственного интеллекта как науки произошло в середине ХХ века – после создания электронно-вычислительных машин, с помощью которых идея моделирования человеческих рассуждений смогла получить практическое воплощение. В это же время возникла и стала развиваться новая наука – кибернетика. Само название «искусственный интеллект» (Artificial Intelligence – AI) было введено в 1956 году на семинаре в Дартсмутском колледже (США).
После возникновения искусственного интеллекта как отдельной области науки произошло его разделение на два направления: нейрокибернетика и «кибернетика черного ящика».
Это разделение неразрывно связано с двумя метафорическими теориями мозга, строящимися на основании глубоких аналогий.
Первая из них: «человек – это животное» – основана на теории эволюции биологических видов. С точки зрения этой метафоры человек рассматривается в неразрывной связи с миром животных, а его строение и поведение можно объяснить на основе данных, накопленных сравнительной биологией и теорией эволюции. Исследования, опирающиеся на эту метафору, имеют своей конечной целью создание теории мозга. Именно в этом направлении ведутся исследования в нейрокибернетике.
Нейрокибернетика, таким образом, ориентирована на программно-аппаратное моделирование структур, подобных структуре мозга. Основные усилия в этой области направлены на создание систем элементов, подобных нейронам головного мозга, и моделирование связей между ними. Такие системы называются нейронными сетями.
Существует три основных подхода к созданию нейросетей:
1. Аппаратный;
2. Программный;
3. Гибридный.
Вторая метафора: «Человек – это машина» привела к созданию «кибернетики черного ящика». Она основана на использовании внешнего сходства в поведении человека и различных технических устройств; чаще всего это сходство – по результатам деятельности, а в качестве технического эталона для сравнения используется ЭВМ.
В фундамент этого подхода заложен принцип, противоположный биологическому, и, как следствие, нейрокибернетическому: не имеет значения, что внутри искусственного устройства; главное, чтобы на заданные воздействия оно реагировало так же, как человеческий мозг.
Это направление ориентировано на создание алгоритмов и программную реализацию решения интеллектуальных задач.
До недавнего времени эти два ответвления искусственного интеллекта развивались практически независимо друг от друга, и только в последнее время наметились тенденции к их объединению.

@темы: Искусственный интеллект, Amicus Plato

21:17 

Давненько я здесь не была в этой ипостаси...

Amicus Plato
Простыми словами
Приветствую новых участников и постоянных читателей!

И тут же философский вопрос.
Если мы что-то познаем, что-то совсем новое, то мы его "определяем", даем ему определение, о-пределение, о-пределивание.
Значит ли это, что и в самом деле мы ставим этому нечто пределы, за которые после нашего познания оно не сможет выйти? Значит ли это, что определяя мы ограничиваем вещи, явления, и в целом мир вокруг?

@темы: Amicus Plato, Вопросы, Искусственный интеллект, Органон

11:47 

Копирую из дневника Дилетанта

Дилетант
На плечах гигантов, на спинах электронов
Цитата из книги по системному анализу.

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

Никто не знает, где взять такие тесты?
Чтобы еще желательно и скачать можно было? А?
Интересно!

@темы: Amicus Plato, Вопросы, Искусственный интеллект

21:52 

Ничего нельзя пропускать...

Дилетант
На плечах гигантов, на спинах электронов
Вот с чего должно было начаться:


@темы: Amicus Plato, Искусственный интеллект, голография

21:48 

А вот иллюстрация к предыдущей записи:

Дилетант
На плечах гигантов, на спинах электронов

Поп-математика для взрослых детей

главная