Dendral

Dendral var ett projekt inom artificiell intelligens (AI) på 1960-talet, och det datorprogramexpertsystem som det producerade. Dess primära syfte var att studera hypotesbildning och upptäckt inom vetenskap. För det valdes en specifik uppgift inom vetenskapen: hjälpa organiska kemister att identifiera okända organiska molekyler, genom att analysera deras masspektra och använda kunskap om kemi. Det gjordes vid Stanford University av Edward Feigenbaum , Bruce G. Buchanan, Joshua Lederberg och Carl Djerassi , tillsammans med ett team av mycket kreativa forskarkollegor och studenter. Det började 1965 och spänner över ungefär hälften av AI-forskningens historia.

Programvaran Dendral anses vara det första expertsystemet eftersom det automatiserade organiska kemisters beslutsfattande och problemlösningsbeteende. Projektet bestod av forskning kring två huvudprogram Heuristic Dendral och Meta-Dendral , samt flera delprogram. Det skrevs i programmeringsspråket Lisp , som ansågs vara AI-språket på grund av dess flexibilitet.

Många system härleddes från Dendral, inklusive MYCIN , MOLGEN, PROSPECTOR, XCON och SEAMER. Det finns många andra program idag för att lösa det omvända masspektrometriproblemet, se Lista över programvara för masspektrometri , men de beskrivs inte längre som "artificiell intelligens", bara som struktursökare.

Namnet Dendral är en akronym av termen "dendritisk algoritm".

Heuristisk Dendral

Heuristic Dendral är ett program som använder masspektra eller andra experimentella data tillsammans med en kunskapsbas om kemi för att producera en uppsättning möjliga kemiska strukturer som kan vara ansvariga för att producera data. Ett masspektrum av en förening produceras av en masspektrometer och används för att bestämma dess molekylvikt, summan av massorna av dess atomära beståndsdelar. Till exempel har det sammansatta vattnet (H2O), en molekylvikt på 18 eftersom väte har en massa på 1,01 och syre 16,00, och dess masspektrum har en topp vid 18 enheter. Heuristiska Dendral skulle använda denna ingående massa och kunskapen om atommassatal och valensregler för att bestämma de möjliga kombinationerna av atombeståndsdelar vars massa skulle summera till 18. När vikten ökar och molekylerna blir mer komplexa, ökar antalet möjliga föreningar. ökar drastiskt. Således är ett program som kan minska detta antal kandidatlösningar genom hypotesbildningsprocessen väsentligt.

Nya grafteoretiska algoritmer uppfanns av Lederberg, Harold Brown och andra som genererar alla grafer med en specificerad uppsättning noder och anslutningstyper (kemiska atomer och bindningar) - med eller utan cykler. Dessutom kunde teamet bevisa matematiskt att generatorn är komplett, genom att den producerar alla grafer med de angivna noderna och kanterna, och att den är icke-redundant, eftersom utdata inte innehåller några ekvivalenta grafer (t.ex. spegelbilder) . CONGEN-programmet, som det blev känt, utvecklades till stor del av beräkningskemisterna Ray Carhart, Jim Nourse och Dennis Smith. Det var användbart för kemister som ett fristående program för att generera kemiska grafer som visar en komplett lista över strukturer som uppfyller de begränsningar som specificerats av en användare.

Meta-Dendral

Meta-Dendral är ett maskininlärningssystem som tar emot uppsättningen av möjliga kemiska strukturer och motsvarande masspektra som input, och föreslår en uppsättning regler för masspektrometri som korrelerar strukturella egenskaper med processer som producerar masspektrat. Dessa regler skulle återkopplas till Heuristic Dendral (i planerings- och testprogrammen som beskrivs nedan) för att testa deras tillämplighet. Således, "Heuristic Dendral är ett prestationssystem och Meta-Dendral är ett inlärningssystem". Programmet är baserat på två viktiga funktioner: plan-generera-test-paradigmet och kunskapsteknik.

Planera-generera-test-paradigm

Plan-generera-test-paradigmet är den grundläggande organisationen av problemlösningsmetoden, och är ett vanligt paradigm som används av både heuristiska Dendral- och Meta-Dendral- system. Generatorn (senare kallad CONGEN) genererar potentiella lösningar för ett visst problem, som sedan uttrycks som kemiska grafer i Dendral . Detta är dock möjligt endast när antalet kandidatlösningar är minimalt. När det finns ett stort antal möjliga lösningar måste Dendral hitta ett sätt att sätta begränsningar som utesluter stora uppsättningar av kandidatlösningar. Detta är det primära syftet med Dendral planner , som är ett "hypotesbildning"-program som använder "uppgiftsspecifik kunskap för att hitta begränsningar för generatorn". Sist men inte minst testaren varje föreslagen kandidatlösning och kasserar de som inte uppfyller vissa kriterier. Denna mekanism av plan-generera-test-paradigm är det som håller ihop Dendral.

Kunskapsteknik

Det primära syftet med kunskapsteknik är att uppnå en produktiv interaktion mellan den tillgängliga kunskapsbasen och problemlösningstekniker. Detta är möjligt genom utveckling av en procedur där stora mängder uppgiftsspecifik information kodas in i heuristiska program. Således är den första väsentliga komponenten i kunskapsteknik en stor " kunskapsbas." Dendral har specifik kunskap om masspektrometritekniken, en stor mängd information som ligger till grund för kemi och grafteori, och information som kan vara till hjälp för att hitta lösningen på ett visst problem med att belysa kemiska strukturer. Denna "kunskapsbas" används både för att söka efter möjliga kemiska strukturer som matchar indata, och för att lära sig nya "allmänna regler" som hjälper till att beskära sökningar. Fördelen som Dendral ger slutanvändaren, även en icke-expert, är en minimerad uppsättning möjliga lösningar att kontrollera manuellt.

