Úvod do umělé inteligence, řešení problémů Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: Co je “umělá inteligence” Organizace předmětu PB016 Řešení problémů Úvod do umělé inteligence 1/12 1 / 22 Co je “umělá inteligence” Co je “umělá inteligence” ? Úvod do umělé inteligence 1/12 2 / 22 Co je “umělá inteligence” Co je “umělá inteligence” ? → sli.do/uui SliDo Úvod do umělé inteligence 1/12 2 / 22 Co je “umělá inteligence” Co je “umělá inteligence” Communication on AI for Europe, COM 2018/237 final Artificial intelligence (AI) refers to systems that display intelligent behaviour by analysing their environment and taking actions – with some degree of autonomy – to achieve specific goals. AI-based systems can be purely software-based, acting in the virtual world (e.g. voice assistants, image analysis software, search engines, speech and face recognition systems) or AI can be embedded in hardware devices (e.g. advanced robots, autonomous cars, drones or Internet of Things applications). High Level Expert Group, A definition of AI, 2019 EU Artificial Intelligence Act, A definition of AI, COM/2021/206 final Úvod do umělé inteligence 1/12 3 / 22 Co je “umělá inteligence” Co je “umělá inteligence” Communication on AI for Europe, COM 2018/237 final High Level Expert Group, A definition of AI, 2019 Artificial intelligence (AI) systems are software (and possibly also hardware) systems designed by humans that, given a complex goal, act in the physical or digital dimension by perceiving their environment through data acquisition, interpreting the collected structured or unstructured data, reasoning on the knowledge, or processing the information, derived from this data and deciding the best action(s) to take to achieve the given goal. AI systems can either use symbolic rules or learn a numeric model, and they can also adapt their behaviour by analysing how the environment is affected by their previous actions. EU Artificial Intelligence Act, A definition of AI, COM/2021/206 final Úvod do umělé inteligence 1/12 3 / 22 Co je “umělá inteligence” Co je “umělá inteligence” Communication on AI for Europe, COM 2018/237 final High Level Expert Group, A definition of AI, 2019 EU Artificial Intelligence Act, A definition of AI, COM/2021/206 final ‘Artificial intelligence system’ (AI system) means software that is developed with one or more of the techniques and approaches listed in Annex I and can, for a given set of human-defined objectives, generate outputs such as content, predictions, recommendations, or decisions influencing the environments they interact with. Annex I: 1. Machine learning approaches, including supervised, unsupervised and reinforcement learning, using a wide variety of methods including deep learning; 2. Logic- and knowledge-based approaches, including knowledge representation, inductive (logic) programming, knowledge bases, inference and deductive engines, (symbolic) reasoning and expert systems; 3. Statistical approaches, Bayesian estimation, search and optimization methods. Úvod do umělé inteligence 1/12 3 / 22 Co je “umělá inteligence” Co je “umělá inteligence” systém, který se chová jako člověk Úvod do umělé inteligence 1/12 4 / 22 Co je “umělá inteligence” Co je “umělá inteligence” systém, který se chová jako člověk Turingův test (1950) zahrnuje: zpracování přirozeného jazyka (NLP) reprezentaci znalostí (KRepresentation) vyvozování znalostí (KReasoning) strojové učení (počítačové vidění) (robotiku) 1991–2019 – Loebnerova cena (Loebner Prize) → každý rok $4.000 za “nejlidštější” program, nabízí $100.000 a zlatá medaile za složení celého Turingova testu Úvod do umělé inteligence 1/12 4 / 22 Co je “umělá inteligence” Turingův test 2023 Úvod do umělé inteligence 1/12 6 / 22 Co je “umělá inteligence” Turingův test 2023 ChatGPT/Bard nebyly testovány v nastavení podobném Loebnerově ceně předpokládá se ale, že by mohly být úspěšné Úvod do umělé inteligence 1/12 6 / 22 Co je “umělá inteligence” Turingův test 2023 ChatGPT/Bard nebyly testovány v nastavení podobném Loebnerově ceně předpokládá se ale, že by mohly být úspěšné květen 2023 – AI21 Labs z Tel Avivu uspořádala masívní on-line experiment Human or Not? s 1.5 mil. účastníků Úvod do umělé inteligence 1/12 6 / 22 Co je “umělá inteligence” Turingův test 2023 ChatGPT/Bard nebyly testovány v nastavení podobném Loebnerově ceně předpokládá se ale, že by mohly být úspěšné květen 2023 – AI21 Labs z Tel Avivu uspořádala masívní on-line experiment Human or Not? s 1.5 mil. účastníků 40 % chatbotů lidi zmátlo Úvod do umělé inteligence 1/12 6 / 22 Co je “umělá inteligence” Turingův test 2023 ChatGPT/Bard nebyly testovány v nastavení podobném Loebnerově ceně předpokládá se ale, že by mohly být úspěšné květen 2023 – AI21 Labs z Tel Avivu uspořádala masívní on-line experiment Human or Not? s 1.5 mil. účastníků 40 % chatbotů lidi zmátlo hledá se nový “Turingův test” (ConceptARC, Turing test in Creative Arts, artificial capable intelligence, ...) Úvod do umělé inteligence 1/12 6 / 22 Co je “umělá inteligence” systém, který myslí jako člověk snaha porozumět postupům lidského myšlení – kognitivní (poznávací) věda využívá poznatků neurologie, neurochirurgie,. . . Úvod do umělé inteligence 1/12 7 / 22 Co je “umělá inteligence” systém, který myslí jako člověk snaha porozumět postupům lidského myšlení – kognitivní (poznávací) věda využívá poznatků neurologie, neurochirurgie,. . . např. Angela Friederici: Language Processing in the Human Brain Max Planck Institute of Cognitive Neuroscience, Leipzig měření “Event Related Potentials” (ERP) v mozku – jako potvrzení oddělení syntaxe a sémantiky při zpracování věty 2013–2023 Human Brain Project, Geneva, Švýcarsko Úvod do umělé inteligence 1/12 7 / 22 Co je “umělá inteligence” systém, který myslí rozumně od dob Aristotela (350 př.n.l.) náplň studia logiky problém – umět najít řešení teoreticky × prakticky (složitost a vyčíslitelnost) problém – neúplnost a nejistota vstupních dat Úvod do umělé inteligence 1/12 8 / 22 Co je “umělá inteligence” systém, který myslí rozumně od dob Aristotela (350 př.n.l.) náplň studia logiky problém – umět najít řešení teoreticky × prakticky (složitost a vyčíslitelnost) problém – neúplnost a nejistota vstupních dat systém, který se chová rozumně (inteligentně) inteligentní agent – systém, který jedná za nějakým účelem jedná samostatně jedná na základě vstupů ze svého prostředí pracuje delší dobu adaptuje se na změny Úvod do umělé inteligence 1/12 8 / 22 Co je “umělá inteligence” Čím se budeme zabývat? Čím se budeme zabývat? základní struktury a algoritmy běžně používané při technikách programovaní pro inteligentní agenty strategie řešení, prohledávání stavového prostoru, heuristiky, . . . s příklady ve cvičení v jazyce Python Úvod do umělé inteligence 1/12 9 / 22 Co je “umělá inteligence” Čím se budeme zabývat? Náplň předmětu 1 úvod do UI, řešení problémů 2 prohledávání stavového prostoru 3 dekompozice problému, problémy s omezujícími podmínkami 4 hry a základní herní strategie 5 logický agent. výroková logika 6 důkazové metody a systémy, predikátová logika prvního řádu 7 rezoluční metoda, úvod do logického programování průběžná písemka z 1–6 8 reprezentace a vyvozování znalostí 9 zpracování přirozeného jazyka 10 učení, rozhodovací stromy, neuronové sítě 11 hluboké učení 12 generativní modely Úvod do umělé inteligence 1/12 10 / 22 Organizace předmětu PB016 Obsah 1 Co je “umělá inteligence” Čím se budeme zabývat? 2 Organizace předmětu PB016 Základní informace Cvičení 3 Řešení problémů Problém osmi dam I Problém osmi dam II Problém osmi dam III Další příklad – posunovačka Reálné problémy řešitelné prohledáváním Úvod do umělé inteligence 1/12 11 / 22 Organizace předmětu PB016 Organizace předmětu PB016 Hodnocení předmětu: dotazníky na cvičení (12 × 2 = max 24 bodů) nutná podmínka k závěrečné zkoušce ≥ 10 bodů průběžná písemka (max 20 bodů) • v 1/2 semestru – v týdnu po 7. přednášce, pro všechny jediný termín závěrečná písemka (max 60 bodů) • dva řádné a jeden opravný termín hodnocení – součet bodů (max 104 bodů) známka A za > 95 bodů známka E za > 63 bodů rozdíly zk, k, z – různé limity někteří mohou získat extra body ve cvičení (max 1/cvičení) • oprava chyby v materiálech • nadprůměrné elegantní řešení Úvod do umělé inteligence 1/12 12 / 22 Organizace předmětu PB016 Základní informace Základní informace web stránka předmětu – nlp.fi.muni.cz/uui/ slajdy i cvičení – průběžně doplňovány v interaktivních osnovách kontakt na přednášející – Aleš Horák , Luboš Popelínský (Subject: PB016 . . . ) literatura: • Russell, S. a Norvig, P.: Artificial Intelligence: A Modern Approach, 4th ed., Prentice Hall, 2020. (prezenčně v knihovně) • slajdy a cvičení na webu předmětu Úvod do umělé inteligence 1/12 13 / 22 Organizace předmětu PB016 Cvičení Cvičení materiály viz interaktivní osnova cvičení a sdílené disky seminárních skupin (nasdílí cvičící) formát cvičení je prezenční dle rozvrhu, pracuje se u počítače na začátku cvičení odpovědník na znalost tématu přednášky a vyznačených definic ve sbírce příkladů platforma pro řešení úkolů je Google Colaboratory na sdíleném Google disku • Jupyter notebooky (Python + Markdown/LaTeX) cvičení jsou povinná (možné max 3 neomluvené absence) Úvod do umělé inteligence 1/12 14 / 22 Řešení problémů Obsah 1 Co je “umělá inteligence” Čím se budeme zabývat? 2 Organizace předmětu PB016 Základní informace Cvičení 3 Řešení problémů Problém osmi dam I Problém osmi dam II Problém osmi dam III Další příklad – posunovačka Reálné problémy řešitelné prohledáváním Úvod do umělé inteligence 1/12 15 / 22 Řešení problémů Problém osmi dam Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. Úvod do umělé inteligence 1/12 16 / 22 Řešení problémů Problém osmi dam Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. Úvod do umělé inteligence 1/12 16 / 22 Řešení problémů Problém osmi dam Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. celkem pro 8 dam existuje 92 různých řešení Úvod do umělé inteligence 1/12 16 / 22 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura – osmiprvková množina {(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7), (x8, y8)} Úvod do umělé inteligence 1/12 17 / 22 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura – osmiprvková množina {(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7), (x8, y8)} solution = {(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} Úvod do umělé inteligence 1/12 17 / 22 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura – osmiprvková množina {(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7), (x8, y8)} solution = {(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} function N-Queens(n ← 8, queens ← {}) if length(queens) = n then print queens # řešení else for qx ← 1 to n do for qy ← 1 to n do if NoAttack(qx , qy , queens) then N-Queens(n, queens + {(qx , qy )}) Úvod do umělé inteligence 1/12 17 / 22 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura – osmiprvková množina {(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7), (x8, y8)} solution = {(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} function N-Queens(n ← 8, queens ← {}) if length(queens) = n then print queens # řešení else for qx ← 1 to n do for qy ← 1 to n do if NoAttack(qx , qy , queens) then N-Queens(n, queens + {(qx , qy )}) function NoAttack(qx , qy , queens) for q ∈ queens do if qx = q[1] or qy = q[2] or abs(q[1]-qx ) = abs(q[2]-qy ) then return False return True Úvod do umělé inteligence 1/12 17 / 22 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura – osmiprvková množina {(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6), (x7, y7), (x8, y8)} solution = {(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} function N-Queens(n ← 8, queens ← {}) if length(queens) = n then print queens # řešení else for qx ← 1 to n do for qy ← 1 to n do if NoAttack(qx , qy , queens) then N-Queens(n, queens + {(qx , qy )}) function NoAttack(qx , qy , queens) for q ∈ queens do if qx = q[1] or qy = q[2] or abs(q[1]-qx ) = abs(q[2]-qy ) then return False return True N-Queens(8) {(8,4), (7,2), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} {(7,2), (8,4), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} ... Úvod do umělé inteligence 1/12 17 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 = 281 474 976 710 656 při neopakování pozic 64 · 63 · 62 . . . · 57 = 178 462 987 637 760 Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 omezení stavového prostoru – každá dáma má svůj sloupec {(1, y1), (2, y2), (3, y3), (4, y4), (5, y5), (6, y6), (7, y7), (8, y8)} Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 omezení stavového prostoru – každá dáma má svůj sloupec [y1, y2, y3, y4, y5, y6, y7, y8] Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 omezení stavového prostoru – každá dáma má svůj sloupec [y1, y2, y3, y4, y5, y6, y7, y8] počet možností u řešení II = 88 = 16 777 216 Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 omezení stavového prostoru – každá dáma má svůj sloupec [y1, y2, y3, y4, y5, y6, y7, y8] počet možností u řešení II = 8 · 7 · 6 . . . · 1 = 40 320 Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 ≈ 2.8 × 1014 při neopakování pozic 64 · 63 · 62 . . . · 57 ≈ 1.8 × 1014 omezení stavového prostoru – každá dáma má svůj sloupec [y1, y2, y3, y4, y5, y6, y7, y8] počet možností u řešení II = 8 · 7 · 6 . . . · 1 = 40 320 function N-Queens(n ← 8, queensy ← []) if length(queensy ) = n then print queensy # řešení else for qy ← 1 to n do if NoAttack(qy , queensy ) then N-Queens(n, queensy + [qy ]) function NoAttack(qy , queensy ) qx = length(queensy ) + 1 for i ← 1 to length(queensy ) do if qy = queensy [i] or abs(i-qx ) = abs(queensy [i]-qy ) then return False return True Úvod do umělé inteligence 1/12 18 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III k souřadnicím x a y −→ přidáme i souřadnice diagonály u a v u = x − y v = x + y Dx = [1..8] Dy = [1..8] −→ Du = [−7..7] Dv = [2..16] Úvod do umělé inteligence 1/12 19 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III k souřadnicím x a y −→ přidáme i souřadnice diagonály u a v u = x − y v = x + y Dx = [1..8] Dy = [1..8] −→ Du = [−7..7] Dv = [2..16] Úvod do umělé inteligence 1/12 19 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III k souřadnicím x a y −→ přidáme i souřadnice diagonály u a v u = x − y v = x + y Dx = [1..8] Dy = [1..8] −→ Du = [−7..7] Dv = [2..16] Úvod do umělé inteligence 1/12 19 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {}) if length(queensy ) = 0 and length(dy ) = 0 then return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)}) if length(queensy ) = n then print queensy # řešení else for qy ∈ dy do qx ← length(queensy ) + 1 qu ← qx − qy qv ← qx + qy if qu ∈ du and qv ∈ dv then N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv }) dy = [1..8], du = {−7..7}, dv = {2..16} Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {}) if length(queensy ) = 0 and length(dy ) = 0 then return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)}) if length(queensy ) = n then print queensy # řešení else for qy ∈ dy do qx ← length(queensy ) + 1 qu ← qx − qy qv ← qx + qy if qu ∈ du and qv ∈ dv then N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv }) dy = [1..8], du = {−7..7}, dv = {2..16} Problém n dam pro n = 100: SliDo Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {}) if length(queensy ) = 0 and length(dy ) = 0 then return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)}) if length(queensy ) = n then print queensy # řešení else for qy ∈ dy do qx ← length(queensy ) + 1 qu ← qx − qy qv ← qx + qy if qu ∈ du and qv ∈ dv then N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv }) dy = [1..8], du = {−7..7}, dv = {2..16} Problém n dam pro n = 100: SliDo řešení I . . . 10400 Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {}) if length(queensy ) = 0 and length(dy ) = 0 then return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)}) if length(queensy ) = n then print queensy # řešení else for qy ∈ dy do qx ← length(queensy ) + 1 qu ← qx − qy qv ← qx + qy if qu ∈ du and qv ∈ dv then N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv }) dy = [1..8], du = {−7..7}, dv = {2..16} Problém n dam pro n = 100: SliDo řešení I . . . 10400 řešení II . . . 10158 Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Problém osmi dam III Problém osmi dam III po každém umístění dámy aktualizujeme seznamy volných pozic počet možností u řešení III = 2 057 function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {}) if length(queensy ) = 0 and length(dy ) = 0 then return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)}) if length(queensy ) = n then print queensy # řešení else for qy ∈ dy do qx ← length(queensy ) + 1 qu ← qx − qy qv ← qx + qy if qu ∈ du and qv ∈ dv then N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv }) dy = [1..8], du = {−7..7}, dv = {2..16} Problém n dam pro n = 100: SliDo řešení I . . . 10400 řešení II . . . 10158 řešení III . . . 1052 Úvod do umělé inteligence 1/12 20 / 22 Řešení problémů Další příklad – posunovačka Další příklad – posunovačka počáteční stav (např.) −→ . . . −→ cílový stav hra na čtvercové šachovnici m × m s n = m2 − 1 očíslovanými kameny příklad pro šachovnici 3 × 3, posunování osmi kamenů (8-posunovačka) stavy – pozice všech kamenů akce – “pohyb” prázdného místa Úvod do umělé inteligence 1/12 21 / 22 Řešení problémů Další příklad – posunovačka Další příklad – posunovačka počáteční stav (např.) −→ . . . −→ cílový stav hra na čtvercové šachovnici m × m s n = m2 − 1 očíslovanými kameny příklad pro šachovnici 3 × 3, posunování osmi kamenů (8-posunovačka) stavy – pozice všech kamenů akce – “pohyb” prázdného místa ☞ Optimální řešení obecné n-posunovačky je NP-úplné Počet stavů u 8-posunovačky . . . 9!/2 =181 440 u 15-posunovačky . . . 1013 u 24-posunovačky . . . 1025 Úvod do umělé inteligence 1/12 21 / 22 Řešení problémů Reálné problémy řešitelné prohledáváním Reálné problémy řešitelné prohledáváním hledání cesty z města A do města B hledání itineráře, problém obchodního cestujícího návrh VLSI čipu navigace auta, robota, . . . postup práce automatické výrobní linky návrh proteinů – 3D-sekvence aminokyselin Internetové vyhledávání informací Úvod do umělé inteligence 1/12 22 / 22