Дендрал

Дендрал — это проект в области искусственного интеллекта (ИИ) 1960-х годов и компьютерного программного обеспечения экспертная система созданная им . Его основной целью было изучение формирования гипотез и открытий в науке. Для этого была выбрана конкретная научная задача: помочь химикам-органикам идентифицировать неизвестные органические молекулы, анализируя их масс-спектры и используя знания по химии. ^[1] Это было сделано в Стэнфордском университете Эдвардом Фейгенбаумом , Брюсом Бьюкененом , ^[2] Джошуа Ледерберг и Карл Джерасси , а также команда очень творческих научных сотрудников и студентов. ^[3] Оно началось в 1965 году и охватывает примерно половину истории исследований ИИ. ^[4]

Программное обеспечение Dendral считается первой экспертной системой, поскольку она автоматизировала процесс принятия решений и поведение химиков-органиков при решении проблем. ^[1] Проект состоял из исследований по двум основным программам Heuristic Dendral и Meta-Dendral . ^[4] и несколько подпрограмм. Он был написан на Lisp языке программирования , который из-за своей гибкости считался языком ИИ. ^[1]

Многие системы были производными от Dendral, включая MYCIN , MOLGEN, PROSPECTOR, XCON и STEAMER. Сегодня существует множество других программ для решения обратной задачи масс-спектрометрии, см. Список программного обеспечения для масс-спектрометрии , но их больше не называют «искусственным интеллектом», а называют структурными искателями.

Название Dendral является аббревиатурой термина «Дендритный алгоритм». ^[4]

Эвристический Дендрал

Heuristic Dendral — это программа, которая использует масс-спектры или другие экспериментальные данные вместе с базой знаний по химии для создания набора возможных химических структур, которые могут отвечать за получение данных. ^[4] Масс-спектр соединения создается с помощью масс-спектрометра и используется для определения его молекулярной массы, суммы масс его атомных составляющих. Например, соединение воды (H ₂ O) имеет молекулярную массу 18, поскольку водород имеет массу 1,01, а кислород 16,00, а его масс-спектр имеет пик при 18 единицах. Эвристический Дендрал будет использовать эту входную массу, а также знание атомных массовых чисел и правил валентности, чтобы определить возможные комбинации атомных составляющих, масса которых в сумме будет равна 18. ^[1] По мере увеличения веса и усложнения молекул количество возможных соединений резко увеличивается. Таким образом, необходима программа, которая способна сократить это количество возможных решений в процессе формирования гипотез.

Ледерберг, Гарольд Браун и другие изобрели новые теоретико-графовые алгоритмы, которые генерируют все графы с заданным набором узлов и типами связей (химические атомы и связи) — с циклами или без них. Более того, команде удалось математически доказать, что генератор полон, поскольку он создает все графы с указанными узлами и ребрами, и что он неизбыточен, поскольку выходные данные не содержат эквивалентных графов (например, зеркальных изображений). . Программа CONGEN, как она стала известна, была разработана в основном химиками-вычислителями Рэем Кархартом, Джимом Норсом и Деннисом Смитом. Это было полезно химикам как отдельная программа для создания химических графиков, показывающих полный список структур, удовлетворяющих ограничениям, указанным пользователем.

Мета-Дендрал

Meta-Dendral — это система машинного обучения, которая получает на вход набор возможных химических структур и соответствующих масс-спектров и предлагает набор правил масс-спектрометрии, которые соотносят структурные особенности с процессами, создающими масс-спектр. ^[4] Эти правила будут переданы обратно в Heuristic Dendral (в программах планирования и тестирования, описанных ниже), чтобы проверить их применимость. ^[1] Таким образом, «Эвристика Дендрал — это система производительности, а Мета-Дендрал — это система обучения». ^[4] Программа основана на двух важных особенностях: парадигме «план-генерация-тест» и инженерии знаний. ^[4]

Парадигма «планируй-генерируй-тестируй»

