Kunstmatige Intelligentie Samenvatting 2
Cyclisch pessimisme: Ontstaat in onderzoek gemeenschap → Teruggang in investeringen →
Onderzoek moet worden gestopt. Vaak bij opkomende technologieën.
Investeerders zijn ontevreden. Dit kwam vaak doordat onderzoekers irreële pretenties hadden.
Toepassingen zijn oa: Computer vertalingen, militaire toepassing, spraakherkenning. Hidden
Markov models was een erg belangrijk onderzoek voor spraakherkenning:
Fundamentele problemen in onderzoek (James Lighthill 1973):
• Combinatorial explosion: 2n bij binaire variabelen, maar Zn bij variabelen die Z
verschillende waarden toestaan.
• Intractability: Berekening waarin met 2n operaties moeten plaatsvinden. Al bij en kleine
n, moeten heel erg veel operaties uitgevoerd worden.
• Toy problems.
Onbeslisbaarheid (Halting Problem):
• Kun je beslissen of een programma stopt of niet? Ja/nee vraag.
• Als beslisbaar, dan berekenbare functie f(x,y) := {1, als programma x met invoer y
eindigt, anders 0}. Een gedeelte van de functie wordt gedefinieerd als functie g: g(x) = {0
als h(x,x) = 0, ongedefinieerd als h(x,x) ≠ 0}.
• Conclusie:
o Er is geen berekenbare functie die correcte uitkomsten voor halting problem kan
geven
o Andere onbeslisbare problemen zijn:
▪ Eerste orde logica/FOL
▪ Iedere logische taal met equivalentie en 1 ander binair predicaat
o FOL: gedeeltelijk waar
▪ Als iets logisch gevolg heeft, dan is er een algoritme dat dat 1 maakt
▪ Als geen logisch gevolg, dan hoeft er geen algoritme te zijn dat dat 0
maakt
, Berekenbaarheid (intractability, combinatorial explosion):
• Richard Karp: Er zijn veel problemen die exponentiële tijd nodig hebben, waardoor
alleen toy problems opgelost kunnen worden.
• Intractable problem: problem dat niet snel genoeg opgelost wordt, waardoor de
oplossing niet bruikbaar is. Intractable betekent dat het niet meer werkt.
• In KI willen we consistente en volledige theoriën:
o Theorie; verzameling zinnen
o Consistentie; zinnen spreken elkaar niet tegen
o Volledigheid; als een zin waar is, zit hij in de theorie
• Gödel zinnen: zinnen die waar en onbeslisbaar zijn
o Eerste onvolledigheidsstelling:
▪ Iedere formele theorie die in staat is om basale getaltheorie te
beschrijven, kan niet zowel consistent alsook volledig zijn.
▪ In iedere enigszins interessante consistente formele theorie, is er een
oneindig aantal zinnen dat die wel waar zijn, maar die niet bewijsbaar
zijn binnen die theorie
o Tweede onvolledigheidsstelling:
▪ Een theorie kan bewijzen dat ze zelf consistent is dan en slechts dan die
theorie inconsistent is.
▪ Dit is de consequentie van het formuleren van de eerste
onvolledigheidsstelling binnen een formele theorie.
Mathematische inductie: 0 is een getal. Als x een getal is, dan is s(x) ook een getal.
• Theorie: een verzameling zinnen.
• Consistentie: de theorie bevat geen zinnen die elkaar tegenspreken.
• Volledigheid: als een zin waar is, dan zit hij in de theorie.
Gödel zinnen maken theorieën inconsistent of onvolledig.
Kwalitatieve fundamentele problemen:
• Commensense knowledge problem: Het systeem moet de context van een uitspraak
probleem weten om het probleem goed te kunnen begrijpen.
• Moravec’s paradox: Taken die makkelijk zijn voor de mens, zijn heel oud en doen we
(bijna) onbewust waardoor we ze moeilijk kunnen implementeren, terwijl we ons van de
werking van moeilijke taken erg bewust zijn waardoor we ze makkelijk kunnen
implementeren.
• Qualification problem: Het is onmogelijk om alle condities te beschrijven die nodig zijn
om een actie te laten plaatsvinden. Hoe moet er om worden gegaan met dingen die
voorkomen dat het doel behaald wordt. Onder welke omstandigheden mag een regel
worden toegepast?
• Frame problem: Welke kenmerken blijven er na een actie nog hetzelfde in de wereld.
(tegenovergestelde van Qualification problem), Zie artikel Morgenstern
• Various objections (disability, informality, mathematical)
• Philosophical underpinnings
Situation calculus (McCarthy, 1958):
• Situation as a snapshot in time of the world
• State is an collection of situations, ordered in time
• States are fluents: their value changes over time
• Actions are functions from state before to state after
• Problem: predicting how things stay the same as actions occur
Cyclisch pessimisme: Ontstaat in onderzoek gemeenschap → Teruggang in investeringen →
Onderzoek moet worden gestopt. Vaak bij opkomende technologieën.
Investeerders zijn ontevreden. Dit kwam vaak doordat onderzoekers irreële pretenties hadden.
Toepassingen zijn oa: Computer vertalingen, militaire toepassing, spraakherkenning. Hidden
Markov models was een erg belangrijk onderzoek voor spraakherkenning:
Fundamentele problemen in onderzoek (James Lighthill 1973):
• Combinatorial explosion: 2n bij binaire variabelen, maar Zn bij variabelen die Z
verschillende waarden toestaan.
• Intractability: Berekening waarin met 2n operaties moeten plaatsvinden. Al bij en kleine
n, moeten heel erg veel operaties uitgevoerd worden.
• Toy problems.
Onbeslisbaarheid (Halting Problem):
• Kun je beslissen of een programma stopt of niet? Ja/nee vraag.
• Als beslisbaar, dan berekenbare functie f(x,y) := {1, als programma x met invoer y
eindigt, anders 0}. Een gedeelte van de functie wordt gedefinieerd als functie g: g(x) = {0
als h(x,x) = 0, ongedefinieerd als h(x,x) ≠ 0}.
• Conclusie:
o Er is geen berekenbare functie die correcte uitkomsten voor halting problem kan
geven
o Andere onbeslisbare problemen zijn:
▪ Eerste orde logica/FOL
▪ Iedere logische taal met equivalentie en 1 ander binair predicaat
o FOL: gedeeltelijk waar
▪ Als iets logisch gevolg heeft, dan is er een algoritme dat dat 1 maakt
▪ Als geen logisch gevolg, dan hoeft er geen algoritme te zijn dat dat 0
maakt
, Berekenbaarheid (intractability, combinatorial explosion):
• Richard Karp: Er zijn veel problemen die exponentiële tijd nodig hebben, waardoor
alleen toy problems opgelost kunnen worden.
• Intractable problem: problem dat niet snel genoeg opgelost wordt, waardoor de
oplossing niet bruikbaar is. Intractable betekent dat het niet meer werkt.
• In KI willen we consistente en volledige theoriën:
o Theorie; verzameling zinnen
o Consistentie; zinnen spreken elkaar niet tegen
o Volledigheid; als een zin waar is, zit hij in de theorie
• Gödel zinnen: zinnen die waar en onbeslisbaar zijn
o Eerste onvolledigheidsstelling:
▪ Iedere formele theorie die in staat is om basale getaltheorie te
beschrijven, kan niet zowel consistent alsook volledig zijn.
▪ In iedere enigszins interessante consistente formele theorie, is er een
oneindig aantal zinnen dat die wel waar zijn, maar die niet bewijsbaar
zijn binnen die theorie
o Tweede onvolledigheidsstelling:
▪ Een theorie kan bewijzen dat ze zelf consistent is dan en slechts dan die
theorie inconsistent is.
▪ Dit is de consequentie van het formuleren van de eerste
onvolledigheidsstelling binnen een formele theorie.
Mathematische inductie: 0 is een getal. Als x een getal is, dan is s(x) ook een getal.
• Theorie: een verzameling zinnen.
• Consistentie: de theorie bevat geen zinnen die elkaar tegenspreken.
• Volledigheid: als een zin waar is, dan zit hij in de theorie.
Gödel zinnen maken theorieën inconsistent of onvolledig.
Kwalitatieve fundamentele problemen:
• Commensense knowledge problem: Het systeem moet de context van een uitspraak
probleem weten om het probleem goed te kunnen begrijpen.
• Moravec’s paradox: Taken die makkelijk zijn voor de mens, zijn heel oud en doen we
(bijna) onbewust waardoor we ze moeilijk kunnen implementeren, terwijl we ons van de
werking van moeilijke taken erg bewust zijn waardoor we ze makkelijk kunnen
implementeren.
• Qualification problem: Het is onmogelijk om alle condities te beschrijven die nodig zijn
om een actie te laten plaatsvinden. Hoe moet er om worden gegaan met dingen die
voorkomen dat het doel behaald wordt. Onder welke omstandigheden mag een regel
worden toegepast?
• Frame problem: Welke kenmerken blijven er na een actie nog hetzelfde in de wereld.
(tegenovergestelde van Qualification problem), Zie artikel Morgenstern
• Various objections (disability, informality, mathematical)
• Philosophical underpinnings
Situation calculus (McCarthy, 1958):
• Situation as a snapshot in time of the world
• State is an collection of situations, ordered in time
• States are fluents: their value changes over time
• Actions are functions from state before to state after
• Problem: predicting how things stay the same as actions occur
