Dendral был проектом в области искусственного интеллекта (ИИ) 1960-х годов и экспертной системой компьютерного программного обеспечения , которую он создал. Его основной целью было изучение формирования гипотез и открытий в науке. Для этого была выбрана конкретная задача в науке: помочь химикам-органикам идентифицировать неизвестные органические молекулы, анализируя их масс-спектры и используя знания химии. [1] Это было сделано в Стэнфордском университете Эдвардом Фейгенбаумом , Брюсом Г. Бьюкененом, [2] Джошуа Ледербергом и Карлом Джерасси вместе с командой очень креативных научных сотрудников и студентов. [3] Это началось в 1965 году и охватывает примерно половину истории исследований ИИ. [4]
Программное обеспечение Dendral считается первой экспертной системой, поскольку оно автоматизировало процесс принятия решений и поведение химиков-органиков при решении проблем. [1] Проект состоял из исследований двух основных программ Heuristic Dendral и Meta-Dendral , [4] и нескольких подпрограмм. Он был написан на языке программирования Lisp , который считался языком ИИ из-за своей гибкости. [1]
Многие системы были получены из Dendral, включая MYCIN , MOLGEN, PROSPECTOR, XCON и STEAMER. Сегодня существует множество других программ для решения обратной задачи масс-спектрометрии, см. Список программного обеспечения для масс-спектрометрии , но их больше не называют «искусственным интеллектом», а просто ищут структуры.
Название Dendral является аббревиатурой термина «Dendritic Algorithm» (дендритный алгоритм). [4]
Эвристический Dendral — это программа, которая использует масс-спектры или другие экспериментальные данные вместе с базой знаний по химии для создания набора возможных химических структур, которые могут быть ответственны за создание данных. [4] Масс-спектр соединения создается масс-спектрометром и используется для определения его молекулярной массы, суммы масс его атомных составляющих. Например, соединение вода (H 2 O) имеет молекулярную массу 18, поскольку водород имеет массу 1,01, а кислород 16,00, и его масс-спектр имеет пик при 18 единицах. Эвристический Dendral будет использовать эту входную массу и знание атомных массовых чисел и правил валентности для определения возможных комбинаций атомных составляющих, масса которых составит 18. [1] По мере увеличения веса и усложнения молекул число возможных соединений резко возрастает. Таким образом, необходима программа, которая способна сократить это число возможных решений посредством процесса формирования гипотез.
Новые графовые теоретико-алгоритмы были изобретены Ледербергом, Гарольдом Брауном и другими, которые генерируют все графы с указанным набором узлов и типов соединений (химические атомы и связи) — с циклами или без них. Более того, команда смогла математически доказать, что генератор является полным, в том смысле, что он производит все графы с указанными узлами и ребрами, и что он не является избыточным, в том смысле, что вывод не содержит эквивалентных графов (например, зеркальных изображений). Программа CONGEN, как она стала известна, была разработана в основном вычислительными химиками Рэем Кархартом, Джимом Нурсом и Деннисом Смитом. Она была полезна химикам как автономная программа для генерации химических графов, показывающих полный список структур, которые удовлетворяют ограничениям, указанным пользователем.
Meta-Dendral — это система машинного обучения, которая получает набор возможных химических структур и соответствующих масс-спектров в качестве входных данных и предлагает набор правил масс-спектрометрии, которые коррелируют структурные особенности с процессами, которые производят масс-спектр. [4] Эти правила будут возвращены в Heuristic Dendral (в программах планирования и тестирования, описанных ниже) для проверки их применимости. [1] Таким образом, «Heuristic Dendral — это система производительности, а Meta-Dendral — это обучающаяся система». [4] Программа основана на двух важных функциях: парадигме «планировать-генерировать-тестировать» и инженерии знаний. [4]
Парадигма « план-генерация-тест» является базовой организацией метода решения проблем и является общей парадигмой, используемой как эвристическими системами Dendral , так и системами Meta-Dendral . [4] Генератор (позже названный CONGEN) генерирует потенциальные решения для конкретной проблемы, которые затем выражаются в виде химических графов в Dendral. [4] Однако это осуществимо только тогда, когда количество возможных решений минимально. Когда существует большое количество возможных решений, Dendral должен найти способ наложить ограничения, которые исключают большие наборы возможных решений. [4] Это основная цель планировщика Dendral , который является программой «формирования гипотез», которая использует «специфические для задачи знания для поиска ограничений для генератора». [4] И последнее, но не менее важное: тестер анализирует каждое предложенное возможное решение и отбрасывает те, которые не соответствуют определенным критериям. [4] Этот механизм парадигмы «план-генерация-тест» удерживает Dendral вместе. [4]
Основная цель инженерии знаний — достичь продуктивного взаимодействия между доступной базой знаний и методами решения проблем. [4] Это возможно посредством разработки процедуры, в которой большие объемы информации, специфичной для задачи, кодируются в эвристические программы. [4] Таким образом, первым существенным компонентом инженерии знаний является большая «база знаний». Dendral обладает конкретными знаниями о методе масс-спектрометрии, большим объемом информации, которая составляет основу химии и теории графов, и информацией, которая может быть полезна при поиске решения конкретной проблемы выяснения химической структуры. [4] Эта «база знаний» используется как для поиска возможных химических структур, которые соответствуют входным данным, так и для изучения новых «общих правил», которые помогают сократить поиски. Преимущество, которое Dendral предоставляет конечному пользователю, даже не являющемуся экспертом, — это минимизированный набор возможных решений для ручной проверки.
Эвристика — это эмпирическое правило, алгоритм, который не гарантирует решения, но уменьшает количество возможных решений, отбрасывая маловероятные и нерелевантные решения. [1] Использование эвристики для решения проблем называется «эвристическим программированием» и использовалось в Dendral, чтобы позволить ему воспроизвести в машинах процесс, посредством которого эксперты-люди находят решение проблем с помощью эмпирических правил и конкретной информации.
Эвристическое программирование было основным подходом и гигантским шагом вперед в области искусственного интеллекта, [4] поскольку оно позволило ученым наконец автоматизировать некоторые черты человеческого интеллекта. Оно стало заметным среди ученых в конце 1940-х годов благодаря книге Джорджа Полиа « Как это решить: новый аспект математического метода » . [1] Как сказал Герберт А. Саймон в «Науках об искусственном », «если вы принимаете эвристический вывод как несомненный, вы можете быть обмануты и разочарованы; но если вы полностью пренебрегаете эвристическими выводами, вы вообще не достигнете никакого прогресса».
В середине 20-го века вопрос «могут ли машины мыслить?» стал интригующим и популярным среди ученых, в первую очередь для того, чтобы добавить гуманистические характеристики поведению машин. Джон Маккарти , который был одним из главных исследователей в этой области, назвал эту концепцию машинного интеллекта « искусственным интеллектом » (ИИ) летом 1956 года в Дартмуте. ИИ обычно определяется как способность машины выполнять операции, которые аналогичны когнитивным способностям человека. [5] В 20-м веке было проведено много исследований по созданию ИИ.
Также примерно в середине 20-го века наука, особенно биология, столкнулась с быстро растущей потребностью в разработке «симбиоза человека и компьютера», чтобы помочь ученым в решении проблем. [6] Например, структурный анализ миоглобина, гемоглобина и других белков постоянно нуждался в разработке инструментов из-за своей сложности.
В начале 1960-х годов Джошуа Ледерберг начал работать с компьютерами и быстро заинтересовался созданием интерактивных компьютеров, которые помогли бы ему в его исследованиях экзобиологии . [1] В частности, он был заинтересован в разработке вычислительных систем, которые помогли бы ему изучать инопланетные органические соединения. [1] Поскольку он не был экспертом ни в химии, ни в компьютерном программировании, он сотрудничал с химиком из Стэнфорда Карлом Джерасси, чтобы тот помог ему с химией, и с Эдвардом Фейгенбаумом с программированием, чтобы автоматизировать процесс определения химических структур из необработанных данных масс-спектрометрии. [1] Фейгенбаум был экспертом в языках программирования и эвристике и помог Ледербергу разработать систему, которая воспроизводила способ, которым Джерасси решал проблемы выяснения структуры. [1] Они разработали систему под названием Дендритный алгоритм (Dendral), которая была способна генерировать возможные химические структуры, соответствующие данным масс-спектрометрии в качестве выходных данных. [1]
Дендрал тогда все еще был очень неточен в оценке спектров кетонов , спиртов и изомеров химических соединений. [1] Таким образом, Джерасси «обучил» Дендрала общим правилам, которые могли помочь устранить большинство «химически неправдоподобных» структур и создать набор структур, которые теперь мог проанализировать «неэкспертный» пользователь, чтобы определить правильную структуру. [1]
Команда Dendral наняла Брюса Бьюкенена для расширения программы Lisp, изначально написанной Джорджией Сазерленд. [1] У Бьюкенена были схожие идеи с идеями Фейгенбаума и Ледерберга, но его особыми интересами были научные открытия и формирование гипотез. [1] Как сказал Джозеф Новембер в книге «Оцифровка жизни: введение компьютеров в биологию и медицину », «(Бьюкенен) хотел, чтобы система (Dendral) совершала открытия сама по себе, а не просто помогала людям их совершать». Бьюкенен, Ледерберг и Фейгенбаум разработали «Meta-Dendral», которая была «генератором гипотез». [1] Эвристический Dendral «служил шаблоном для подобных систем, основанных на знаниях, в других областях», а не просто концентрировался на области органической химии. Meta-Dendral был моделью для систем обучения, богатых знаниями, которая позже была кодифицирована во влиятельной Модели обучения пространства версий Тома Митчелла . [1]