Heuristik

En heuristik är en tumregel, en algoritm som inte garanterar en lösning, men som minskar antalet möjliga lösningar genom att kassera osannolika och irrelevanta lösningar. Användningen av heuristik för att lösa problem kallas "heuristisk programmering", och användes i Dendral för att tillåta den att i maskiner replikera den process genom vilken mänskliga experter inducerar lösningen på problem via tumregler och specifik information.

Heuristisk programmering var ett stort tillvägagångssätt och ett stort steg framåt inom artificiell intelligens, eftersom det gjorde det möjligt för forskare att äntligen automatisera vissa egenskaper hos mänsklig intelligens. Det blev framträdande bland forskare i slutet av 1940-talet genom George Polyas bok, How to Solve It: A New Aspect of Mathematical Method . Som Herbert A. Simon sa i The Sciences of the Artificial , "om du tar en heuristisk slutsats som säker kan du bli lurad och besviken, men om du försummar heuristiska slutsatser helt och hållet kommer du inte att göra några framsteg alls."

Historia

Under mitten av 1900-talet kom frågan "kan maskiner tänka?" blev spännande och populärt bland forskare, främst för att lägga till humanistiska egenskaper till maskinbeteende. John McCarthy , som var en av de främsta forskarna inom detta område, kallade detta koncept av maskinintelligens som " artificiell intelligens " (AI) under Dartmouth-sommaren 1956. AI definieras vanligtvis som en maskins kapacitet att utföra operationer som är analogt med mänskliga kognitiva förmågor. Mycket forskning för att skapa AI gjordes under 1900-talet.

Också runt mitten av 1900-talet stod vetenskapen, särskilt biologin, inför ett snabbt ökande behov av att utveckla en "man-dator-symbios", för att hjälpa forskare att lösa problem. Till exempel behövde den strukturella analysen av myogoblin, hemoglobin och andra proteiner obevekligt utveckling av instrumentering på grund av dess komplexitet.

I början av 1960-talet började Joshua Lederberg arbeta med datorer och blev snabbt enormt intresserad av att skapa interaktiva datorer för att hjälpa honom i hans exobiologiforskning . Specifikt var han intresserad av att designa datorsystem för att hjälpa honom att studera främmande organiska föreningar. Eftersom han inte var expert på vare sig kemi eller datorprogrammering, samarbetade han med Stanford-kemisten Carl Djerassi för att hjälpa honom med kemi, och Edward Feigenbaum med programmering, för att automatisera processen att bestämma kemiska strukturer från rå masspektrometridata. Feigenbaum var expert på programmeringsspråk och heuristik och hjälpte Lederberg att designa ett system som replikerade hur Djerassi löste strukturförklaringsproblem. De utarbetade ett system som heter Dendritic Algorithm (Dendral) som kunde generera möjliga kemiska strukturer som motsvarar masspektrometridata som en utdata.

Dendral var då fortfarande mycket inexakt i att bedöma spektra av ketoner , alkoholer och isomerer av kemiska föreningar. Således "lärde" Djerassi ut allmänna regler för Dendral som kunde hjälpa till att eliminera de flesta av de "kemiskt osannolika" strukturerna, och producera en uppsättning strukturer som nu kunde analyseras av en "icke-expert" användare för att bestämma rätt struktur.

Dendral-teamet rekryterade Bruce Buchanan för att utöka Lisp-programmet som ursprungligen skrevs av Georgia Sutherland. Buchanan hade liknande idéer som Feigenbaum och Lederberg, men hans speciella intressen var vetenskaplig upptäckt och hypotesbildning. Som Joseph November sa i Digitalizing Life: The Introduction of Computers to Biology and Medicine, "(Buchanan) ville att systemet (Dendral) skulle göra upptäckter på egen hand, inte bara hjälpa människor att göra dem". Buchanan, Lederberg och Feigenbaum designade "Meta-Dendral", som var en "hypotesmakare". Heuristiska Dendral "skulle tjäna som en mall för liknande kunskapsbaserade system inom andra områden" snarare än att bara koncentrera sig på området organisk kemi. Meta-Dendral var en modell för kunskapsrika lärsystem som senare kodifierades i Tom Mitchells inflytelserika Version Space Model of learning.

Anteckningar

1. Berk, A. LISP: Språket för artificiell intelligens. New York: Van Nostrand Reinhold Company, 1985. 1-25.
2. Lederberg, Joshua. En instrumenteringskris i biologi . Stanford University Medical School. Palo Alto, 1963.
3. Lederberg, Joshua. Hur Dendral föddes och föddes . ACM Symposium on the History of Medical Informatics, 5 november 1987, Rockefeller University. New York: National Library of Medicine, 1987.
4. Lindsay, Robert K., Bruce G. Buchanan, Edward A. Feigenbaum och Joshua Lederberg. Tillämpningar av artificiell intelligens för organisk kemi: Dendral-projektet . McGraw-Hill Book Company, 1980.
5. Lindsay, Robert K., Bruce G. Buchanan, EA Feigenbaum och Joshua Lederberg. DENDRAL: En fallstudie av det första expertsystemet för bildning av vetenskapliga hypoteser . Artificial Intelligence 61, 2 (1993): 209-261.
6. November, Joseph A. "Digitisera livet: introduktionen av datorer till biologi och medicin." Doktorsavhandling, Princeton University, 2006