Парадигма «план-генерация-тест» представляет собой базовую организацию метода решения проблем и является общей парадигмой, используемой как в эвристических системах Dendral , так и в системах Meta-Dendral . ^[4] Генератор . (позже названный CONGEN) генерирует потенциальные решения конкретной проблемы, которые затем выражаются в виде химических графиков в Dendral ^[4] Однако это возможно только тогда, когда число возможных решений минимально. Когда существует большое количество возможных решений, Дендралу приходится найти способ установить ограничения, исключающие большие наборы возможных решений. ^[4] Это основная цель планировщика Dendral , который представляет собой программу «формирования гипотез», которая использует «знания, специфичные для конкретной задачи, для поиска ограничений для генератора». ^[4] И последнее, но не менее важное: тестер анализирует каждое предлагаемое решение-кандидат и отбрасывает те, которые не соответствуют определенным критериям. ^[4] Этот механизм парадигмы «план-генерация-тест» — это то, что объединяет Dendral. ^[4]

Инженерия знаний

Основная цель инженерии знаний — добиться продуктивного взаимодействия между доступной базой знаний и методами решения проблем. ^[4] Это возможно за счет разработки процедуры, в которой большие объемы информации, специфичной для задачи, кодируются в эвристические программы. ^[4] Таким образом, первым важным компонентом инженерии знаний является большая «база знаний». Дендрал обладает специфическими знаниями о методе масс-спектрометрии, большим объемом информации, которая составляет основу химии и теории графов, а также информацией, которая может быть полезна при поиске решения конкретной проблемы выяснения химической структуры. ^[4] Эта «база знаний» используется как для поиска возможных химических структур, соответствующих входным данным, так и для изучения новых «общих правил», которые помогают сократить поиск. Преимущество Dendral, которое предоставляет конечному пользователю, даже неспециалисту, заключается в минимизированном наборе возможных решений для проверки вручную.

Эвристика

Эвристика — это эмпирическое правило, алгоритм, который не гарантирует решения, но уменьшает количество возможных решений, отбрасывая маловероятные и нерелевантные решения. ^[1] Использование эвристики для решения проблем называется «эвристическим программированием» и использовалось в Дендрале, чтобы позволить ему воспроизвести в машинах процесс, посредством которого люди-эксперты стимулируют решение проблем с помощью практических правил и конкретной информации.

Эвристическое программирование стало важным подходом и гигантским шагом вперед в области искусственного интеллекта. ^[4] поскольку это позволило ученым наконец автоматизировать некоторые черты человеческого интеллекта. Она стала известна среди учёных в конце 1940-х годов благодаря Джорджа Пойа книге «Как её решить: новый аспект математического метода» . ^[1] Как Герберт А. Саймон сказал в «Науках об искусственном» , «если вы примете эвристический вывод как достоверный, вы можете быть обмануты и разочарованы; но если вы вообще пренебрегаете эвристическими выводами, вы вообще не добьетесь никакого прогресса».

История

В середине 20 века вопрос «могут ли машины думать?» стала интригующей и популярной среди учёных, прежде всего потому, что придала поведению машин гуманистические характеристики. Джон Маккарти , который был одним из ведущих исследователей в этой области, назвал эту концепцию машинного интеллекта « искусственным интеллектом » (ИИ) во время лета в Дартмуте в 1956 году. ИИ обычно определяется как способность машины выполнять операции, которые аналог когнитивных способностей человека. ^[5] Много исследований по созданию ИИ было проведено в 20 веке.

Также примерно в середине 20-го века наука, особенно биология, столкнулась с быстро растущей потребностью в разработке «симбиоза человека и компьютера», чтобы помочь ученым в решении проблем. ^[6] Например, структурный анализ миогоблина , гемоглобина и других белков постоянно нуждался в разработке инструментов из-за своей сложности.

