Dendral - Dendral

Dendral był projektem związanym ze sztuczną inteligencją (AI) lat 60. i stworzonym przez niego systemem eksperckim oprogramowania komputerowego . Jego głównym celem było zbadanie formułowania i odkrywania hipotez w nauce. W tym celu wybrano konkretne zadanie w nauce: pomóc chemikom organicznym w identyfikacji nieznanych cząsteczek organicznych poprzez analizę ich widm masowych i wykorzystanie wiedzy chemicznej. To było zrobione w Stanford University przez Edward Feigenbaum , Bruce G. Buchanan , Joshua Lederberg i Carl Djerassi , wraz z zespołem wysoce kreatywnych współpracowników naukowych i studentów. Zaczęło się w 1965 roku i obejmuje mniej więcej połowę historii badań nad sztuczną inteligencją.

Oprogramowanie Dendral jest uważane za pierwszy system ekspercki, ponieważ zautomatyzowało proces podejmowania decyzji i rozwiązywanie problemów przez chemików organicznych. Projekt składał się z badań nad dwoma głównymi programami Heuristic Dendral i Meta-Dendral oraz kilkoma podprogramami. Został napisany w języku programowania Lisp , który został uznany za język AI ze względu na jego elastyczność.

Wiele systemów wywodzi się z Dendral, w tym MYCIN , MOLGEN, PROSPECTOR, XCON i STEAMER. Obecnie istnieje wiele innych programów do rozwiązywania problemu odwrotności spektrometrii mas, patrz Lista oprogramowania do spektrometrii mas , ale nie są one już opisywane jako „sztuczna inteligencja”, tylko jako poszukiwacze struktur.

Nazwa Dendral jest akronimem terminu „algorytm dendrytyczny”.

Heuristic Dendral

Heuristic Dendral to program, który wykorzystuje widma masowe lub inne dane eksperymentalne wraz z bazą wiedzy chemicznej w celu stworzenia zestawu możliwych struktur chemicznych, które mogą być odpowiedzialne za tworzenie danych. Spektrometr masowy wytwarza widmo masowe związku i służy do określenia jego masy cząsteczkowej, czyli sumy mas jego składników atomowych. Na przykład, związek woda (H2O) ma masę cząsteczkową 18, ponieważ wodór ma masę 1,01, a tlen 16,00, a jego widmo masowe ma pik przy 18 jednostkach. Heurystyczny Dendral użyłby tej masy wejściowej oraz znajomości liczb mas atomowych i reguł walencyjnych, aby określić możliwe kombinacje składników atomowych, których masa sumowałaby się do 18. Wraz ze wzrostem wagi i zwiększeniem złożoności cząsteczek liczba możliwych związków drastycznie wzrasta. Zatem program, który jest w stanie zredukować tę liczbę kandydujących rozwiązań poprzez proces formułowania hipotez, jest niezbędny.

Nowe algorytmy oparte na teorii grafów zostały wynalezione przez Lederberga, Harolda Browna i innych, które generują wszystkie wykresy z określonym zestawem węzłów i typami połączeń (atomy chemiczne i wiązania) - z cyklami lub bez. Ponadto zespół był w stanie matematycznie udowodnić, że generator jest kompletny, ponieważ generuje wszystkie wykresy z określonymi węzłami i krawędziami oraz że nie jest nadmiarowy, ponieważ dane wyjściowe nie zawierają równoważnych wykresów (np. Odbicia lustrzane) . Program CONGEN, jak stał się znany, został opracowany w dużej mierze przez chemików obliczeniowych Ray Carharta, Jima Nourse'a i Dennisa Smitha. Był przydatny dla chemików jako samodzielny program do generowania wykresów chemicznych pokazujących pełną listę struktur spełniających ograniczenia określone przez użytkownika.

Meta-Dendral

Meta-Dendral to system uczenia maszynowego, który otrzymuje zestaw możliwych struktur chemicznych i odpowiadających im widm masowych jako dane wejściowe i proponuje zestaw reguł spektrometrii mas, które korelują cechy strukturalne z procesami wytwarzającymi widmo mas. Te zasady zostaną zwrócone do Heuristic Dendral (w programach planowania i testowania opisanych poniżej) w celu przetestowania ich zastosowania. Zatem „Heurystyczny Dendral to system wydajności, a Meta-Dendral to system uczący się”. Program opiera się na dwóch ważnych cechach: paradygmacie plan-generowanie-test i inżynierii wiedzy.

