Projekt Dendral

Po przeprowadzce Eda Feigenbauma z UC Berkeley do Stanford w 1965 r. zainteresował się "tworzeniem modeli procesów myślenia naukowców, zwłaszcza procesów indukcji empirycznej, na podstawie których z danych wywnioskowano hipotezy i teorie". Jak to ujął: "Potrzebowałem konkretnego środowiska zadań, w którym konkretnie przestudiowałbym te kwestie". Feigenbaum przypomina, że uczestniczył w warsztatach nauk behawioralnych w Stanford i wysłuchał przemówienia Joshua Lederberga, laureata Nagrody Nobla {genetyk i założyciel Departamentu Genetyki Stanford. Lederberg mówił o problemie rozpoznawania struktury związku chemicznego na podstawie wiedzy o jego składnikach atomowych i spektrogramie masowym. Brzmiało to jak problem, którego szukał Feigenbaum, i on i Lederberg wkrótce zgodzili się współpracować w tej sprawie. Cząsteczki chemiczne są opisane wzorami, które dają ich składniki atomowe. Na przykład wzór na propan to C₃H₈, co wskazuje, że składa się z trzech atomów węgla i ośmiu atomów wodoru. Ale o związku można dowiedzieć się więcej niż z jakich atomów jest on zbudowany. Atomy tworzące cząsteczkę są ułożone w geometryczną strukturę, a chemicy chcą wiedzieć, czym jest ta struktura. Na przykład trzy atomy węgla w propanie są połączone razem w łańcuch. Każdy z dwóch atomów węgla na końcach łańcucha ma trzy przyłączone do nich atomy wodoru, a pojedynczy atom węgla w środku łańcucha ma związane z nim dwa atomy wodoru. Chemicy odkryli, że rozpoznanie struktury prostych związków, takich jak propan, nie jest zbyt trudne. Jednak trudniejsze są związki bardziej złożone, takie jak 2-metyloheksan-3-on, keton o wzorze chemicznym C₇H₁₄₀. Jedną z metod stosowanych przez chemików do wnioskowania o strukturze związku jest bombardowanie go elektronami o wysokiej energii w spektrometrze mas. Wiązka elektronowa spektrometru mas rozbija związek fragmenty, a powstałe fragmenty są sortowane według ich masy za pomocą pola magnetycznego w spektrometrze. Przykładowy spektrogram masowy pokazano na rysunku



Fragmenty wytwarzane przez spektrometr mas zwykle składają się z wytrzymałych podbudów związku, a ich masy ujawniają wskazówki na temat głównej struktury. Doświadczony chemik wykorzystuje "zgromadzoną wiedzę" (by użyć wyrażenia Berlinera) na temat tego, w jaki sposób związki rozpadają się w spektrometrze mas, aby dobrze odgadnąć strukturę związku. Feigenbaum i Lederberg wraz ze swoim kolegą Brucem Buchananem, który dołączył do Stanford w 1966 r. Po uzyskaniu stopnia doktora. w Philosophy na University of Michigan, podjęto próbę budowy programów komputerowych, które mogłyby wykorzystywać dane ze spektrogramu masowego, wraz ze wzorem chemicznym związku, aby "wyjaśnić" (jak to ujęli) strukturę związku. Lederberg już wcześniej opracował komputerową procedurę o nazwie Dendral (akronim algorytmu Dendritic Algorytm), który mógłby wygenerować wszystkie możliwe topologicznie struktury acykliczne, biorąc pod uwagę wzór chemiczny i inne podstawowe informacje chemiczne o tym, jak atomy łączą się z innymi atomami (struktura acykliczna to taka, która nie zawiera żadnych pierścieni Przypomnij sobie na przykład, że benzen zawiera sześć atomów węgla ułożonych w sześciokąt, który chemicy nazywają pierścieniem. Każdy z atomów węgla ma dołączony atom wodoru). Algorytm Lederberga postępował stopniowo, generując częściowe struktury z głównego formuła, a następnie generowanie z nich bardziej przegubowych struktur cząstkowych itd. w podobny sposób. Końce lub liście drzewa zawierają ostateczne, w pełni przegubowe struktury możliwe topologicznie. Znalezienie faktycznej struktury związku (lub przynajmniej najbardziej prawdopodobnych rzeczywistych struktur) można porównać do przeszukania drzewa do odpowiedniej końcówki lub końcówek. Feigenbaum i koledzy zaproponowali wykorzystanie wiedzy, którą wykorzystali wykwalifikowani chemicy podczas interpretacji danych widm masowych. Chemicy wiedzieli, że niektóre cechy spektrogramów sugerują, że badana cząsteczka będzie zawierać pewne podstruktury i nie będzie zawierać innych. Wiedzę tę można wykorzystać do ograniczenia możliwych struktur generowanych przez Algorytm Dendrala Lederberga. Wiedza tego rodzaju była reprezentowana jako "reguły". Oto jeden przykład reguły Dendral:

Reguła 74:
IF Widmo cząsteczki ma dwa piki
o masach X1 i X2 takich, że:
X1 + X2 = M + 28
i
X1 - 28 to wysoki pik
i
X2 - 28 to wysoki pik
i
co najmniej jeden z X1 lub X2 jest wysoki
TO Cząsteczka zawiera grupę ketonową

Pierwszy program wykorzystujący tę wiedzę nazywał się HEURISTIC DENDRAL. (Przymiotnik "heurystyczny" został użyty, ponieważ wiedza chemików została wykorzystana do kontroli wyszukiwania w drzewie Dendral.) Użyto go jako danych wejściowych wzoru chemicznego i danych spektrometru masowego (a czasami danych jądrowego rezonansu magnetycznego) i wytworzono jako wynik uporządkowany zestaw opisów struktury chemicznej postawiony hipotetycznie w celu wyjaśnienia danych. Wczesna praca z HEURISTIC DENDRAL ograniczała się do wyjaśnienia struktury związków acyklicznych, ponieważ były to jedyne, z którymi algorytm Lederberga mógł sobie poradzić. Obejmowały one nasycone acykliczne etery, alkohole, tioetery, tiole i aminy. Oto przykład siły ich wczesnego programu: istnieje 14 715 813 możliwych struktur N, N-dimetylo-1-oktadecyloaminy. Wykorzystując widmo masowe tego związku, HEURISTIC DENDRAL zmniejszył numer do 1 284 792. Wykorzystując dane widma masowego i jądrowego rezonansu magnetyczno-jądrowego, przetrwała tylko jedna struktura. Nazwa "DENDRAL "zaczęła opisywać całą kolekcję programów służących do wyjaśnienia struktury opracowanych podczas projektu Dendral, które trwało do końca lat siedemdziesiątych. Wiele z tych programów jest dziś używanych przez chemików. Informatycy i chemicy pracujący nad projektem byli w stanie rozszerzyć algorytm Lederberga na związki cykliczne. Po tym, jak Lederberg przekonał chemika Stanforda Carla Djerassiego do przyłączenia się do projektu, wydajność została znacznie zwiększona zarówno pod względem szerokości, jak i głębokości. Ważną innowacją dokonaną podczas projektu Dendral była symulacja rozpadu struktury chemicznej w spektrometrze mas. Po wytworzeniu przez HEURISTIC DENDRAL niektórych struktur kandydujących dla określonego związku, struktury te poddano analizie w symulowanym spektrometrze mas. Wyniki porównano następnie z rzeczywistą mocą spektrometru masowego. Struktura, której symulowany spektrogram był najbliższy rzeczywistemu spektrogramowi, prawdopodobnie była faktyczną strukturą związku. Ten proces "analizy przez syntezę" stał się szeroko stosowany w sztucznej inteligencji, zwłaszcza w wizji komputerowej. Opierając się na swoim doświadczeniu w latach DENDRAL, Feigenbaum opowiadał się za znaczeniem specjalistycznej wiedzy na temat dziedziny problemów w aplikacjach AI (w przeciwieństwie do stosowania ogólnych metod wnioskowania). Zaproponował coś, co nazwał hipotezą "wiedzy-mocy", którą później nazwał "zasadą wiedzy". Oto jak to później opisał: Musimy postawić hipotezę z naszego dotychczasowego doświadczenia, że moc rozwiązywania problemów wykazywana w działaniu inteligentnego agenta jest przede wszystkim konsekwencją wiedzy specjalisty wykorzystywanej przez agenta, a jedynie bardzo wtórnie związana z ogólnością i mocą zastosowanej metody wnioskowania. Nasi agenci muszą być bogaci w wiedzę, nawet jeśli nie znają metod. Wykorzystanie wiedzy ekspertów w programach AI doprowadziło do rozwoju wielu systemów eksperckich, "jak zobaczymy później. Doprowadziło to również do zwiększonej koncentracji na specyficznych i wysoce ograniczonych problemach i odejścia od koncentrowania się na ogólnych mechanizmach inteligencji