В начале 1960-х годов Джошуа Ледерберг начал работать с компьютерами и быстро заинтересовался созданием интерактивных компьютеров, которые могли бы помочь ему в экзобиологических исследованиях. ^[1] В частности, он был заинтересован в разработке компьютерных систем, которые помогут ему изучать инопланетные органические соединения. ^[1] Поскольку он не был экспертом ни в химии, ни в компьютерном программировании, он сотрудничал со Стэнфордским химиком Карлом Джерасси, чтобы помочь ему с химией, и Эдвардом Фейгенбаумом с программированием, чтобы автоматизировать процесс определения химических структур на основе необработанных данных масс-спектрометрии. ^[1] Фейгенбаум был экспертом в языках программирования и эвристике и помог Ледербергу разработать систему, повторяющую метод, которым Джерасси решал задачи объяснения структур. ^[1] Они разработали систему под названием Дендритный алгоритм (Дендрал), которая была способна генерировать на выходе возможные химические структуры, соответствующие данным масс-спектрометрии. ^[1]

Дендрал тогда еще был очень неточен в оценке спектров кетонов , спиртов и изомеров химических соединений. ^[1] Таким образом, Джерасси «обучил» Дендрала общим правилам, которые могли помочь устранить большинство «химически неправдоподобных» структур и создать набор структур, которые теперь мог бы проанализировать «неопытный» пользователь для определения правильной структуры. ^[1]

Команда Dendral наняла Брюса Бьюкенена для расширения программы Lisp, первоначально написанной Джорджией Сазерленд. ^[1] У Бьюкенена были схожие идеи с Фейгенбаумом и Ледербергом, но его особыми интересами были научные открытия и формирование гипотез. ^[1] Как сказал Джозеф Ноябрь в книге «Оцифровка жизни: введение компьютеров в биологию и медицину» , «(Бьюкенен) хотел, чтобы система (Дендрал) делала открытия самостоятельно, а не просто помогала людям делать их». Бьюкенен, Ледерберг и Фейгенбаум разработали «Мета-Дендрал», который был «создателем гипотез». ^[1] Эвристический Дендрал «послужит образцом для аналогичных систем, основанных на знаниях, в других областях», а не просто сосредоточится на области органической химии. Мета-Дендрал был моделью систем обучения, богатых знаниями, которая позже была систематизирована во влиятельной модели обучения Тома Митчелла. ^[1]

Примечания

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ноябрь 2006 г.
^ Устное историческое интервью с Брюсом Г. Бьюкененом , Институт Чарльза Бэббиджа , Университет Миннесоты.
^ Ледерберг, 1987.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Линдси и др., 1980 г.
^ Берк, 1985
^ Ледерберг, 1963 г.

Ссылки

Берк, А. А. LISP: язык искусственного интеллекта. Нью-Йорк: Компания Ван Ностранд Рейнхольд, 1985. 1–25.
Ледерберг, Джошуа. Инструментальный кризис в биологии . Медицинская школа Стэнфордского университета. Пало-Альто, 1963 год.
Ледерберг, Джошуа. Как Дендрал был зачат и рожден . Симпозиум ACM по истории медицинской информатики, 5 ноября 1987 г., Рокфеллеровский университет. Нью-Йорк: Национальная медицинская библиотека, 1987.
Линдси, Роберт К., Брюс Г. Бьюкенен, Эдвард А. Фейгенбаум и Джошуа Ледерберг. Применение искусственного интеллекта в органической химии: проект Dendral . Книжная компания МакГроу-Хилл, 1980.
Линдси, Роберт К., Брюс Г. Бьюкенен, Э.А. Фейгенбаум и Джошуа Ледерберг. ДЕНДРАЛ: пример первой экспертной системы для формирования научных гипотез . Искусственный интеллект 61, 2 (1993): 209-261.
Ноябрь, Джозеф А. «Оцифровка жизни: введение компьютеров в биологию и медицину». Докторская диссертация, Принстонский университет, 2006 г.

[November,_2006-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ноябрь 2006 г.

[2] Устное историческое интервью с Брюсом Г. Бьюкененом , Институт Чарльза Бэббиджа , Университет Миннесоты.

[3] Ледерберг, 1987.

[Lindsay_et_al.,_1980-4] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Линдси и др., 1980 г.

[5] Берк, 1985

[6] Ледерберг, 1963 г.

[1]

[2]

[3]

[4]

[5]

[6]