Paradygmat planowania-generowania-testów

Paradygmat plan-generuj-test jest podstawową organizacją metody rozwiązywania problemów i jest powszechnym paradygmatem używanym zarówno przez heurystyczny system Dendral, jak i Meta-Dendral . Generatora (później nazwany CONGEN) generuje możliwych rozwiązań dla poszczególnych problemów, które są wyrażone w postaci wykresów chemicznych w dendral. Jest to jednak możliwe tylko wtedy, gdy liczba propozycji rozwiązań jest minimalna. Gdy istnieje duża liczba możliwych rozwiązań, Dendral musi znaleźć sposób na wprowadzenie ograniczeń, które wykluczają duże zestawy rozwiązań kandydujących. To jest główny cel Dendral planner , który jest programem „formułowania hipotez”, który wykorzystuje „wiedzę specyficzną dla zadania, aby znaleźć ograniczenia dla generatora”. Wreszcie tester analizuje każde proponowane rozwiązanie kandydata i odrzuca te, które nie spełniają określonych kryteriów. Ten mechanizm paradygmatu generowania planu i testu jest tym, co trzyma Dendral razem.

Inżynieria wiedzy

Podstawowym celem inżynierii wiedzy jest osiągnięcie produktywnej interakcji między dostępną bazą wiedzy a technikami rozwiązywania problemów. Jest to możliwe dzięki opracowaniu procedury, w której duże ilości informacji specyficznych dla zadania są kodowane w programach heurystycznych. Zatem pierwszym istotnym składnikiem inżynierii wiedzy jest duża „baza wiedzy”. Dendral posiada specjalistyczną wiedzę na temat techniki spektrometrii mas, dużą ilość informacji, które stanowią podstawę chemii i teorii grafów, a także informacje, które mogą być pomocne w znalezieniu rozwiązania konkretnego problemu wyjaśniającego strukturę chemiczną. Ta „baza wiedzy” jest używana zarówno do wyszukiwania możliwych struktur chemicznych, które pasują do danych wejściowych, jak i do uczenia się nowych „ogólnych zasad”, które pomagają w wyszukiwaniu śliwek. Korzyścią, jaką Dendral zapewnia użytkownikowi końcowemu, nawet nie będącemu ekspertem, jest zminimalizowany zestaw możliwych rozwiązań do ręcznego sprawdzenia.

Heurystyka

Heurystyczny jest zasada, algorytmu, który nie gwarantuje rozwiązanie, ale ogranicza liczbę możliwych rozwiązań odrzucając mało prawdopodobne i nietrafnych rozwiązań. Użycie heurystyki do rozwiązywania problemów nazywane jest „programowaniem heurystycznym” i było używane w Dendral, aby umożliwić replikację w maszynach procesu, za pomocą którego eksperci od ludzi wprowadzają rozwiązanie problemów za pomocą praktycznych reguł i konkretnych informacji.

Programowanie heurystyczne było głównym podejściem i ogromnym krokiem naprzód w dziedzinie sztucznej inteligencji, ponieważ pozwoliło naukowcom ostatecznie zautomatyzować pewne cechy ludzkiej inteligencji. Stało się widoczne wśród naukowców pod koniec lat czterdziestych dzięki książce George'a Polyi How to Solve It: A New Aspect of Mathematical Method . Jak powiedział Herbert A. Simon w The Sciences of the Artificial , „jeśli przyjmiesz heurystyczny wniosek jako pewny, możesz zostać oszukany i rozczarowany; ale jeśli całkowicie zaniedbasz heurystyczne wnioski, nie zrobisz żadnego postępu”.

Historia

W połowie XX wieku pytanie „czy maszyny mogą myśleć?” stał się intrygujący i popularny wśród naukowców, głównie w celu dodania humanistycznych cech do zachowania maszyn. John McCarthy , który był jednym z czołowych badaczy w tej dziedzinie, nazwał tę koncepcję inteligencji maszynowej „ sztuczną inteligencją ” (AI) latem w Dartmouth w 1956 roku. AI jest zwykle definiowana jako zdolność maszyny do wykonywania operacji, które są analogiczne do ludzkich zdolności poznawczych. Wiele badań nad stworzeniem sztucznej inteligencji przeprowadzono w XX wieku.

