Dendral

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

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

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

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

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

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

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

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

Эвристическое программирование стало важнейшим шагом в развитии искусственного интеллекта,^[4] поскольку позволило впервые автоматизировать отдельные черты человеческого разума. Научная популярность эвристик связана с книгой Джорджа Пойи «Как решать задачу. Новый аспект математического метода»^[1] (How to Solve It: A New Aspect of Mathematical Method, 1945). Герберт Саймон в книге «Науки об искусственном» отмечал: «Если считать эвристический вывод достоверным, можно ошибиться и быть разочарованным; но если полностью пренебречь эвристикой, не будет никакого прогресса».

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

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

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

Первая версия Dendral была неточной при анализе спектров кетонов, спиртов и изомеров.^[1] Поэтому Джерасси «обучал» систему общим правилам, позволяющим отсечь химически невозможные структуры и получить список кандидатов, который мог просмотреть даже неспециалист.^[1] Новые правила содержали больше сведений о масс-спектрометрии и органической химии. Джерасси также расширил систему для анализа данных ЯМР-спектроскопии вдобавок к масс-спектрам.^[7].

В команду Dendral вошёл Брюс Бьюкенен, который дополнил исходную программу на Lisp, начатую Джорджией Сазерленд^[1] У Бьюкенена были схожие идеи с Фейгенбаумом и Ледербергом, но основной его интерес лежал в области научных открытий и формирования гипотез.^[1]

Как отмечал Джозеф Новембер в «Digitizing Life: The Introduction of Computers to Biology and Medicine»:

«... хотел, чтобы система (Dendral) совершала открытия самостоятельно, а не только помогала людям их делать».

В результате Бьюкенен, Ледерберг и Фейгенбаум разработали Meta-Dendral, предназначенный для формулирования гипотез.^[1] Евристическая Dendral стала образцом для последующих экспертных систем и в других областях, а Meta-Dendral легла в основу моделей обучения с насыщением знаний, позднее формализованных в модели версионного пространства Тома Митчелла.^[1]

К 1970 году Dendral достигла уровня интерпретации структур на уровне постдокторанта. В течение следующего десятилетия группа Джерасси использовала программу в собственных исследованиях.^[7].

В последние годы влияние Dendral проявляется в современных AI-системах для автогенерации структур по спектральным данным. Проекты METIS и SpecTUS (2025) продолжают традицию Dendral, применяя машинное обучение для автоматической интерпретации данных ГХ–МС и построения новых моделей молекул.