Również około połowy XX wieku nauka, zwłaszcza biologia, stanęła w obliczu szybko rosnącej potrzeby stworzenia „symbiozy człowiek-komputer”, aby pomóc naukowcom w rozwiązywaniu problemów. Na przykład analiza strukturalna miogobliny , hemoglobiny i innych białek wymagała nieustannie rozwoju oprzyrządowania ze względu na swoją złożoność.

We wczesnych latach sześćdziesiątych Joshua Lederberg rozpoczął pracę z komputerami i szybko zainteresował się tworzeniem interaktywnych komputerów, które miały mu pomóc w badaniach egzobiologicznych . W szczególności był zainteresowany projektowaniem systemów komputerowych, które pomogłyby mu w badaniu obcych związków organicznych. Ponieważ nie był ekspertem ani w chemii, ani w programowaniu komputerowym, współpracował z chemikiem ze Stanford Carlem Djerassim, aby pomóc mu w chemii, i Edwardem Feigenbaumem w programowaniu, aby zautomatyzować proces określania struktur chemicznych na podstawie surowych danych spektrometrii mas. Feigenbaum był ekspertem w językach programowania i heurystyce i pomógł Lederbergowi zaprojektować system, który naśladował sposób, w jaki Djerassi rozwiązywał problemy z wyjaśnieniem struktury. Opracowali system zwany algorytmem dendrytycznym (Dendral), który był w stanie wygenerować możliwe struktury chemiczne odpowiadające danym ze spektrometrii mas jako wyjście.

Dendral był wówczas nadal bardzo niedokładny w ocenie widm ketonów , alkoholi i izomerów związków chemicznych. W ten sposób Djerassi „nauczył” Dendral'a ogólnych zasad, które mogą pomóc wyeliminować większość „chemicznie nieprawdopodobnych” struktur i stworzyć zestaw struktur, które mogą być teraz analizowane przez „nie-eksperta” użytkownika w celu określenia właściwej struktury.

Zespół Dendral zwerbował Bruce'a Buchanana do rozszerzenia programu Lisp napisanego początkowo przez Georgię Sutherland. Buchanan miał podobne pomysły jak Feigenbaum i Lederberg, ale jego szczególnymi zainteresowaniami były odkrycia naukowe i formowanie hipotez. Jak powiedział Joseph November w Digitizing Life: The Introduction of Computers to Biology and Medicine , „(Buchanan) chciał, aby system (Dendral) dokonywał własnych odkryć, a nie tylko pomagał ludziom w ich dokonywaniu”. Buchanan, Lederberg i Feigenbaum zaprojektowali „Meta-Dendral”, który był „twórcą hipotez”. Heurystyczny Dendral „służyłby jako szablon dla podobnych systemów opartych na wiedzy w innych obszarach”, zamiast koncentrować się tylko na chemii organicznej. Meta-Dendral był modelem bogatych w wiedzę systemów uczenia się, który został później skodyfikowany w wpływowym modelu uczenia się w przestrzeni wersji Toma Mitchella .

Uwagi

Bibliografia

  1. Berk, A. A. LISP: język sztucznej inteligencji. Nowy Jork: Van Nostrand Reinhold Company, 1985. 1-25.
  2. Lederberg, Joshua. Kryzys instrumentacyjny w biologii . Szkoła Medyczna Uniwersytetu Stanforda. Palo Alto, 1963.
  3. Lederberg, Joshua. Jak powstał i urodził się Dendral . ACM Symposium on the History of Medical Informatics, 5 listopada 1987, Rockefeller University. Nowy Jork: National Library of Medicine, 1987.
  4. Lindsay, Robert K., Bruce G. Buchanan, Edward A. Feigenbaum i Joshua Lederberg. Zastosowania sztucznej inteligencji w chemii organicznej: projekt Dendral . McGraw-Hill Book Company, 1980.
  5. Lindsay, Robert K., Bruce G. Buchanan, EA Feigenbaum i Joshua Lederberg. DENDRAL: studium przypadku pierwszego systemu eksperckiego do formułowania hipotez naukowych . Sztuczna inteligencja 61, 2 (1993): 209-261.
  6. Listopad, Joseph A. „Digitizing Life: The Introduction of Computers to Biology and Medicine”. Rozprawa doktorska, Princeton University, 2006