commit 83212ddd404003051c758c82d3e2408f4dd1aaa2 parent a5e01c30f7ae52f538c376c7a88c00e5462a904d Author: Alex Balgavy <alex@balgavy.eu> Date: Sun, 1 Nov 2020 00:25:49 +0100 Intelligent Systems notes Diffstat:
100 files changed, 1470 insertions(+), 5248 deletions(-)
diff --git a/content/_index.md b/content/_index.md @@ -24,7 +24,7 @@ title = "Alex's university course notes" * [Data Structures & Algorithms](dsa-notes/) * [Statistical Methods](https://thezeroalpha.github.io/stats-notes) * [Operating Systems](https://thezeroalpha.github.io/os-notes) -* [Intelligent Systems](https://thezeroalpha.github.io/is-notes) +* [Intelligent Systems](is-notes/) * [Linear Algebra](https://thezeroalpha.github.io/lin-algebra-notes) * [Software Design](https://thezeroalpha.github.io/softdesign-notes) * [Logic & Modelling](https://thezeroalpha.github.io/logic-modelling-notes) diff --git a/content/is-notes/_index.md b/content/is-notes/_index.md @@ -0,0 +1,126 @@ ++++ +title = "Intelligent Systems" ++++ +# Intelligent Systems + +core topics: + * search & heuristics + * knowledge + * adaptivity + + + +Table of contents: + * [Assessment information](assessment-info) + * [State Space Representations Intro](state-space-repr-intro) + * [State space search](state-space-search) + * [Uninformed search strategies](state-space-search#uninformed-search-strategies) + * [Breadth-first (BF) search](state-space-search#breadth-first-bf-search) + * [Depth-first (DF) search](state-space-search#depth-first-df-search) + * [Depth-limited search](state-space-search#depth-limited-search) + * [Iterative deepening search](state-space-search#iterative-deepening-search) + * [Informed search (heuristics)](state-space-search#informed-search-heuristics) + * [A Search](state-space-search#a-search) + * [A* Search](state-space-search#a-search-1) + * [Adversarial search](state-space-search#adversarial-seach) + * [Minimax](state-space-search#minimax) + * [Setup](state-space-search#setup) + * [Optimal strategies](setup#optimal-strategies) + * [Evaluation](state-space-search#evaluation) + * [Reducing problems of complexity with Minimax](state-space-search#reducing-problems-of-complexity-with-minimax) + * [Cutting off search:](state-space-search#cutting-off-search) + * [Alpha-Beta pruning (efficient Minimax)](state-space-search#alpha-beta-pruning-efficient-minimax) + * [Search with no or partial information](state-space-search#search-with-no-or-partial-information) + * [Perfect information Monte Carlo sampling (rdeep)](state-space-search#perfect-information-monte-carlo-sampling-rdeep) + * [Games with chance](state-space-search#games-with-chance) + * [Summary (Schnapsen)](state-space-search#summary-schnapsen) + * [Search direction](state-space-search#search-direction) + * [Rational agents](rational-agents) + * [Agents](rational-agents#agents) + * [Rationality](rational-agents#rationality) + * [Task environments](rational-agents#task-environments) + * [Agent types](rational-agents#agent-types) + * [Simple Reflex](rational-agents#simple-reflex) + * [Reflex & State](rational-agents#reflex-state) + * [Goal-Based](rational-agents#goal-based) + * [Learning](rational-agents#learning) + * [Logical agents](logical-agents) + * [What is logic](logical-agents#what-is-logic) + * [Syntax](logical-agents#syntax) + * [Propositional logic (PL)](logical-agents#propositional-logic-pl) + * [First order logic (FOL)](logical-agents#first-order-logic-fol) + * [Basic elements:](logical-agents#basic-elements) + * [Sentences](logical-agents#sentences) + * [Quantification](logical-agents#quantification) + * [Universal quantification](logical-agents#universal-quantification) + * [Existential quantification](logical-agents#existential-quantification) + * [Quantifier Duality](logical-agents#quantifier-duality) + * [Decidability vs undecidability](logical-agents#decidability-vs-undecidability) + * [Knowledge engineering in FOL](logical-agents#knowledge-engineering-in-fol) + * [Choice of formalisms](logical-agents#choice-of-formalisms) + * [Propositionalising FOL](logical-agents#propositionalising-fol) + * [Reduction to propositional inference](logical-agents#reduction-to-propositional-inference) + * [Universal instantiation (UI):](logical-agents#universal-instantiation-ui) + * [Existential instantiation (EI):](logical-agents#existential-instantiation-ei) + * [Applying in Schnapsen - Strategies (examples)](logical-agents#applying-in-schnapsen-strategies-examples) + * [Play Jack](logical-agents#play-jack) + * [Play cheap](logical-agents#play-cheap) + * [Play trump marriage](logical-agents#play-trump-marriage) + * [Semantics](logical-agents#semantics) + * [Interpretations & Models](logical-agents#interpretations-models) + * [Entailment](logical-agents#entailment) + * [Truth](logical-agents#truth) + * [Validity](logical-agents#validity) + * [Satisfiability](logical-agents#satisfiability) + * [Calculus (algorithms for inference)](logical-agents#calculus-algorithms-for-inference) + * [Properties of inference](logical-agents#properties-of-inference) + * [Proof methods](logical-agents#proof-methods) + * [Model checking & search](logical-agents#model-checking-search) + * [Truth Tables for inference](logical-agents#truth-tables-for-inference) + * [Effective proofs by model checking](logical-agents#effective-proofs-by-model-checking) + * [Clause Normal Form (CNF)](logical-agents#clause-normal-form-cnf) + * [DPLL algorithm](logical-agents#dpll-algorithm) + * [Heuristic search in DPLL](logical-agents#heuristic-search-in-dpll) + * [Satisfiability modulo theory](logical-agents#satisfiability-modulo-theory) + * [Rule-based reasoning](logical-agents#rule-based-reasoning) + * [Inference rules](logical-agents#inference-rules) + * [Searching for proofs](logical-agents#searching-for-proofs) + * [Forward and backward chaining](logical-agents#forward-and-backward-chaining) + * [Resolution](logical-agents#resolution) + * [Probability and Uncertainty](probability-uncertainty) + * [Vagueness: Fuzzy Set Theory](probability-uncertainty#vagueness-fuzzy-set-theory) + * [Fuzzy sets](probability-uncertainty#fuzzy-sets) + * [Fuzzy relations](probability-uncertainty#fuzzy-relations) + * [Evaluation](probability-uncertainty#evaluation) + * [Uncertainties: Probability Theory](probability-uncertainty#uncertainties-probability-theory) + * [General](probability-uncertainty#general) + * [Axioms of probability](probability-uncertainty#axioms-of-probability) + * [Joint probability distributions](probability-uncertainty#joint-probability-distributions) + * [Bayesian networks](probability-uncertainty#bayesian-networks) + * [Evaluation of probabilities](probability-uncertainty#evaluation-of-probabilities) + - [Machine Learning](machine-learning) + - [Learning problems](machine-learning#learning-problems) + - [Methodology](machine-learning#methodology) + - [Data](machine-learning#data) + - [Experimentation](machine-learning#experimentation) + - [Evaluation](machine-learning#evaluation) + - [Machine Learning Steps:](machine-learning#machine-learning-steps) + - [Choose the features](machine-learning#choose-the-features) + - [Inductive learning method](machine-learning#inductive-learning-method) + - [Classifying with naive Bayes](machine-learning#classifying-with-naive-bayes) + - [Clustering with K-nearest neighbor](machine-learning#clustering-with-k-nearest-neighbor) + - [Linear classifier](machine-learning#linear-classifier) + - [Support vector machine](machine-learning#support-vector-machine) + - [Choose the model (model search)](machine-learning#choose-the-model-model-search) + - [Regression](machine-learning#regression) + - [Gradient descent](machine-learning#gradient-descent) + - [Neural Networks](machine-learning#neural-networks) + - [Overview](machine-learning#overview) + - [Training neural networks](machine-learning#training-neural-networks) + - [Autoencoders: a NN architecture](machine-learning#autoencoders-a-nn-architecture) + - [Trying it out](machine-learning#trying-it-out) + - [The promise of depth](machine-learning#the-promise-of-depth) + * [Ethics of AI](ethics) + * [Sci-fi ethics (problems down the road)](ethics#sci-fi-ethics-problems-down-the-road) + * [Today's problems](ethics#today-s-problems) + * [Philosophy of AI](philosophy) diff --git a/content/is-notes/assessment-info.html b/content/is-notes/assessment-info.html @@ -1,149 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>assessment-info</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Assessment info"><h1 id="Assessment info">Assessment info</h1></div> -<p> -check learning goals on canvas. -</p> - -<p> -everything in working groups (this means go through the sheets again) -</p> -<ul> -<li> -informed search (DF, BF, DFID) - -<li> -uninformed search (Hill Climbing, BF, A, A*) - -<li> -adversarial search (minimax with alpha-beta) - -<li> -logical representations - -<li> -DPLL - -<li> -uncertainty representations - -<li> -Bayesian learning - -<li> -NN/Deep learning - -</ul> - -<p> -research procedure -</p> -<ul> -<li> -take at least 4 bots you implemented - -<li> -compare performance -- play against each other, in different environments - -<li> -study results: outperforming, speed - -<li> -define interesting hypotheses and research questions, use analysis to verify/falsify them - -</ul> - -<p> -scientific paper structure: -</p> -<ul> -<li> -title page with abstract - -<ul> -<li> -title and authors - -<li> -abstract of 2-3 paragraphs - -</ul> -<li> -introduction: intro to problem, solution, some results (2 pages) - -<li> -background info - -<ul> -<li> -describe game, challenge, IS framework, whatever else is needed (1-2 pages) - -</ul> -<li> -research question - -<ul> -<li> -describe approach - -<li> -what are: - -<ul> -<li> -possible outcomes of setup and contribution - -<li> -e.g. whether one method works, whether it works better than others - -</ul> -<li> -also, define "working better" - -</ul> -<li> -experimental setup (2 pages) - -<ul> -<li> -explain how experiments were set up - -<li> -what you did in terms of implementation - -<li> -compare different methods - -<li> -define metrics - -</ul> -<li> -results (2 pages) - -<ul> -<li> -describe results in overview tables - -<li> -point reader to most significant, interesting results - -</ul> -<li> -findings - -<li> -conclusions - -</ul> - -</body> -</html> diff --git a/content/is-notes/assessment-info.md b/content/is-notes/assessment-info.md @@ -0,0 +1,46 @@ ++++ +title = "Assessment info" ++++ +# Assessment info +check learning goals on canvas. + +everything in working groups (this means go through the sheets again) +* informed search (DF, BF, DFID) +* uninformed search (Hill Climbing, BF, A, A*) +* adversarial search (minimax with alpha-beta) +* logical representations +* DPLL +* uncertainty representations +* Bayesian learning +* NN/Deep learning + +research procedure + * take at least 4 bots you implemented + * compare performance -- play against each other, in different environments + * study results: outperforming, speed + * define interesting hypotheses and research questions, use analysis to verify/falsify them + +scientific paper structure: + * title page with abstract + * title and authors + * abstract of 2-3 paragraphs + * introduction: intro to problem, solution, some results (2 pages) + * background info + * describe game, challenge, IS framework, whatever else is needed (1-2 pages) + * research question + * describe approach + * what are: + * possible outcomes of setup and contribution + * e.g. whether one method works, whether it works better than others + * also, define "working better" + * experimental setup (2 pages) + * explain how experiments were set up + * what you did in terms of implementation + * compare different methods + * define metrics + * results (2 pages) + * describe results in overview tables + * point reader to most significant, interesting results + * findings + * conclusions + diff --git a/content/is-notes/img/decision-making.png b/content/is-notes/decision-making.png Binary files differ. diff --git a/content/is-notes/ethics.html b/content/is-notes/ethics.html @@ -1,106 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>ethics</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Ethics of AI"><h1 id="Ethics of AI">Ethics of AI</h1></div> -<p> -three main questions: -</p> -<ul> -<li> -how do we encode ethical behavior? - -<li> -how should we behave towards AI? - -<li> -how does the existence of AI affects our daily lives? - -</ul> -<blockquote> -"Ethics begins when elements of a moral system conflict." -</blockquote> - -<p> -Fundamental ethics: moral absolutism, you are not allowed to do something due to e.g. religion -</p> - -<p> -Pragmatic ethics: humans always have a choice, you have the freedom of choice at any point in time -</p> - -<div id="Ethics of AI-Sci-fi ethics (problems down the road)"><h2 id="Sci-fi ethics (problems down the road)">Sci-fi ethics (problems down the road)</h2></div> -<p> -Asimov's laws: -</p> -<ol> -<li> -A robot may not injure a human being or, through inaction, allow a human being to come to harm. - -<li> -A robot must obey the orders given to it by human beings except where such orders would conflict with the First Law. - -<li> -A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws. - -</ol> - -<p> -The trolley problem is a good example of an ethical dilemma, and can be extended to self-driving cars (should it kill the driver or bystanders?). -</p> - -<p> -How do we treat AI? How should we? -</p> - -<div id="Ethics of AI-Today's problems"><h2 id="Today's problems">Today's problems</h2></div> -<ul> -<li> -Autonomous weapons: weapons that decide what to do by themselves - -<ul> -<li> -what are we allowing these systems to do? - -<li> -the Dutch government said it's fine "if there's a human in the wider loop"...but this is very vague, what is the wider loop? - -</ul> -<li> -Privacy - -<ul> -<li> -big companies have a bunch of data about people - -<li> -often, people give this data for free. - -</ul> -<li> -Profiling (e.g. racial) - -<ul> -<li> -e.g. a black person was stopped while driving in an expensive car because the system thought he could only be driving the car if he stole it. - -</ul> -</ul> - -<p> -Prosecutor's fallacy: -</p> -<ul> -<li> -using probabilities incorrectly. \(P(\text{black} | \text{uses drugs}) \neq P(\text{uses drugs} | \text{black})\) - -</ul> - -</body> -</html> diff --git a/content/is-notes/ethics.md b/content/is-notes/ethics.md @@ -0,0 +1,39 @@ ++++ +title = "Ethics of AI" +template = 'page-math.html' ++++ +# Ethics of AI +three main questions: +* how do we encode ethical behavior? +* how should we behave towards AI? +* how does the existence of AI affects our daily lives? + +> "Ethics begins when elements of a moral system conflict." + +Fundamental ethics: moral absolutism, you are not allowed to do something due to e.g. religion + +Pragmatic ethics: humans always have a choice, you have the freedom of choice at any point in time + +## Sci-fi ethics (problems down the road) +Asimov's laws: +1. A robot may not injure a human being or, through inaction, allow a human being to come to harm. +2. A robot must obey the orders given to it by human beings except where such orders would conflict with the First Law. +3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws. + +The trolley problem is a good example of an ethical dilemma, and can be extended to self-driving cars (should it kill the driver or bystanders?). + +How do we treat AI? How should we? + +## Today's problems +* Autonomous weapons: weapons that decide what to do by themselves + * what are we allowing these systems to do? + * the Dutch government said it's fine "if there's a human in the wider loop"...but this is very vague, what is the wider loop? +* Privacy + * big companies have a bunch of data about people + * often, people give this data for free. +* Profiling (e.g. racial) + * e.g. a black person was stopped while driving in an expensive car because the system thought he could only be driving the car if he stole it. + +Prosecutor's fallacy: +* using probabilities incorrectly. $P(\text{black} | \text{uses drugs}) \neq P(\text{uses drugs} | \text{black})$ + diff --git a/content/is-notes/index.html b/content/is-notes/index.html @@ -1,443 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>index</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> -<nav> -<a href="http://thezeroalpha.github.io">Homepage</a> -</nav> -<div id="Intelligent Systems"><h1 id="Intelligent Systems">Intelligent Systems</h1> - <h3 class="name">Alex Balgavy</h3></div> - -<p> -core topics: -</p> -<ul> -<li> -search & heuristics - -<li> -knowledge - -<li> -adaptivity - -</ul> - -<p> -<img src="img/decision-making.png" alt="Decision making diagram" /> -</p> - -<p> -Table of contents: -</p> -<ul> -<li> -<a href="assessment-info.html">Assessment information</a> - -<li> -<a href="state-space-repr-intro.html#State Space Representations Intro">State Space Representations Intro</a> - -<li> -<a href="state-space-search.html#State space search">State space search</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Uninformed search strategies">Uninformed search strategies</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Uninformed search strategies-Breadth-first (BF) search">Breadth-first (BF) search</a> - -<li> -<a href="state-space-search.html#State space search-Uninformed search strategies-Depth-first (DF) search">Depth-first (DF) search</a> - -<li> -<a href="state-space-search.html#State space search-Uninformed search strategies-Depth-limited search">Depth-limited search</a> - -<li> -<a href="state-space-search.html#State space search-Uninformed search strategies-Iterative deepening search">Iterative deepening search</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Informed search (heuristics)">Informed search (heuristics)</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Informed search (heuristics)-A Search">A Search</a> - -<li> -<a href="state-space-search.html#State space search-Informed search (heuristics)-A* Search">A* Search</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search">Adversarial search</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Minimax">Minimax</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Minimax-Setup">Setup</a> - -<li> -<a href="state-space-search.html#State space search-Adversarial search-Minimax-Optimal strategies">Optimal strategies</a> - -<li> -<a href="state-space-search.html#State space search-Adversarial search-Minimax-Evaluation">Evaluation</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Reducing problems of complexity with Minimax">Reducing problems of complexity with Minimax</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Reducing problems of complexity with Minimax-Cutting off search:">Cutting off search:</a> - -<li> -<a href="state-space-search.html#State space search-Adversarial search-Reducing problems of complexity with Minimax-Alpha-Beta pruning (efficient Minimax)">Alpha-Beta pruning (efficient Minimax)</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Search with no or partial information">Search with no or partial information</a> - -<ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Search with no or partial information-Perfect information Monte Carlo sampling (rdeep)">Perfect information Monte Carlo sampling (rdeep)</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Adversarial search-Games with chance">Games with chance</a> - -</ul> -<li> -<a href="state-space-search.html#State space search-Summary (Schnapsen)">Summary (Schnapsen)</a> - -<li> -<a href="state-space-search.html#State space search-Search direction">Search direction</a> - -</ul> -<li> -<a href="rational-agents.html#Rational agents">Rational agents</a> - -<ul> -<li> -<a href="rational-agents.html#Rational agents-Agents">Agents</a> - -<li> -<a href="rational-agents.html#Rational agents-Rationality">Rationality</a> - -<li> -<a href="rational-agents.html#Rational agents-Task environments">Task environments</a> - -<li> -<a href="rational-agents.html#Rational agents-Agent types">Agent types</a> - -<ul> -<li> -<a href="rational-agents.html#Rational agents-Agent types-Simple Reflex">Simple Reflex</a> - -<li> -<a href="rational-agents.html#Rational agents-Agent types-Reflex & State">Reflex & State</a> - -<li> -<a href="rational-agents.html#Rational agents-Agent types-Goal-Based">Goal-Based</a> - -<li> -<a href="rational-agents.html#Rational agents-Agent types-Learning">Learning</a> - -</ul> -</ul> -<li> -<a href="logical-agents.html#Logical agents">Logical agents</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-What is logic">What is logic</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax">Syntax</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositional logic (PL)">Propositional logic (PL)</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)">First order logic (FOL)</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Basic elements:">Basic elements:</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Sentences">Sentences</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Quantification">Quantification</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Quantification-Universal quantification">Universal quantification</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Quantification-Existential quantification">Existential quantification</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Quantification-Quantifier Duality">Quantifier Duality</a> - -</ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Decidability vs undecidability">Decidability vs undecidability</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-First order logic (FOL)-Knowledge engineering in FOL">Knowledge engineering in FOL</a> - -</ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-Choice of formalisms">Choice of formalisms</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL">Propositionalising FOL</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Reduction to propositional inference">Reduction to propositional inference</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Universal instantiation (UI):">Universal instantiation (UI):</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Existential instantiation (EI):">Existential instantiation (EI):</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)">Applying in Schnapsen - Strategies (examples)</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play Jack">Play Jack</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play cheap">Play cheap</a> - -<li> -<a href="logical-agents.html#Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play trump marriage">Play trump marriage</a> - -</ul> -</ul> -</ul> -<li> -<a href="logical-agents.html#Logical agents-Semantics">Semantics</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Semantics-Interpretations & Models">Interpretations & Models</a> - -<li> -<a href="logical-agents.html#Logical agents-Semantics-Entailment">Entailment</a> - -<li> -<a href="logical-agents.html#Logical agents-Semantics-Truth">Truth</a> - -<li> -<a href="logical-agents.html#Logical agents-Semantics-Validity">Validity</a> - -<li> -<a href="logical-agents.html#Logical agents-Semantics-Satisfiability">Satisfiability</a> - -</ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)">Calculus (algorithms for inference)</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Properties of inference">Properties of inference</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods">Proof methods</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search">Model checking & search</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Truth Tables for inference">Truth Tables for inference</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Effective proofs by model checking">Effective proofs by model checking</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Clause Normal Form (CNF)">Clause Normal Form (CNF)</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-DPLL algorithm">DPLL algorithm</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-DPLL algorithm-Heuristic search in DPLL">Heuristic search in DPLL</a> - -</ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Satisfiability modulo theory">Satisfiability modulo theory</a> - -</ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning">Rule-based reasoning</a> - -<ul> -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Inference rules">Inference rules</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Searching for proofs">Searching for proofs</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Forward and backward chaining">Forward and backward chaining</a> - -<li> -<a href="logical-agents.html#Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Resolution">Resolution</a> - -</ul> -</ul> -</ul> -</ul> -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty">Probability and Uncertainty</a> - -<ul> -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Vagueness: Fuzzy Set Theory">Vagueness: Fuzzy Set Theory</a> - -<ul> -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Fuzzy sets">Fuzzy sets</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Fuzzy relations">Fuzzy relations</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Evaluation">Evaluation</a> - -</ul> -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory">Uncertainties: Probability Theory</a> - -<ul> -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory-General">General</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory-Axioms of probability">Axioms of probability</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory-Joint probability distributions">Joint probability distributions</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory-Bayesian networks">Bayesian networks</a> - -<li> -<a href="probability-uncertainty.html#Probability and Uncertainty-Uncertainties: Probability Theory-Evaluation of probabilities">Evaluation of probabilities</a> - -</ul> -</ul> -<li> -<a href="machine-learning.html#Machine Learning">Machine Learning</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Learning problems">Learning problems</a> - -<li> -<a href="machine-learning.html#Machine Learning-Methodology">Methodology</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Methodology-Data">Data</a> - -<li> -<a href="machine-learning.html#Machine Learning-Methodology-Experimentation">Experimentation</a> - -<li> -<a href="machine-learning.html#Machine Learning-Methodology-Evaluation">Evaluation</a> - -</ul> -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:">Machine Learning Steps:</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features">Choose the features</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features-Inductive learning method">Inductive learning method</a> - -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features-Classifying with naive Bayes">Classifying with naive Bayes</a> - -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features-Clustering with K-nearest neighbor">Clustering with K-nearest neighbor</a> - -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features-Linear classifier">Linear classifier</a> - -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the features-Support vector machine">Support vector machine</a> - -</ul> -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the model (model search)">Choose the model (model search)</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the model (model search)-Regression">Regression</a> - -<li> -<a href="machine-learning.html#Machine Learning-Machine Learning Steps:-Choose the model (model search)-Gradient descent">Gradient descent</a> - -</ul> -</ul> -<li> -<a href="machine-learning.html#Machine Learning-Neural Networks">Neural Networks</a> - -<ul> -<li> -<a href="machine-learning.html#Machine Learning-Neural Networks-Overview">Overview</a> - -<li> -<a href="machine-learning.html#Machine Learning-Neural Networks-Training neural networks">Training neural networks</a> - -<li> -<a href="machine-learning.html#Machine Learning-Neural Networks-Autoencoders: a NN architecture">Autoencoders: a NN architecture</a> - -<li> -<a href="machine-learning.html#Machine Learning-Neural Networks-Trying it out">Trying it out</a> - -</ul> -<li> -<a href="machine-learning.html#Machine Learning-The promise of depth">The promise of depth</a> - -</ul> -<li> -<a href="ethics.html#Ethics of AI">Ethics of AI</a> - -<ul> -<li> -<a href="ethics.html#Ethics of AI-Sci-fi ethics (problems down the road)">Sci-fi ethics (problems down the road)</a> - -<li> -<a href="ethics.html#Ethics of AI-Today's problems">Today's problems</a> - -</ul> -<li> -<a href="philosophy.html#Philosophy of AI">Philosophy of AI</a> - -</ul> - -</body> -</html> diff --git a/content/is-notes/logical-agents.html b/content/is-notes/logical-agents.html @@ -1,1045 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>logical-agents</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Logical agents"><h1 id="Logical agents">Logical agents</h1></div> - -<div id="Logical agents-What is logic"><h2 id="What is logic">What is logic</h2></div> -<p> -logic: generic method to deal with partial/imperfect/implicit information -</p> - -<p> -we need: -</p> -<ul> -<li> -syntax to write statement about rules & knowledge of the game (a language) - -<li> -semantics to say what legal expressions mean, the meaning of each sentence with respect to interpretations - -<li> -calculus for how to determine meaning for legal expressions - -</ul> - -<p> -knowledge-based/logical agents must be able to: -</p> -<ul> -<li> -represent states & actions - -<li> -incorporate new percepts, update internal representation of world - -<li> -deduce hidden properties of the world & appropriate actions - -</ul> - -<p> -online/exploratory search: go to position, evaluate all options, possibly look ahead. have to re-evaluate current position. -</p> - -<div id="Logical agents-Syntax"><h2 id="Syntax">Syntax</h2></div> -<div id="Logical agents-Syntax-Propositional logic (PL)"><h3 id="Propositional logic (PL)">Propositional logic (PL)</h3></div> -<p> -assumes world contains facts -</p> - -<p> -uses proposition symbols to state these facts. -</p> - -<p> -pros: -</p> -<ul> -<li> -declarative - -<li> -allows partial/disjunctive/negated information - -<li> -is compositional - -<li> -meaning of statements is context-independent - -</ul> - -<p> -cons: -</p> -<ul> -<li> -very limited expressive power - -</ul> - -<div id="Logical agents-Syntax-First order logic (FOL)"><h3 id="First order logic (FOL)">First order logic (FOL)</h3></div> -<p> -an extension of propositional logic. -</p> - -<p> -allows variables to range over atomic symbols in the domain. -</p> - -<p> -assumes world contains: -</p> -<ul> -<li> -objects: people, houses, colors, baseball games, etc. - -<li> -relations: red, round, prime, brother of, comes between, bigger than, etc. - -<li> -functions: father of, best friend, one more than, plus, etc. - -</ul> - -<div id="Logical agents-Syntax-First order logic (FOL)-Basic elements:"><h4 id="Basic elements:">Basic elements:</h4></div> -<ul> -<li> -Constants: KingJohn, 2, UCB, ... - -<li> -Predicates: Brother, >, ... - -<li> -Functions: Sqrt, LeftLegOf, ... - -<li> -Variables: x, y, ... - -<li> -Connectives: ∧, ∨, ¬, ⇒, ⇔ - -</ul> - -<div id="Logical agents-Syntax-First order logic (FOL)-Sentences"><h4 id="Sentences">Sentences</h4></div> -<pre> -Atomic sentence = predicate (term_1,..., term_n) - or term_1 = term_2 -Term = function(term_1,..., term_n) - or constant - or variable -</pre> - -<p> -Complex sentences are made from atomic sentences using connectives. -</p> - -<div id="Logical agents-Syntax-First order logic (FOL)-Quantification"><h4 id="Quantification">Quantification</h4></div> -<div id="Logical agents-Syntax-First order logic (FOL)-Quantification-Universal quantification"><h5 id="Universal quantification">Universal quantification</h5></div> -<p> -∀ <variables> <sentence> -</p> - -<p> -∀x P is true in a model <em>m</em> iff P is true with x being each possible object in the model -</p> - -<p> -(you can roughly translate that to conjunctions) -</p> - -<p> -typically used with ⇒ -</p> - -<p> -<span id="Logical agents-Syntax-First order logic (FOL)-Quantification-Universal quantification-CARE:"></span><strong id="CARE:">CARE:</strong> ∀x ∀y ≠ ∀y ∀x -</p> - -<div id="Logical agents-Syntax-First order logic (FOL)-Quantification-Existential quantification"><h5 id="Existential quantification">Existential quantification</h5></div> -<p> -∃ <variables> <sentence> -</p> - -<p> -∃x P is true in a model <em>m</em> iff P is true with x being some possible object in the model -</p> - -<p> -(you can roughly translate that to disjunction of instantiations of P) -</p> - -<p> -typically used with ∧ -</p> - -<p> -watch out, if you use it with ⇒, it works even if the LHS is false! -</p> - -<p> -<span id="Logical agents-Syntax-First order logic (FOL)-Quantification-Existential quantification-CARE"></span><strong id="CARE">CARE</strong>: ∃x ∃y ≠ ∃y ∃x -</p> - -<div id="Logical agents-Syntax-First order logic (FOL)-Quantification-Quantifier Duality"><h5 id="Quantifier Duality">Quantifier Duality</h5></div> -<p> -each quantifier can be expressed in terms of the other -</p> - -<p> -e.g. these are the same: -</p> -<ul> -<li> -∀x Likes(x, IceCream) -- "everyone likes ice cream" - -<li> -¬∃x ¬Likes(x, IceCream) -- "there is nobody who doesn't like ice cream" - -</ul> - -<div id="Logical agents-Syntax-First order logic (FOL)-Decidability vs undecidability"><h4 id="Decidability vs undecidability">Decidability vs undecidability</h4></div> -<p> -undecidability -</p> -<ul> -<li> -Turing machine can calculate everything that can be calculated - -<li> -halting problem: \(K := { (i,x) | \text{program i halts when run on input x})\) - -</ul> - -<p> -decidability -</p> -<ul> -<li> -validity of FOL is not decidable (but semi-decidable) - -<li> -if a theorem is logically entailed by an axiom, you can prove that it is. - -<li> -if not, you can't necessarily prove that it's not (because you can continue with your proof infinitely). - -</ul> - -<div id="Logical agents-Syntax-First order logic (FOL)-Knowledge engineering in FOL"><h4 id="Knowledge engineering in FOL">Knowledge engineering in FOL</h4></div> -<ol> -<li> -Identify the task - -<li> -Assemble relevant knowledge - -<li> -Decide on vocabulary of predicates, functions, and constants - -<li> -Encode general knowledge about the domain (terms that we want to use) - -<li> -Encode description of the specific problem instance - -<li> -Pose queries to the inference procedure and get answers - -</ol> - -<div id="Logical agents-Syntax-Choice of formalisms"><h3 id="Choice of formalisms">Choice of formalisms</h3></div> -<p> -first-order logic: represents knowledge -</p> - -<p> -propositional logic: used for reasoning ("propositionalisation") -</p> - -<p> -then use reasoner to check for entailment of propositional logic knowledge base an decision query -</p> -<ul> -<li> -Davis Putnam (DPLL) algorithm - -<li> -formulas have to be in clause normal form (CNF) - -<li> -calculus is proof by refutation: - -<ul> -<li> -DPLL determines satisfiability of a KB - -<li> -entailment of KB |= a by "refutation": - -<ul> -<li> -KB |= a if KB ∩ {~a} is unsatisfiable - -<li> -assume the opposite and prove it's impossible - -</ul> -</ul> -</ul> - -<div id="Logical agents-Syntax-Propositionalising FOL"><h3 id="Propositionalising FOL">Propositionalising FOL</h3></div> -<div id="Logical agents-Syntax-Propositionalising FOL-Reduction to propositional inference"><h4 id="Reduction to propositional inference">Reduction to propositional inference</h4></div> -<p> -every FOL KB can be propositionalised so as to preserve entailment -</p> - -<p> -if a sentence α is entailed by an FOL KB, it is entailed by a <em>finite</em> subset of the propositionalised KB -</p> - -<div id="Logical agents-Syntax-Propositionalising FOL-Universal instantiation (UI):"><h4 id="Universal instantiation (UI):">Universal instantiation (UI):</h4></div> -<p> -every instantiation of a universally quantified sentence is entailed by it. -</p> - -<p> -<img src="img/univ-instant.png" alt="Universal instantiation" /> -</p> - -<p> -example: -</p> -<pre> -∀x King(x) ∧ Greedy(x) ⇒ Evil(x) -King(John) ∧ Greedy(John) ⇒ Evil(John) -etc. -</pre> - -<div id="Logical agents-Syntax-Propositionalising FOL-Existential instantiation (EI):"><h4 id="Existential instantiation (EI):">Existential instantiation (EI):</h4></div> -<p> -<img src="img/exist-instant.png" alt="Existential instantiation" /> -</p> - -<p> -example: -</p> -<pre> -∃x Crown(x) ∧ OnHead(x,John) -Crown(C_1) ∧ OnHead(C_1, John) -</pre> - -<div id="Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)"><h4 id="Applying in Schnapsen - Strategies (examples)">Applying in Schnapsen - Strategies (examples)</h4></div> -<div id="Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play Jack"><h5 id="Play Jack">Play Jack</h5></div> - -<p> -check whether card is a jack: -</p> - -<pre> -KB |= PlayJack(x) ? -</pre> - -<p> -represent strategy: -</p> - -<pre> -∀x PlayJack(x) ⇔ Jack(x) -</pre> - -<p> -represent game information: -</p> - -<pre> -KB = {Jack(4), Jack(0), Jack(14), Jack(19)} -</pre> - -<div id="Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play cheap"><h5 id="Play cheap">Play cheap</h5></div> -<p> -only play Jacks: check whether card is cheap -</p> - -<pre> -KB |= PlayCheap(x) ? -</pre> - -<p> -represent strategy: -</p> - -<pre> -∀x PlayCheap(x) ⇔ Jack(x) ∨ Queen(x) ∨ King(x) -</pre> - -<p> -represent game information: -</p> - -<pre> -KB = {Jack(4), Jack(9), Jack(14), Jack(19), Queen(5), ...} -</pre> - -<div id="Logical agents-Syntax-Propositionalising FOL-Applying in Schnapsen - Strategies (examples)-Play trump marriage"><h5 id="Play trump marriage">Play trump marriage</h5></div> -<pre> -TrumpMarriage(x) ⇔ Q(x) & Trump(x) & ∃y: SameColor(x,y) & K(y) & MyCard(y) -SameColor(x,y) ⇔ (C(x) & C(y)) ∨ (D(x) & D(y)) ∨ (H(x) & H(y)) ∨ (S(x) & S(y)) -</pre> - -<div id="Logical agents-Semantics"><h2 id="Semantics">Semantics</h2></div> -<div id="Logical agents-Semantics-Interpretations & Models"><h3 id="Interpretations & Models">Interpretations & Models</h3></div> -<p> -interpretation: assignment of meaning to symbols of formal language -</p> - -<p> -model: interpretation that satisfies defining axioms of knowledge base -</p> - -<p> -<em>m</em> is a model of a sentence <em>α</em> if <em>α</em> holds in <em>m</em>. -</p> - -<p> -M(a) is the set of all models of a. -</p> - -<p> -each model specifies true/false for each proposition symbol (∧, ∨, ¬, ⇒, ⇐, ⇔) -</p> - -<div id="Logical agents-Semantics-Entailment"><h3 id="Entailment">Entailment</h3></div> -<p> -the knowledge base (KB) entails <em>α</em>: <em>α</em> follows from the information in the knowledge base (KB |= <em>α</em>) -</p> - -<p> -KB entails <em>α</em> iff <em>α</em> holds in all worlds where KB is true. -</p> - -<p> -a knowledge base is the rules + observations. -</p> - -<p> -a sentence is: -</p> -<ul> -<li> -entailed by KB iff α holds in all models of KB - -<li> -valid if it is true in all models - -<li> -satisfiable if it is true in some model - -<li> -unsatisfiable if it is true in no models - -</ul> - -<p> -two statements are logically equivalent if they are true in same set of models: -</p> - -<p> -α ≡ β iff α |= β and β |= α -</p> - -<div id="Logical agents-Semantics-Truth"><h3 id="Truth">Truth</h3></div> -<p> -sentences are true with respect to model and interpretation. -</p> - -<p> -model contains objects and relations among them -</p> - -<p> -interpretation specifies referents for: -</p> -<ul> -<li> -constant symbols -- objects - -<li> -predicate symbols -- relations - -<li> -function symbols -- functional relations - -</ul> - -<p> -an atomic sentence \(predicate(term_1, ..., term_n)\) is true -iff the objects referred to by \(term_1,..., term_n\) -are in the relation referred to by \(predicate\) -</p> - -<div id="Logical agents-Semantics-Validity"><h3 id="Validity">Validity</h3></div> -<p> -valid if it is true in all models. -</p> - -<p> -e.g. True, A ∨ ¬A, A ⇒ A, (A ∧ (A e.g. True, A ∨ ⇒ B)) ⇒ B) -</p> - -<div id="Logical agents-Semantics-Satisfiability"><h3 id="Satisfiability">Satisfiability</h3></div> -<ul> -<li> -satisfiable if it is true in <em>some</em> model - -<li> -unsatisfiable if it is true in <em>no</em> models - -</ul> - -<div id="Logical agents-Calculus (algorithms for inference)"><h2 id="Calculus (algorithms for inference)">Calculus (algorithms for inference)</h2></div> -<div id="Logical agents-Calculus (algorithms for inference)-Properties of inference"><h3 id="Properties of inference">Properties of inference</h3></div> -<p> -sound: if an algorithm \(|-\) only derives entailed sentences. - i.e. if KB \(|-\) α also KB |= α -</p> - -<p> -complete: if an algorithm derives any sentence that is entailed. - i.e. KB |= α implies KB |- α -</p> - -<p> -a calculus terminates if it finds entailed sentences in finite time. -</p> - -<p> -a logic is <em>decidable</em> if there is <em>sound and complete</em> calculus that <em>terminates</em>. -</p> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods"><h3 id="Proof methods">Proof methods</h3></div> -<ol> -<li> -Model checking and search - -<ul> -<li> -truth table enumeration (exponential in n) - -<li> -improved backtracking (DPLL) - -<li> -heuristics for choosing right order - -</ul> -<li> -application of inference rules - -<ul> -<li> -sound generation of new sentences from old - -<li> -proof = sequence of rule applications (actions) - -</ul> -</ol> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search"><h4 id="Model checking & search">Model checking & search</h4></div> -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Truth Tables for inference"><h5 id="Truth Tables for inference">Truth Tables for inference</h5></div> -<p> -enumerate interpretations and check that where KB is true, α is true. -</p> - -<table> -<tr> -<th> -\(fact_1\) -</th> -<th> -\(fact_2\) -</th> -<th> -\(fact_3\) -</th> -<th> -\(KB\) -</th> -<th> -\(α\) -</th> -</tr> -<tr> -<td> -false -</td> -<td> -false -</td> -<td> -false -</td> -<td> -false -</td> -<td> -true -</td> -</tr> -<tr> -<td> -false -</td> -<td> -false -</td> -<td> -false -</td> -<td> -false -</td> -<td> -true -</td> -</tr> -<tr> -<td> -false -</td> -<td> -true -</td> -<td> -false -</td> -<td> -<em>true</em> -</td> -<td> -<em>true</em> -</td> -</tr> -</table> - -<p> -algorithm: -</p> - -<pre> -for (m in truth assignments) { - if (m makes F true) return "satisfiable" -} -return "unsatisfiable" -</pre> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Effective proofs by model checking"><h5 id="Effective proofs by model checking">Effective proofs by model checking</h5></div> - -<p> -Clever search (depth first, redundancy, heuristics) -</p> - -<p> -Two families of efficient algorithms for propositional inference based on model checking -</p> -<ul> -<li> -complete backtracking search algorithms -- DPLL (Davis, Putnam, Logemann, Loveland) - -<li> -incomplete local search algorithm (WalkSAT algorithm) - -</ul> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Clause Normal Form (CNF)"><h5 id="Clause Normal Form (CNF)">Clause Normal Form (CNF)</h5></div> - -<p> -memo technique: the C in CNF for <em>conjunction</em> normal form -</p> - -<p> -A PL formula is in CNF if it is a conjunction of disjunctions of literals. -</p> -<ul> -<li> -e.g.: {{a,b}, {~a, c}, {~b, c}} - -<li> -equivalent to (a ∨ b) ∧ (~ a ∨ c) ∧ (~ b ∨ c) - -</ul> - -<p> -calculating CNF: -</p> -<ol> -<li> -Remove implications: - -<ul> -<li> -(p ⇔ q) to ((p ⇒ q) ∧ (q ⇒ p)) - -<li> -(p → q) to (¬ p ∨ q) - -</ul> -<li> -Move negations inward: - -<ul> -<li> -¬ (p ∨ q) to (¬ p ∧ ¬ q) - -<li> -¬ (p ∧ q) to (¬ p ∨ ¬ q) - -</ul> -<li> -Move conjunctions outward: - -<ul> -<li> -(r ∨ (p ∧ q)) to ((r ∨ p) ∧ (r ∨ q)) - -</ul> -<li> -Split up conjunctive clauses: - -<ul> -<li> -( (p1 ∨ p2) ∧ (q1 ∨ q2) ) to (p1 ∨ p2), (q1 ∨ q2) - -</ul> -</ol> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-DPLL algorithm"><h5 id="DPLL algorithm">DPLL algorithm</h5></div> - -<p> -when you have CNF, you can run the DPLL algorithm. determines if propositional logic sentence in CNF is satisfiable. -</p> - -<p> -returns true if F is satisfiable, false otherwise. -</p> - -<p> -basically assign values until contradiction, then backtrack. -</p> - -<p> -Improving DPLL: -</p> -<ul> -<li> -if a literal in a disjunction clause is true, the clause is true - -<li> -if a literal in a disjunction clause is false, the literal can be removed - -<li> -if a clause is empty, it is false - -<li> -a unit literal has to be true - -<li> -a pure literal (only appears non-negated) has to be true - -</ul> - -<p> -the algorithm: -</p> - -<pre> -dpll (F, literal) { - remove clauses containing literal - shorten clauses containing ¬literal - if (F contains no clauses) - return true - if (F contains empty clause) - return false - if (F contains a unit or pure literal) - return dpll(F, literal) - - choose P in F - if (dpll(F, ¬P)) - return true - - return dpll(F, P) -} -</pre> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-DPLL algorithm-Heuristic search in DPLL"><h6 id="Heuristic search in DPLL">Heuristic search in DPLL</h6></div> - -<p> -used in DPLL to select proposition for branching -</p> - -<p> -idea: identify most constrained variable, likely to create many unit clauses -</p> - -<p> -MOM's heuristic: most occurrences in clauses of minimum length -</p> - -<p> -why is it better than truth table enumeration? -</p> -<ul> -<li> -early termination: clause is true if any literal is true. sentence is false if any clause is false. - -<li> -pure symbol heuristic: always appears with the same sign in all clauses, has to be true - -<li> -unit clause heuristic: only one literal in the clause, so it must be true - -</ul> - -<p> -proving entailment KB |= a by refutation: -</p> -<ol> -<li> -translate KB into CNF to get cnf(KB) - -<li> -translate ~a into CNF to get cnf(~a) - -<li> -add cnf(~a) to cnf(KB) - -<li> -apply DPLL until either satisfiable (model is found) or unsatisfiable (search exhausted) - -<li> -if satisfiable, not entailed. otherwise, entailed. - -</ol> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Model checking & search-Satisfiability modulo theory"><h5 id="Satisfiability modulo theory">Satisfiability modulo theory</h5></div> - -<p> -Boolean satisfiability (SAT): is there an assignment to the \(p_1, p_2, ..., p_n\) variables such that \(\phi\) evaluates to 1? -</p> - -<p> -<img src="img/boolean-satisfiability.png" alt="Boolean satisfiability diagram" /> -</p> - -<p> -SAT vs SMT: -</p> -<ul> -<li> -SMT (satisfiability modulo theories) extend SAT solving by adding extensions. - -<li> -SMT solver can solve SAT problem, but not vice-versa. - -<li> -SMT is used in analog circuit verification, RTL, verification, and card games. - -</ul> - -<p> -SMT theories: -</p> -<ul> -<li> -real or integer arithmetic - -<li> -equality and uninterpreted functions - -<li> -bit vectors and arrays - -<li> -properties: - -<ul> -<li> -decidable: an effective procedure exists to determine if formula is member of theory T - -<li> -often quantifier-free - -</ul> -<li> -core theory: - -<ul> -<li> -type boolean - -<li> -constants {TRUE, FALSE} - -<li> -functions {AND, OR, XOR, =>} - -</ul> -<li> -integer theory: - -<ul> -<li> -type int - -<li> -all numerals are int constants - -<li> -functions {+, -, x, mod, div, abs} - -</ul> -<li> -reals theory: - -<ul> -<li> -type real - -<li> -functions {+, -, x, /, <, >} - -<li> - - -</ul> -</ul> -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning"><h4 id="Rule-based reasoning">Rule-based reasoning</h4></div> -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Inference rules"><h5 id="Inference rules">Inference rules</h5></div> -<p> -inference rule: logical form consisting of function taking premises, analyzing their syntax, and returning one or more conclusions -</p> - -<p> -Modens Ponens: \(\frac{\alpha\implies\beta,\;\alpha}{\beta}\) -</p> - -<p> -And-elimination: \(\frac{\alpha\land\beta}{\alpha}\) -</p> - -<p> -logical equivalences used as rules: \(\frac{\alpha\iff\beta}{(\alpha\implies\beta)\land(\beta\implies\alpha)}\) -</p> - -<p> -all logical equivalence rewriting rules: -</p> - -<p> -<img src="img/logical-rewriting-rules.png" alt="Rewriting rules for logic" /> -</p> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Searching for proofs"><h5 id="Searching for proofs">Searching for proofs</h5></div> -<p> -Finding proofs is like finding solutions to search problems. -</p> - -<p> -monotonicity: set of entailed sentences can only increase as info is added to the knowledge base. -</p> -<ul> -<li> -for any sentence α and β, - -<li> -if KB |= α, then KB ∧ β |= α - -</ul> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Forward and backward chaining"><h5 id="Forward and backward chaining">Forward and backward chaining</h5></div> -<p> -FC is data-driven, automatic, unconscious: -</p> -<ul> -<li> -derive all facts entailed by the KB - -<li> -may do lots of work irrelevant to the goal - -</ul> - -<p> -BC is goal-driven, appropriate for problem-solving -</p> -<ul> -<li> -specific fact entailed by the KB - -<li> -complexity of BC can be much less than linear in size of KB - -</ul> - -<div id="Logical agents-Calculus (algorithms for inference)-Proof methods-Rule-based reasoning-Resolution"><h5 id="Resolution">Resolution</h5></div> -<p> -a rule is sound if its conclusion is evaluated to true whenever the premise is evaluated to true. -</p> - -<p> -can be shown to be sound using truth table: -</p> - -<p> -<img src="img/sound-rules-inference.png" alt="Sound rules for inference" /> -</p> - -<p> -properties resolution: -</p> -<ul> -<li> -resolution rule is sound - -<li> -resolution rule is complete (on its own) for formulas in CNF - -<li> -resolution can only decide satisfiability - -</ul> - -<p> -algorithm (again proof by refutation): -</p> -<ol> -<li> -Convert KB ∧ ¬ α into CNF - -<li> -Apply resolution rule to resulting clauses - -<li> -Continue until: - -<ol> -<li> -no new clauses can be added, hence α does not entail β - -<li> -two clauses resolve to entail empty clause, hence α entails β - -</ol> -</ol> - -</body> -</html> diff --git a/content/is-notes/img/boolean-satisfiability.png b/content/is-notes/logical-agents/boolean-satisfiability.png Binary files differ. diff --git a/content/is-notes/img/exist-instant.png b/content/is-notes/logical-agents/exist-instant.png Binary files differ. diff --git a/content/is-notes/logical-agents/index.md b/content/is-notes/logical-agents/index.md @@ -0,0 +1,456 @@ ++++ +title = "Logical agents" +template = 'page-math.html' ++++ +# Logical agents + +## What is logic +logic: generic method to deal with partial/imperfect/implicit information + +we need: +* syntax to write statement about rules & knowledge of the game (a language) +* semantics to say what legal expressions mean, the meaning of each sentence with respect to interpretations +* calculus for how to determine meaning for legal expressions + +knowledge-based/logical agents must be able to: +* represent states & actions +* incorporate new percepts, update internal representation of world +* deduce hidden properties of the world & appropriate actions + +online/exploratory search: go to position, evaluate all options, possibly look ahead. have to re-evaluate current position. + +## Syntax +### Propositional logic (PL) +assumes world contains facts + +uses proposition symbols to state these facts. + +pros: +* declarative +* allows partial/disjunctive/negated information +* is compositional +* meaning of statements is context-independent + +cons: +* very limited expressive power + +### First order logic (FOL) +an extension of propositional logic. + +allows variables to range over atomic symbols in the domain. + +assumes world contains: +* objects: people, houses, colors, baseball games, etc. +* relations: red, round, prime, brother of, comes between, bigger than, etc. +* functions: father of, best friend, one more than, plus, etc. + +#### Basic elements: +- Constants: KingJohn, 2, UCB, ... +- Predicates: Brother, >, ... +- Functions: Sqrt, LeftLegOf, ... +- Variables: x, y, ... +- Connectives: ∧, ∨, ¬, ⇒, ⇔ + +#### Sentences +``` +Atomic sentence = predicate (term_1,..., term_n) + or term_1 = term_2 +Term = function(term_1,..., term_n) + or constant + or variable +``` + +Complex sentences are made from atomic sentences using connectives. + +#### Quantification +##### Universal quantification +∀ <variables> <sentence> + +∀x P is true in a model _m_ iff P is true with x being each possible object in the model + +(you can roughly translate that to conjunctions) + +typically used with ⇒ + +*CARE:* ∀x ∀y ≠ ∀y ∀x + +##### Existential quantification +∃ <variables> <sentence> + +∃x P is true in a model _m_ iff P is true with x being some possible object in the model + +(you can roughly translate that to disjunction of instantiations of P) + +typically used with ∧ + +watch out, if you use it with ⇒, it works even if the LHS is false! + +*CARE*: ∃x ∃y ≠ ∃y ∃x + +##### Quantifier Duality +each quantifier can be expressed in terms of the other + +e.g. these are the same: +* ∀x Likes(x, IceCream) -- "everyone likes ice cream" +* ¬∃x ¬Likes(x, IceCream) -- "there is nobody who doesn't like ice cream" + +#### Decidability vs undecidability +undecidability +* Turing machine can calculate everything that can be calculated +* halting problem: $K := { (i,x) | \text{program i halts when run on input x})$ + +decidability +* validity of FOL is not decidable (but semi-decidable) +* if a theorem is logically entailed by an axiom, you can prove that it is. +* if not, you can't necessarily prove that it's not (because you can continue with your proof infinitely). + +#### Knowledge engineering in FOL +1. Identify the task +2. Assemble relevant knowledge +3. Decide on vocabulary of predicates, functions, and constants +4. Encode general knowledge about the domain (terms that we want to use) +5. Encode description of the specific problem instance +6. Pose queries to the inference procedure and get answers + +### Choice of formalisms +first-order logic: represents knowledge + +propositional logic: used for reasoning ("propositionalisation") + +then use reasoner to check for entailment of propositional logic knowledge base an decision query +* Davis Putnam (DPLL) algorithm +* formulas have to be in clause normal form (CNF) +* calculus is proof by refutation: +* DPLL determines satisfiability of a KB +* entailment of KB |= a by "refutation": + * KB |= a if KB ∩ {~a} is unsatisfiable + * assume the opposite and prove it's impossible + +### Propositionalising FOL +#### Reduction to propositional inference +every FOL KB can be propositionalised so as to preserve entailment + +if a sentence α is entailed by an FOL KB, it is entailed by a _finite_ subset of the propositionalised KB + +#### Universal instantiation (UI): +every instantiation of a universally quantified sentence is entailed by it. + + + +example: +``` +∀x King(x) ∧ Greedy(x) ⇒ Evil(x) +King(John) ∧ Greedy(John) ⇒ Evil(John) +etc. +``` + +#### Existential instantiation (EI): + + +example: +``` +∃x Crown(x) ∧ OnHead(x,John) +Crown(C_1) ∧ OnHead(C_1, John) +``` + +#### Applying in Schnapsen - Strategies (examples) +##### Play Jack + +check whether card is a jack: + +``` +KB |= PlayJack(x) ? +``` + +represent strategy: + +``` +∀x PlayJack(x) ⇔ Jack(x) +``` + +represent game information: + +``` +KB = {Jack(4), Jack(0), Jack(14), Jack(19)} +``` + +##### Play cheap +only play Jacks: check whether card is cheap + +``` +KB |= PlayCheap(x) ? +``` + +represent strategy: + +``` +∀x PlayCheap(x) ⇔ Jack(x) ∨ Queen(x) ∨ King(x) +``` + +represent game information: + +``` +KB = {Jack(4), Jack(9), Jack(14), Jack(19), Queen(5), ...} +``` + +##### Play trump marriage +``` +TrumpMarriage(x) ⇔ Q(x) & Trump(x) & ∃y: SameColor(x,y) & K(y) & MyCard(y) +SameColor(x,y) ⇔ (C(x) & C(y)) ∨ (D(x) & D(y)) ∨ (H(x) & H(y)) ∨ (S(x) & S(y)) +``` + +## Semantics +### Interpretations & Models +interpretation: assignment of meaning to symbols of formal language + +model: interpretation that satisfies defining axioms of knowledge base + +_m_ is a model of a sentence _α_ if _α_ holds in _m_. + +M(a) is the set of all models of a. + +each model specifies true/false for each proposition symbol (∧, ∨, ¬, ⇒, ⇐, ⇔) + +### Entailment +the knowledge base (KB) entails _α_: _α_ follows from the information in the knowledge base (KB |= _α_) + +KB entails _α_ iff _α_ holds in all worlds where KB is true. + +a knowledge base is the rules + observations. + +a sentence is: +* entailed by KB iff α holds in all models of KB +* valid if it is true in all models +* satisfiable if it is true in some model +* unsatisfiable if it is true in no models + +two statements are logically equivalent if they are true in same set of models: + +α ≡ β iff α |= β and β |= α + +### Truth +sentences are true with respect to model and interpretation. + +model contains objects and relations among them + +interpretation specifies referents for: +* constant symbols -- objects +* predicate symbols -- relations +* function symbols -- functional relations + +an atomic sentence $predicate(term_1, ..., term_n)$ is true +iff the objects referred to by $term_1,..., term_n$ +are in the relation referred to by $predicate$ + +### Validity +valid if it is true in all models. + +e.g. True, A ∨ ¬A, A ⇒ A, (A ∧ (A e.g. True, A ∨ ⇒ B)) ⇒ B) + +### Satisfiability +- satisfiable if it is true in _some_ model +- unsatisfiable if it is true in _no_ models + +## Calculus (algorithms for inference) +### Properties of inference +sound: if an algorithm $|-$ only derives entailed sentences. + i.e. if KB $|-$ α also KB |= α + +complete: if an algorithm derives any sentence that is entailed. + i.e. KB |= α implies KB |- α + +a calculus terminates if it finds entailed sentences in finite time. + +a logic is _decidable_ if there is _sound and complete_ calculus that _terminates_. + +### Proof methods +1. Model checking and search + * truth table enumeration (exponential in n) + * improved backtracking (DPLL) + * heuristics for choosing right order +2. application of inference rules + * sound generation of new sentences from old + * proof = sequence of rule applications (actions) + +#### Model checking & search +##### Truth Tables for inference +enumerate interpretations and check that where KB is true, α is true. + +| $fact_1$ | $fact_2$ | $fact_3$ | $KB$ | $α$ | +|----------|----------|----------|--------|--------| +| false | false | false | false | true | +| false | false | false | false | true | +| false | true | false | _true_ | _true_ | + +algorithm: + +``` +for (m in truth assignments) { + if (m makes F true) return "satisfiable" +} +return "unsatisfiable" +``` + +##### Effective proofs by model checking + +Clever search (depth first, redundancy, heuristics) + +Two families of efficient algorithms for propositional inference based on model checking +* complete backtracking search algorithms -- DPLL (Davis, Putnam, Logemann, Loveland) +* incomplete local search algorithm (WalkSAT algorithm) + +##### Clause Normal Form (CNF) + +memo technique: the C in CNF for _conjunction_ normal form + +A PL formula is in CNF if it is a conjunction of disjunctions of literals. + * e.g.: {{a,b}, {~a, c}, {~b, c}} + * equivalent to (a ∨ b) ∧ (~ a ∨ c) ∧ (~ b ∨ c) + +calculating CNF: +1. Remove implications: + * (p ⇔ q) to ((p ⇒ q) ∧ (q ⇒ p)) + * (p → q) to (¬ p ∨ q) +2. Move negations inward: + * ¬ (p ∨ q) to (¬ p ∧ ¬ q) + * ¬ (p ∧ q) to (¬ p ∨ ¬ q) +3. Move conjunctions outward: + * (r ∨ (p ∧ q)) to ((r ∨ p) ∧ (r ∨ q)) +4. Split up conjunctive clauses: + * ( (p1 ∨ p2) ∧ (q1 ∨ q2) ) to (p1 ∨ p2), (q1 ∨ q2) + +##### DPLL algorithm + +when you have CNF, you can run the DPLL algorithm. determines if propositional logic sentence in CNF is satisfiable. + +returns true if F is satisfiable, false otherwise. + +basically assign values until contradiction, then backtrack. + +Improving DPLL: +* if a literal in a disjunction clause is true, the clause is true +* if a literal in a disjunction clause is false, the literal can be removed +* if a clause is empty, it is false +* a unit literal has to be true +* a pure literal (only appears non-negated) has to be true + +the algorithm: + +``` +dpll (F, literal) { + remove clauses containing literal + shorten clauses containing ¬literal + if (F contains no clauses) + return true + if (F contains empty clause) + return false + if (F contains a unit or pure literal) + return dpll(F, literal) + + choose P in F + if (dpll(F, ¬P)) + return true + + return dpll(F, P) +} +``` + +###### Heuristic search in DPLL + +used in DPLL to select proposition for branching + +idea: identify most constrained variable, likely to create many unit clauses + +MOM's heuristic: most occurrences in clauses of minimum length + +why is it better than truth table enumeration? + * early termination: clause is true if any literal is true. sentence is false if any clause is false. + * pure symbol heuristic: always appears with the same sign in all clauses, has to be true + * unit clause heuristic: only one literal in the clause, so it must be true + +proving entailment KB |= a by refutation: + 1. translate KB into CNF to get cnf(KB) + 2. translate ~a into CNF to get cnf(~a) + 3. add cnf(~a) to cnf(KB) + 4. apply DPLL until either satisfiable (model is found) or unsatisfiable (search exhausted) + 5. if satisfiable, not entailed. otherwise, entailed. + +##### Satisfiability modulo theory + +Boolean satisfiability (SAT): is there an assignment to the $p_1, p_2, ..., p_n$ variables such that $\phi$ evaluates to 1? + + + +SAT vs SMT: +* SMT (satisfiability modulo theories) extend SAT solving by adding extensions. +* SMT solver can solve SAT problem, but not vice-versa. +* SMT is used in analog circuit verification, RTL, verification, and card games. + +SMT theories: +* real or integer arithmetic +* equality and uninterpreted functions +* bit vectors and arrays +* properties: + * decidable: an effective procedure exists to determine if formula is member of theory T + * often quantifier-free +* core theory: + * type boolean + * constants {TRUE, FALSE} + * functions {AND, OR, XOR, =>} +* integer theory: + * type int + * all numerals are int constants + * functions {+, -, x, mod, div, abs} +* reals theory: + * type real + * functions {+, -, x, /, <, >} + +#### Rule-based reasoning +##### Inference rules +inference rule: logical form consisting of function taking premises, analyzing their syntax, and returning one or more conclusions + +Modens Ponens: $\frac{\alpha\implies\beta,\;\alpha}{\beta}$ + +And-elimination: $\frac{\alpha\land\beta}{\alpha}$ + +logical equivalences used as rules: $\frac{\alpha\iff\beta}{(\alpha\implies\beta)\land(\beta\implies\alpha)}$ + +all logical equivalence rewriting rules: + + + +##### Searching for proofs +Finding proofs is like finding solutions to search problems. + +monotonicity: set of entailed sentences can only increase as info is added to the knowledge base. +* for any sentence α and β, +* if KB |= α, then KB ∧ β |= α + +##### Forward and backward chaining +FC is data-driven, automatic, unconscious: +* derive all facts entailed by the KB +* may do lots of work irrelevant to the goal + +BC is goal-driven, appropriate for problem-solving +* specific fact entailed by the KB +* complexity of BC can be much less than linear in size of KB + +##### Resolution +a rule is sound if its conclusion is evaluated to true whenever the premise is evaluated to true. + +can be shown to be sound using truth table: + + + +properties resolution: +* resolution rule is sound +* resolution rule is complete (on its own) for formulas in CNF +* resolution can only decide satisfiability + +algorithm (again proof by refutation): +1. Convert KB ∧ ¬ α into CNF +2. Apply resolution rule to resulting clauses +3. Continue until: + a) no new clauses can be added, hence α does not entail β + b) two clauses resolve to entail empty clause, hence α entails β + diff --git a/content/is-notes/img/logical-rewriting-rules.png b/content/is-notes/logical-agents/logical-rewriting-rules.png Binary files differ. diff --git a/content/is-notes/img/sound-rules-inference.png b/content/is-notes/logical-agents/sound-rules-inference.png Binary files differ. diff --git a/content/is-notes/img/univ-instant.png b/content/is-notes/logical-agents/univ-instant.png Binary files differ. diff --git a/content/is-notes/machine-learning.html b/content/is-notes/machine-learning.html @@ -1,709 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>machine-learning</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Machine Learning"><h1 id="Machine Learning">Machine Learning</h1></div> - -<p> -design of a learning element is affected by: -</p> -<ul> -<li> -which components of performance element are to be learned - -<li> -what feedback is available to learn these components - -<li> -what representation is used for the components - -</ul> - -<p> -offline learning: learn based on some data, then apply results to situation -</p> - -<p> -feedback types (get input, make decision, learn based on feedback): -</p> -<ul> -<li> -supervised learning: correct answers for each example. - -<ul> -<li> -only positive examples - -<li> -positive and negative examples - -</ul> -<li> -unsupervised learning: no correct answers given - -<li> -semi-supervised learning: learn which questions to ask (active learning) - -<li> -reinforcement learning: occasional rewards - -</ul> - -<p> -<img src="img/neurons-vs-nn.png" /> -</p> - -<div id="Machine Learning-Learning problems"><h2 id="Learning problems">Learning problems</h2></div> - -<p> -Classification -</p> -<ul> -<li> -use: from data to discrete classes. - -<li> -examples: handwriting recognition, spam filtering, facial recognition. - -</ul> - -<p> -Regression -</p> -<ul> -<li> -use: predicting a numeric value - -<li> -examples: stock market, weather predictions - -</ul> - -<p> -Ranking -</p> -<ul> -<li> -use: comparing items - -<li> -examples: web search - -</ul> - -<p> -Collaborative filtering -</p> -<ul> -<li> -use: take some else's information, based on that, give prediction - -<li> -examples: recommendation systems (books, movies/shows) - -</ul> - -<p> -Clustering -</p> -<ul> -<li> -use: discovering structure/patterns in data - -<li> -examples: clustering images - -</ul> - -<div id="Machine Learning-Methodology"><h2 id="Methodology">Methodology</h2></div> -<div id="Machine Learning-Methodology-Data"><h3 id="Data">Data</h3></div> -<p> -labeled instances (like spam, not spam) -</p> -<ul> -<li> -training set - -<li> -held out set (e.g. for validation) - -<li> -test set (don't even look at this until you want to test your model) - -</ul> - -<p> -randomly allocate to data sets. -</p> - -<p> -features: attribute-value pairs characterizing each x -</p> - -<div id="Machine Learning-Methodology-Experimentation"><h3 id="Experimentation">Experimentation</h3></div> -<p> -experimentation cycle: -</p> -<ol> -<li> -select hypothesis, tune hyperparameters on held-out/validation set - -<li> -compute accuracy of test set (never "peek" at test set itself) - -</ol> - -<div id="Machine Learning-Methodology-Evaluation"><h3 id="Evaluation">Evaluation</h3></div> -<p> -accuracy -- fraction of instances predicted correctly -</p> - -<p> -Cross validation: -</p> - -<p> -<img src="img/cross-validation.png" alt="Cross validation diagram" /> -</p> - -<p> -create a confusion matrix (<span class="todo">TODO</span>: there's a diagram for this but not in the old slides) -</p> - -<div id="Machine Learning-Machine Learning Steps:"><h2 id="Machine Learning Steps:">Machine Learning Steps:</h2></div> -<ol> -<li> -choose the features - -<li> -choose the model class - -<li> -choose a search method - -</ol> - -<div id="Machine Learning-Machine Learning Steps:-Choose the features"><h3 id="Choose the features">Choose the features</h3></div> -<p> -create a feature space: features on x-y axes, points are individual data, classification would be a color scheme. -</p> - -<p> -<img src="img/feature-space.png" alt="Feature space graph" /> -</p> - - -<div id="Machine Learning-Machine Learning Steps:-Choose the features-Inductive learning method"><h4 id="Inductive learning method">Inductive learning method</h4></div> -<ul> -<li> -construct/adjust h to agree with f (function predicting value) on training set - -<li> -h is consistent if it agrees with f on all examples - -<li> -for example, curve fitting: - -</ul> -<blockquote> -<img src="img/curve-fitting.png" alt="Curve fitting graph" /> -</blockquote> - -<p> -Occam's razor: "one should not increase, beyond what is necessary, the number of entities required to explain anything" -basically, choose the simplest option. -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the features-Classifying with naive Bayes"><h4 id="Classifying with naive Bayes">Classifying with naive Bayes</h4></div> - -<p> -Binary classification -</p> -<ul> -<li> -input: email - -<li> -output: spam, not spam - -<li> -setup: - -<ul> -<li> -get large collection of example emails, labeled "spam/not spam" - -<li> -someone has to hand-label that - -<li> -want to learn to predict label for new emails in future - -</ul> -<li> -features: attributes used to make label decision - -<ul> -<li> -words, text patterns (e.g. caps), non-text - -</ul> -</ul> - -<p> -calculation for Bayesian classifier: \(P(C|F_1,...,F_n)\) -</p> - -<p> -using Bayes' theorem: -</p> - -<p> -\(P(C|F_1,...F_n)=\frac{P(C)P(F_1,...,F_n|C)}{P(F_1,...,F_n)}\) -</p> - -<p> -rewrite the numerator of the equation: -</p> - -<p> -\(P(C)P(F_1,...,F_n |C) = P(C)P(F_1 | C)P(F_2 | C, F_1)P(F_3|C, F_1, F_2)P(F_4,...,F_n | C, F_1, F_2, F_3)\) -</p> - -<p> -that uses the chaining rule. but it's too computationally expensive. -so naively assume conditional independence: -</p> - -<p> -\(P(F_i | C, F_j) = P(F_i | C)\) -</p> - -<p> -This simplifies the formula to: -</p> - -<p> -\(P(C)P(F_1,...,F_n | C) = P(C) PI(0 to n) P(F_i | C)\) -</p> - -<p> -<img src="img/bayes-calculation.png" /> -</p> - -<p> -Laplace smoothing helps with really small probabilities. -Naive Bayes often works. sometimes performs well even if the assumptions are badly violated. -classification is about predicting correct class label, <em>not</em> about accurately estimating probabilities -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the features-Clustering with K-nearest neighbor"><h4 id="Clustering with K-nearest neighbor">Clustering with K-nearest neighbor</h4></div> -<p> -k nearest neighbor classification: find k most similar case, copy majority label -</p> - -<p> -e.g. to classify unlabeled document, find most similar document and copy label: -</p> - -<p> -<img src="img/knn.png" alt="K-nearest neighbor example" /> -</p> - -<p> -the <em>k</em> helps get rid of noise which would lead to misclassification -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the features-Linear classifier"><h4 id="Linear classifier">Linear classifier</h4></div> -<p> -linear classifier: come up with a line that divides feature space, use that for prediction. -</p> - -<p> -works for stuff like \(x \lor y\), but not if we want \(x \oplus y\) or other things that are not linearly separable. -</p> - -<p> -you can build a design matrix of all the different features you want to include. here's an example with 5 different features *age, height, age², age × height, height²) that classifies a person as male/female: -</p> - -<p> -<img src="img/design-matrix.png" alt="Design matrix" /> -</p> - -<p> -if you go to more dimensions (so more features in a design matrix), you need hyperplanes. -</p> - -<p> -hyperplanes sound fancy af but it's just a line in some higher dimension. for example, this is how you would use a hyperplane in the third dimension to separate points: -</p> - -<p> -<img src="img/3d-hyperplane.png" alt="3D hyperplane example" /> -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the features-Support vector machine"><h4 id="Support vector machine">Support vector machine</h4></div> -<p> -k(x,y): "distance" function between instances x and y -</p> - -<p> -SVMs create a linear separating hyperplane -</p> - -<p> -they can embed that hyperplane into a higher dimensional domain using the kernel trick -- so long as <em>k</em> is a kernel, you don't have to explicitly compute the design matrix (that drastically reduces the computation) -</p> - -<p> -try to achieve a good margin -- a large separation from the line for both classes (so reduce the blur between two classes, make a clear distinction). -</p> - -<p> -watch out for over-fitting -- you might end up with the model being trained extremely specifically to your data. -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the model (model search)"><h3 id="Choose the model (model search)">Choose the model (model search)</h3></div> - -<p> -so we have a lot of ways to put a line on a graph. but how do you choose the right one? -</p> - -<div id="Machine Learning-Machine Learning Steps:-Choose the model (model search)-Regression"><h4 id="Regression">Regression</h4></div> -<p> -train a learner to produce a model (the model is the line/hyperplane). then you give the model a new instance, and it produces a new value based on a function. -</p> - -<p> -assign a value for each of the points in the feature space. -</p> - -<p> -evaluating regression -- what's a good model for a regression? -</p> - -<p> -you use an error function (the difference between predicted and real values, square to avoid negatives): -</p> - -<p> -\(error(p) = \sum_i (f_p (x_i) - y_i)^2\) -</p> - -<p> -<img src="img/error-graph.png" alt="Error graph" /> -</p> - -<p> -in this example, each of the possible lines is represented by two parameters (s the slope, b the y-intercept), in the left graph. those parameters can be plotted on 2D axes, on the right graph. -</p> - -<p> -<img src="img/feature-model-space.png" alt="Feature and model space" /> -</p> - -<p> -Then you can take those points in the right graph, and plot their respective error rates (from the error function above) on the z axis, so you end up with a 3D graph -- an error surface: -</p> - -<p> -<img src="img/error-surface.png" alt="Error surface" /> -</p> - -<p> -now the point is to find the one with the lowest error (the lowest point in the surface, colored green). and that's what calculus is for, specifically differentiation. -</p> - -<p> -if you've never done calculus, it's not easy to explain, but basically taking the derivative means you're looking for the slope of a certain function at some point in that function. if you set the derivative to zero, you're looking for the point where the slope is zero -- specifically the minimum or maximum of a function. -</p> - -<p> -quick example: if you have a function \(y = x^2 + 2\), there's a minimum at x = 0. you may know that by intuition, but you can also take the first derivative (\(y' = 2x\)), set \(y'\) equal to zero, and solve for x -- you'll get the same result. it's trivial with a simple function, but once you get into cubic and quartic functions, you can't really do it by intuition.. -</p> - -<p> -so a derivative \(f'(x)\) of a function \(f(x)\) gives the slope of \(f(x)\) at any point in the domain (where \(f(x)\) has a value \(y\)). -</p> - -<p> -the rules for taking derivatives (don't need to memorize these, they will be provided on the exam): -</p> - -<p> -<img src="img/derivative-rules.png" alt="Derivative rules" /> -</p> - -<p> -the problems: -</p> -<ul> -<li> -not all derivatives that we find can be resolved to zero - -<li> -and we also have to consider that this can be in higher dimensions - -</ul> - -<div id="Machine Learning-Machine Learning Steps:-Choose the model (model search)-Gradient descent"><h4 id="Gradient descent">Gradient descent</h4></div> -<p> -you use a variant of the hill climbing algorithm -</p> - -<p> -the steps: -</p> -<ol> -<li> -pick random parameters s (slope), b (intercept) - -<li> -repeat: - -<ol> -<li> -compute the gradient - -<li> -move a small step in the opposite direction - -</ol> -</ol> - -<p> -but there may be multiple zero points -- local optima. there's no guarantee of convergence. -</p> - -<div id="Machine Learning-Neural Networks"><h2 id="Neural Networks">Neural Networks</h2></div> -<div id="Machine Learning-Neural Networks-Overview"><h3 id="Overview">Overview</h3></div> -<p> -the difference between original machine learning and deep learning: -</p> - -<p> -<img src="img/ml-vs-dl.png" /> -</p> - -<p> -the original perceptron: -</p> -<ul> -<li> -binary classifier - -<li> -bias node, always set to 1 - -<li> -n inputs for each feature, with weights - -<li> -\(y=w_1 x_1 _ w_2 x_2 + b\) - -</ul> - -<p> -but chaining doesn't make it more interesting, the function collapses to a linear one -</p> - -<p> -<img src="img/perceptron.png" /> -</p> - -<p> -So introduce an activation function instead of using a standard linear calculation. This puts the values in a certain range, and now the diagram looks like this: -</p> - -<p> -<img src="img/activation-functions.png" /> -</p> - -<p> -Then you can build a feed-forward network with hidden layers between input and output: -</p> - -<p> -<img src="img/feedforward.png" /> -</p> - - -<div id="Machine Learning-Neural Networks-Training neural networks"><h3 id="Training neural networks">Training neural networks</h3></div> -<p> -Loss function determines how close a given network is to being correct for an input. -If you plot neural networks on x-y, and the amount of loss on z axis, you end up with a loss surface. Then you want to find a point in that surface where the loss is the lowest. -</p> - -<p> -<img src="img/loss-plot.png" /> -<img src="img/loss-surface.png" /> -</p> - -<p> -You can find the low point in the error surface with gradient descent (differentiation). -</p> - -<p> -Stochastic gradient descent: -</p> -<ol> -<li> -pick random weights w - -<li> -loop: - -<ul> -<li> -\(w = w - r \triangledown loss (w)\) - -</ul> -</ol> - -<p> -where r is the learning rate. make sure to pick a good learning rate because if it's too high (like 0.1), it will be inaccurate, while if it's too low, it will take a long time. -</p> - -<p> -so in summary: -</p> -<ul> -<li> -get examples of input and output - -<li> -get a loss function - -<li> -work out the gradient of loss with respect to the weights - -<li> -use (stochastic) gradient descent to slowly improve the weights - -</ul> - -<p> -how do you calculate the gradient for complex data? -</p> -<ul> -<li> -symbolically? too computationally expensive - -<li> -numerically? too unstable, also expensive - -<li> -so settle for a middle ground -- backpropagation - -</ul> - -<p> -backpropagation: if the system is a composition of modules, the gradient is the product of the gradient of each module with respect to its arguments -</p> -<ul> -<li> -break computation down into chain of modules - -<li> -work out derivative of each module with respect to its input (<em>symbolically</em>) - -<li> -compute the gradient for a given input by multiplying these gradients for the current input - -</ul> - -<p> -<img src="img/backpropagation.png" /> -</p> - -<p> -for a given input x, you do a forward pass (calculating the value for each part), then fill in into final calculation. -</p> - -<p> -so like this, with x = 0: -</p> - -<p> -<img src="img/backpropagation-calculation.png" /> -</p> - -<p> -neural networks are just a way of thinking about differentiable computation. -</p> - -<div id="Machine Learning-Neural Networks-Autoencoders: a NN architecture"><h3 id="Autoencoders: a NN architecture">Autoencoders: a NN architecture</h3></div> -<p> -bottleneck architecture: -</p> - -<p> -<img src="img/autoencoder-architecture.png" /> -</p> - -<p> -input should be as close as possible to the output. but it must pass through a small representation -</p> - -<p> -autoencoders map data to a <em>latent representation</em> -</p> - -<div id="Machine Learning-Neural Networks-Trying it out"><h3 id="Trying it out">Trying it out</h3></div> -<ul> -<li> -code: <a href="https://github.com/pbloem/machine-learning/blob/master/code-samples/autoencoder/autoencoder.py">https://github.com/pbloem/machine-learning/blob/master/code-samples/autoencoder/autoencoder.py</a> - -<li> -setup: <a href="https://docs.google.com/document/d/1-LXG5Lb76xQy70W2ZdannnYMEXRLt0CsoiaK0gTkmfY/edit?usp=sharing">https://docs.google.com/document/d/1-LXG5Lb76xQy70W2ZdannnYMEXRLt0CsoiaK0gTkmfY/edit?usp=sharing</a> - -</ul> - -<div id="Machine Learning-The promise of depth"><h2 id="The promise of depth">The promise of depth</h2></div> -<p> -if you have many dimensions, the gradient isn't as easy to detect anymore. there's a huge number of parameters. -</p> - -<p> -solutions: -</p> -<ul> -<li> -Pretraining (no pre-classification by humans) - -<ul> -<li> -train the network on itself in hidden layers - -<li> -similar to the autoencoder idea - -<li> -you can then stack the autoencoders (hidden layers) - -</ul> -</ul> -<blockquote> -<img src="img/pretraining.png" alt="Pretraining" /> -</blockquote> - -<ul> -<li> -Pruning the network - -<ul> -<li> -convolutional neural network: combine multiple input nodes into one node of a hidden layer - -</ul> -</ul> - -</body> -</html> diff --git a/content/is-notes/img/3d-hyperplane.png b/content/is-notes/machine-learning/3d-hyperplane.png Binary files differ. diff --git a/content/is-notes/img/activation-functions.png b/content/is-notes/machine-learning/activation-functions.png Binary files differ. diff --git a/content/is-notes/img/autoencoder-architecture.png b/content/is-notes/machine-learning/autoencoder-architecture.png Binary files differ. diff --git a/content/is-notes/img/backpropagation-calculation.png b/content/is-notes/machine-learning/backpropagation-calculation.png Binary files differ. diff --git a/content/is-notes/img/backpropagation.png b/content/is-notes/machine-learning/backpropagation.png Binary files differ. diff --git a/content/is-notes/img/bayes-calculation.png b/content/is-notes/machine-learning/bayes-calculation.png Binary files differ. diff --git a/content/is-notes/img/cross-validation.png b/content/is-notes/machine-learning/cross-validation.png Binary files differ. diff --git a/content/is-notes/img/curve-fitting.png b/content/is-notes/machine-learning/curve-fitting.png Binary files differ. diff --git a/content/is-notes/img/derivative-rules.png b/content/is-notes/machine-learning/derivative-rules.png Binary files differ. diff --git a/content/is-notes/img/design-matrix.png b/content/is-notes/machine-learning/design-matrix.png Binary files differ. diff --git a/content/is-notes/img/error-graph.png b/content/is-notes/machine-learning/error-graph.png Binary files differ. diff --git a/content/is-notes/img/error-surface.png b/content/is-notes/machine-learning/error-surface.png Binary files differ. diff --git a/content/is-notes/img/feature-model-space.png b/content/is-notes/machine-learning/feature-model-space.png Binary files differ. diff --git a/content/is-notes/img/feature-space.png b/content/is-notes/machine-learning/feature-space.png Binary files differ. diff --git a/content/is-notes/img/feedforward.png b/content/is-notes/machine-learning/feedforward.png Binary files differ. diff --git a/content/is-notes/machine-learning/index.md b/content/is-notes/machine-learning/index.md @@ -0,0 +1,308 @@ ++++ +title = "Machine Learning" +template = 'page-math.html' ++++ +# Machine Learning + +design of a learning element is affected by: + * which components of performance element are to be learned + * what feedback is available to learn these components + * what representation is used for the components + +offline learning: learn based on some data, then apply results to situation + +feedback types (get input, make decision, learn based on feedback): + * supervised learning: correct answers for each example. + * only positive examples + * positive and negative examples + * unsupervised learning: no correct answers given + * semi-supervised learning: learn which questions to ask (active learning) + * reinforcement learning: occasional rewards + + + +## Learning problems + +Classification + * use: from data to discrete classes. + * examples: handwriting recognition, spam filtering, facial recognition. + +Regression + * use: predicting a numeric value + * examples: stock market, weather predictions + +Ranking + * use: comparing items + * examples: web search + +Collaborative filtering + * use: take some else's information, based on that, give prediction + * examples: recommendation systems (books, movies/shows) + +Clustering + * use: discovering structure/patterns in data + * examples: clustering images + +## Methodology +### Data +labeled instances (like spam, not spam) + * training set + * held out set (e.g. for validation) + * test set (don't even look at this until you want to test your model) + +randomly allocate to data sets. + +features: attribute-value pairs characterizing each x + +### Experimentation +experimentation cycle: + 1. select hypothesis, tune hyperparameters on held-out/validation set + 2. compute accuracy of test set (never "peek" at test set itself) + +### Evaluation +accuracy -- fraction of instances predicted correctly + +Cross validation: + + + +create a confusion matrix (TODO: there's a diagram for this but not in the old slides) + +## Machine Learning Steps: + 1. choose the features + 2. choose the model class + 3. choose a search method + +### Choose the features +create a feature space: features on x-y axes, points are individual data, classification would be a color scheme. + + + + +#### Inductive learning method + * construct/adjust h to agree with f (function predicting value) on training set + * h is consistent if it agrees with f on all examples + * for example, curve fitting: + +  + +Occam's razor: "one should not increase, beyond what is necessary, the number of entities required to explain anything" +basically, choose the simplest option. + +#### Classifying with naive Bayes + +Binary classification +* input: email +* output: spam, not spam +* setup: + * get large collection of example emails, labeled "spam/not spam" + * someone has to hand-label that + * want to learn to predict label for new emails in future +* features: attributes used to make label decision + * words, text patterns (e.g. caps), non-text + +calculation for Bayesian classifier: $P(C|F_1,...,F_n)$ + +using Bayes' theorem: + +$P(C|F_1,...F_n)=\frac{P(C)P(F_1,...,F_n|C)}{P(F_1,...,F_n)}$ + +rewrite the numerator of the equation: + +$P(C)P(F_1,...,F_n |C) = P(C)P(F_1 | C)P(F_2 | C, F_1)P(F_3|C, F_1, F_2)P(F_4,...,F_n | C, F_1, F_2, F_3)$ + +that uses the chaining rule. but it's too computationally expensive. +so naively assume conditional independence: + +$P(F_i | C, F_j) = P(F_i | C)$ + +This simplifies the formula to: + +$P(C)P(F_1,...,F_n | C) = P(C) PI(0 to n) P(F_i | C)$ + + + +Laplace smoothing helps with really small probabilities. +Naive Bayes often works. sometimes performs well even if the assumptions are badly violated. +classification is about predicting correct class label, _not_ about accurately estimating probabilities + +#### Clustering with K-nearest neighbor +k nearest neighbor classification: find k most similar case, copy majority label + +e.g. to classify unlabeled document, find most similar document and copy label: + + + +the _k_ helps get rid of noise which would lead to misclassification + +#### Linear classifier +linear classifier: come up with a line that divides feature space, use that for prediction. + +works for stuff like $x \lor y$, but not if we want $x \oplus y$ or other things that are not linearly separable. + +you can build a design matrix of all the different features you want to include. here's an example with 5 different features *age, height, age², age × height, height²) that classifies a person as male/female: + + + +if you go to more dimensions (so more features in a design matrix), you need hyperplanes. + +hyperplanes sound fancy af but it's just a line in some higher dimension. for example, this is how you would use a hyperplane in the third dimension to separate points: + + + +#### Support vector machine +k(x,y): "distance" function between instances x and y + +SVMs create a linear separating hyperplane + +they can embed that hyperplane into a higher dimensional domain using the kernel trick -- so long as _k_ is a kernel, you don't have to explicitly compute the design matrix (that drastically reduces the computation) + +try to achieve a good margin -- a large separation from the line for both classes (so reduce the blur between two classes, make a clear distinction). + +watch out for over-fitting -- you might end up with the model being trained extremely specifically to your data. + +### Choose the model (model search) + +so we have a lot of ways to put a line on a graph. but how do you choose the right one? + +#### Regression +train a learner to produce a model (the model is the line/hyperplane). then you give the model a new instance, and it produces a new value based on a function. + +assign a value for each of the points in the feature space. + +evaluating regression -- what's a good model for a regression? + +you use an error function (the difference between predicted and real values, square to avoid negatives): + +$error(p) = \sum_i (f_p (x_i) - y_i)^2$ + + + +in this example, each of the possible lines is represented by two parameters (s the slope, b the y-intercept), in the left graph. those parameters can be plotted on 2D axes, on the right graph. + + + +Then you can take those points in the right graph, and plot their respective error rates (from the error function above) on the z axis, so you end up with a 3D graph -- an error surface: + + + +now the point is to find the one with the lowest error (the lowest point in the surface, colored green). and that's what calculus is for, specifically differentiation. + +if you've never done calculus, it's not easy to explain, but basically taking the derivative means you're looking for the slope of a certain function at some point in that function. if you set the derivative to zero, you're looking for the point where the slope is zero -- specifically the minimum or maximum of a function. + +quick example: if you have a function $y = x^2 + 2$, there's a minimum at x = 0. you may know that by intuition, but you can also take the first derivative ($y' = 2x$), set $y'$ equal to zero, and solve for x -- you'll get the same result. it's trivial with a simple function, but once you get into cubic and quartic functions, you can't really do it by intuition.. + +so a derivative $f'(x)$ of a function $f(x)$ gives the slope of $f(x)$ at any point in the domain (where $f(x)$ has a value $y$). + +the rules for taking derivatives (don't need to memorize these, they will be provided on the exam): + + + +the problems: + * not all derivatives that we find can be resolved to zero + * and we also have to consider that this can be in higher dimensions + +#### Gradient descent +you use a variant of the hill climbing algorithm + +the steps: + 1. pick random parameters s (slope), b (intercept) + 2. repeat: + 1. compute the gradient + 2. move a small step in the opposite direction + +but there may be multiple zero points -- local optima. there's no guarantee of convergence. + +## Neural Networks +### Overview +the difference between original machine learning and deep learning: + + + +the original perceptron: + * binary classifier + * bias node, always set to 1 + * n inputs for each feature, with weights + * $y=w_1 x_1 + w_2 x_2 + b$ + +but chaining doesn't make it more interesting, the function collapses to a linear one + + + +So introduce an activation function instead of using a standard linear calculation. This puts the values in a certain range, and now the diagram looks like this: + + + +Then you can build a feed-forward network with hidden layers between input and output: + + + + +### Training neural networks +Loss function determines how close a given network is to being correct for an input. +If you plot neural networks on x-y, and the amount of loss on z axis, you end up with a loss surface. Then you want to find a point in that surface where the loss is the lowest. + + + + +You can find the low point in the error surface with gradient descent (differentiation). + +Stochastic gradient descent: + 1. pick random weights w + 2. loop: + * $w = w - r \triangledown loss (w)$ + +where r is the learning rate. make sure to pick a good learning rate because if it's too high (like 0.1), it will be inaccurate, while if it's too low, it will take a long time. + +so in summary: + * get examples of input and output + * get a loss function + * work out the gradient of loss with respect to the weights + * use (stochastic) gradient descent to slowly improve the weights + +how do you calculate the gradient for complex data? + * symbolically? too computationally expensive + * numerically? too unstable, also expensive + * so settle for a middle ground -- backpropagation + +backpropagation: if the system is a composition of modules, the gradient is the product of the gradient of each module with respect to its arguments + * break computation down into chain of modules + * work out derivative of each module with respect to its input (_symbolically_) + * compute the gradient for a given input by multiplying these gradients for the current input + + + +for a given input x, you do a forward pass (calculating the value for each part), then fill in into final calculation. + +so like this, with x = 0: + + + +neural networks are just a way of thinking about differentiable computation. + +### Autoencoders: a NN architecture +bottleneck architecture: + + + +input should be as close as possible to the output. but it must pass through a small representation + +autoencoders map data to a _latent representation_ + +### Trying it out +* code: https://github.com/pbloem/machine-learning/blob/master/code-samples/autoencoder/autoencoder.py +* setup: https://docs.google.com/document/d/1-LXG5Lb76xQy70W2ZdannnYMEXRLt0CsoiaK0gTkmfY/edit?usp=sharing + +## The promise of depth +if you have many dimensions, the gradient isn't as easy to detect anymore. there's a huge number of parameters. + +solutions: + * Pretraining (no pre-classification by humans) + * train the network on itself in hidden layers + * similar to the autoencoder idea + * you can then stack the autoencoders (hidden layers) + +  + + * Pruning the network + * convolutional neural network: combine multiple input nodes into one node of a hidden layer diff --git a/content/is-notes/img/knn.png b/content/is-notes/machine-learning/knn.png Binary files differ. diff --git a/content/is-notes/img/loss-plot.png b/content/is-notes/machine-learning/loss-plot.png Binary files differ. diff --git a/content/is-notes/img/loss-surface.png b/content/is-notes/machine-learning/loss-surface.png Binary files differ. diff --git a/content/is-notes/img/ml-vs-dl.png b/content/is-notes/machine-learning/ml-vs-dl.png Binary files differ. diff --git a/content/is-notes/img/neurons-vs-nn.png b/content/is-notes/machine-learning/neurons-vs-nn.png Binary files differ. diff --git a/content/is-notes/img/perceptron.png b/content/is-notes/machine-learning/perceptron.png Binary files differ. diff --git a/content/is-notes/img/pretraining.png b/content/is-notes/machine-learning/pretraining.png Binary files differ. diff --git a/content/is-notes/philosophy.html b/content/is-notes/philosophy.html @@ -1,149 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>philosophy</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Philosophy of AI"><h1 id="Philosophy of AI">Philosophy of AI</h1></div> -<p> -what is intelligence? -</p> -<ul> -<li> -classically, you test this using the Turing Test - -<ul> -<li> -interrogation game - -<li> -interrogate two parties, the goal of both parties is to convince the interrogator that they are human - -<li> -if the interrogator can't tell who is the human, the computer is intelligent - -</ul> -<li> -the objections: - -<ul> -<li> -the test is subjective - -<li> -why are we basing intelligence on <em>human</em> intelligence? metaphor with flight, we only managed to get off the ground once we stopped imitating natural flight - -</ul> -</ul> - -<p> -intelligence is everything a computer can't do yet. -</p> - -<p> -can a computer be intelligent? -</p> -<ul> -<li> -substitution argument: if you replace one neuron at a time with a computer chip in the human brain, you would eventually change into a computer, without your conscience or thought process changing at any point. - -<li> -medium argument: no. "carbohydrate racism", there's something special about carbohydrates that allows us to do stuff that computers can't do. - -<li> -formal systems argument: no. mathematical systems are inherently limited in some way; since computers are just formal systems, therefore they inherently have some limitations. we are not formal systems (that's debatable) so we do not have those limitations. - -<li> -symbol-grounding: learning systems manipulate symbols - -<ul> -<li> -symbols can only refer to other symbols, so how can a computer ever know what's "red", "heavy", "sad" in the 'real' world? - -<li> -so simulated intelligence ≠ real intelligence - -<li> -thought experiment - the Chinese Room: - -<ul> -<li> -a room with Chinese symbols coming in - -<li> -there's one person inside that uses a book to translate Chinese symbols to other symbols - -<li> -there's nothing in this system that understands Chinese - -</ul> -</ul> -</ul> - -<p> -Mind-body problem: -</p> -<ul> -<li> -we have the physical body, and metaphysical thoughts - -<li> -what could be the relationship between the physical and the metaphysical? - -<li> -opinions: - -<ul> -<li> -mind-body dualism, interactionism: we consist of two parts (physical <em>and</em> metaphysical) -- Descartes - -<li> -materialism: the mind and body is one thing - -<li> -gradualism: we evolved the mind (intelligence, consciousness) over time - -</ul> -</ul> - -<p> -Intentional stance: -</p> -<ul> -<li> -intelligence/consciousness is "attributed" and "gradual" - -<li> -so the question isn't "will computers ever be conscious?", but rather "will we ever use consciousness-related words to describe them?" - -<li> -if it's useful to talk about consciousness, motivation, feeling, etc., then we are allowed to (or should) do so equally for both humans and machines - -<li> -people have a strong tendency to take the intentional stance, so we will <em>call</em> our computers "intelligent" - -</ul> - -<p> -Free will: -</p> -<ul> -<li> -reasons why it can't be true: - -<ul> -<li> -physics is deterministic, you can predict the next states, so your brain doesn't <em>physically</em> allow free will - -<li> -inconsistent with psychology and neuroscience -- motor areas begin activity 2 seconds before we think we want to do something (<a href="https://www.youtube.com/watch?v=IQ4nwTTmcgs">Libet's experiment</a>) - -</ul> -</ul> - -</body> -</html> diff --git a/content/is-notes/philosophy.md b/content/is-notes/philosophy.md @@ -0,0 +1,45 @@ ++++ +title = "Philosophy of AI" ++++ +# Philosophy of AI +what is intelligence? + * classically, you test this using the Turing Test + * interrogation game + * interrogate two parties, the goal of both parties is to convince the interrogator that they are human + * if the interrogator can't tell who is the human, the computer is intelligent + * the objections: + * the test is subjective + * why are we basing intelligence on _human_ intelligence? metaphor with flight, we only managed to get off the ground once we stopped imitating natural flight + +intelligence is everything a computer can't do yet. + +can a computer be intelligent? + * substitution argument: if you replace one neuron at a time with a computer chip in the human brain, you would eventually change into a computer, without your conscience or thought process changing at any point. + * medium argument: no. "carbohydrate racism", there's something special about carbohydrates that allows us to do stuff that computers can't do. + * formal systems argument: no. mathematical systems are inherently limited in some way; since computers are just formal systems, therefore they inherently have some limitations. we are not formal systems (that's debatable) so we do not have those limitations. + * symbol-grounding: learning systems manipulate symbols + * symbols can only refer to other symbols, so how can a computer ever know what's "red", "heavy", "sad" in the 'real' world? + * so simulated intelligence ≠ real intelligence + * thought experiment - the Chinese Room: + * a room with Chinese symbols coming in + * there's one person inside that uses a book to translate Chinese symbols to other symbols + * there's nothing in this system that understands Chinese + +Mind-body problem: + * we have the physical body, and metaphysical thoughts + * what could be the relationship between the physical and the metaphysical? + * opinions: + * mind-body dualism, interactionism: we consist of two parts (physical _and_ metaphysical) -- Descartes + * materialism: the mind and body is one thing + * gradualism: we evolved the mind (intelligence, consciousness) over time + +Intentional stance: + * intelligence/consciousness is "attributed" and "gradual" + * so the question isn't "will computers ever be conscious?", but rather "will we ever use consciousness-related words to describe them?" + * if it's useful to talk about consciousness, motivation, feeling, etc., then we are allowed to (or should) do so equally for both humans and machines + * people have a strong tendency to take the intentional stance, so we will _call_ our computers "intelligent" + +Free will: + * reasons why it can't be true: + * physics is deterministic, you can predict the next states, so your brain doesn't _physically_ allow free will + * inconsistent with psychology and neuroscience -- motor areas begin activity 2 seconds before we think we want to do something ([[https://www.youtube.com/watch?v=IQ4nwTTmcgs|Libet's experiment]]) diff --git a/content/is-notes/probability-uncertainty.html b/content/is-notes/probability-uncertainty.html @@ -1,358 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>probability-uncertainty</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Probability and Uncertainty"><h1 id="Probability and Uncertainty">Probability and Uncertainty</h1></div> -<p> -one often has to deal with info that is underspecified, incomplete, vague, etc. -</p> - -<p> -logic by itself is not sufficient for these problems. -</p> - -<div id="Probability and Uncertainty-Vagueness: Fuzzy Set Theory"><h2 id="Vagueness: Fuzzy Set Theory">Vagueness: Fuzzy Set Theory</h2></div> -<p> -model theory often based on set theory -</p> - -<p> -fuzzy set theory allows something to be <em>to some degree</em> an element of a set -</p> - -<p> -dominant approach to vagueness (mostly because wtf else can you do) -</p> - -<div id="Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Fuzzy sets"><h3 id="Fuzzy sets">Fuzzy sets</h3></div> -<ul> -<li> -universe U, object x ∈ U - -<li> -membership function for fuzzy set A is defined to be function \(f_A\) from U to [0,1]: - -<ul> -<li> -\(f_A(x)=y\): x is a member of A to degree y - -<li> -\(f_A(x)=1\): x is certainly member of A - -<li> -\(f_A(x)=0\): x is certainly not a member of A - -<li> -\({x | f_A(x)>0}\): support of A - -</ul> -</ul> - -<p> -modifiers (hedges) -</p> - -<p> -<img src="img/modifiers-hedges.png" alt="Example of modifiers' effects on graphs" /> -</p> - -<p> -operations on fuzzy sets: -</p> -<ul> -<li> -complement: \(f_{\sim{A}}(x)=1-f_A(x)\) - -<li> -union: \(f_{A\cup B}(x)=\max(f_A(x),f_B(x))\) - -<li> -intersection: \(f_{A\cap B}(x)=\min(f_A(x), f_B(x))\) - -<li> -subset: \(A\subset B \iff \forall{x}(f_A(x)\leq f_B(x))\) - -</ul> - -<p> -semantics -- multivalued fuzzy logic -</p> -<ul> -<li> -v(¬ A) = 1-v(A) - -<li> -v(A ∨ B) = max(v(A), v(B)) - -<li> -v(A ∧ B) = min(v(A), v(B)) - -<li> -v(A → B) = min(1, 1 - v(A) + v(B)) - -</ul> - -<div id="Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Fuzzy relations"><h3 id="Fuzzy relations">Fuzzy relations</h3></div> -<p> -fuzzy sets can denote fuzzy relations between objects. e.g. approximately equal, close to, much larger than, etc. -</p> - -<p> -fuzzy composition: -</p> - -<p> -\(f_{R \circ S} (\langle x,z\rangle ) = \max_{y \in Y} \min(f_R (\langle x,y\rangle ), f_S (\langle y,z\rangle ))\) -</p> - -<p> -hands-on example: -</p> - -<p> -<img src="img/fuzzy-composition.png" alt="Fuzzy composition table" /> -</p> - -<div id="Probability and Uncertainty-Vagueness: Fuzzy Set Theory-Evaluation"><h3 id="Evaluation">Evaluation</h3></div> -<ul> -<li> -good -- flexible, coincides with classical set theory, sever successful applications of fuzzy control - -<li> -bad -- requires many arbitrary choices, tends to blur differences between probabilistic uncertainty/ambiguity/vagueness - -</ul> - -<div id="Probability and Uncertainty-Uncertainties: Probability Theory"><h2 id="Uncertainties: Probability Theory">Uncertainties: Probability Theory</h2></div> -<div id="Probability and Uncertainty-Uncertainties: Probability Theory-General"><h3 id="General">General</h3></div> -<p> -main interpretations of probability theory: -</p> -<ul> -<li> -optivist (frequentist) probability - -<ul> -<li> -frequentism: probability is only property of repeated experiments - -<li> -probability of event: limit of <em>relative frequency</em> of occurrence of event, as number of repetitions goes to infinity - -</ul> -<li> -subjective probability - -<ul> -<li> -Bayesianism: probability is an expression of our uncertainty and beliefs - -<li> -probability of event: <em>degree of belief</em> of idealized rational individual - -</ul> -</ul> - -<p> -sample space Ω: set of single outcomes of experiment -</p> - -<p> -event space E: things that have probability (subsets of sample space). if sample space is finite, event space is usually power set. -</p> - -<div id="Probability and Uncertainty-Uncertainties: Probability Theory-Axioms of probability"><h3 id="Axioms of probability">Axioms of probability</h3></div> -<p> -for any event A, B: -</p> -<ul> -<li> -\(0 \leq P(A) \leq 1\) - -<li> -\(P(\Omega) = 1\) - -<li> -\(P(A \cup B) = P(A) + P(B) - P(A \cap B)\) - -</ul> - -<p> -can derive: -</p> -<ul> -<li> -\(P({}) = 0\) - -<li> -\(P(\Omega) = 1\) - -<li> -\(\text{if} A \subset B, P(A) \leq P(B)\) - -</ul> - -<p> -conditional probability ("A given B"): -</p> - -<p> -\(P(A|B) = \frac{P(A \cap B)}{P(B)}\) -</p> - -<div id="Probability and Uncertainty-Uncertainties: Probability Theory-Joint probability distributions"><h3 id="Joint probability distributions">Joint probability distributions</h3></div> -<p> -for a set of random variables, it gives probability of every atomic even on those random variables. -</p> - -<p> -e.g. P(Toothache, Catch, Cavity): -</p> - -<table> -<tr> -<th> - -</th> -<th colspan="2"> -toothache -</th> -<th colspan="2"> -¬ toothache -</th> -</tr> -<tr> -<td> - -</td> -<td> -catch -</td> -<td> -¬ catch -</td> -<td> -catch -</td> -<td> -¬ catch -</td> -</tr> -<tr> -<td> -cavity -</td> -<td> -0.108 -</td> -<td> -0.012 -</td> -<td> -0.072 -</td> -<td> -0.008 -</td> -</tr> -<tr> -<td> -¬ cavity -</td> -<td> -0.015 -</td> -<td> -0.064 -</td> -<td> -0.144 -</td> -<td> -0.576 -</td> -</tr> -</table> - -<p> -inference by enumeration: -</p> -<ul> -<li> -for any proposition Φ, sum atomic events where it's true -- \(P(\Phi) = \sum_{\omega : \omega \models \Phi} P(\omega)\) - -<li> -compute conditional probability by selecting cells -- e.g. for P(¬ cavity | toothache), select toothache column and (¬ cavity) cells - -</ul> - -<p> -use Bayes' rule for opposite conditionals (like finding P(disease | symptom) from P(symptom | disease)) -</p> - -<div id="Probability and Uncertainty-Uncertainties: Probability Theory-Bayesian networks"><h3 id="Bayesian networks">Bayesian networks</h3></div> -<p> -simple graphical notation for -</p> -<ul> -<li> -conditional independence assertions - -<li> -compact specification of full joint distributions - -</ul> - -<p> -syntax: -</p> -<ul> -<li> -set of nodes, one per variable - -<li> -directed acyclic graph, with a link meaning "directly influences" - -<li> -conditional distribution for each node given its parents -- \(P(X_i | Parents(X_i))\) - -</ul> - -<p> -topology example: -</p> - -<p> -<img src="img/bayesian-topology.png" alt="Bayesian network topology" /> -</p> - -<p> -what does it mean? -</p> -<ul> -<li> -<em>weather</em> is independent of other variables - -<li> -<em>toothache</em> and <em>catch</em> are conditionally independent given <em>cavity</em>. - -</ul> - -<div id="Probability and Uncertainty-Uncertainties: Probability Theory-Evaluation of probabilities"><h3 id="Evaluation of probabilities">Evaluation of probabilities</h3></div> -<ul> -<li> -good -- sound theoretical basis, can be extended to decision-making, some good tools available - -<li> -bad -- not always computationally easy, need lots of data which may be hard to get - -</ul> - -</body> -</html> diff --git a/content/is-notes/img/bayesian-topology.png b/content/is-notes/probability-uncertainty/bayesian-topology.png Binary files differ. diff --git a/content/is-notes/img/fuzzy-composition.png b/content/is-notes/probability-uncertainty/fuzzy-composition.png Binary files differ. diff --git a/content/is-notes/probability-uncertainty/index.md b/content/is-notes/probability-uncertainty/index.md @@ -0,0 +1,124 @@ ++++ +title = "Probability and Uncertainty" +template = 'page-math.html' ++++ +# Probability and Uncertainty +one often has to deal with info that is underspecified, incomplete, vague, etc. + +logic by itself is not sufficient for these problems. + +## Vagueness: Fuzzy Set Theory +model theory often based on set theory + +fuzzy set theory allows something to be _to some degree_ an element of a set + +dominant approach to vagueness (mostly because wtf else can you do) + +### Fuzzy sets + * universe U, object x ∈ U + * membership function for fuzzy set A is defined to be function $f_A$ from U to [0,1]: + * $f_A(x)=y$: x is a member of A to degree y + * $f_A(x)=1$: x is certainly member of A + * $f_A(x)=0$: x is certainly not a member of A + * ${x | f_A(x)>0}$: support of A + +modifiers (hedges) + + + +operations on fuzzy sets: + * complement: $f_{\sim{A}}(x)=1-f_A(x)$ + * union: $f_{A\cup B}(x)=\max(f_A(x),f_B(x))$ + * intersection: $f_{A\cap B}(x)=\min(f_A(x), f_B(x))$ + * subset: $A\subset B \iff \forall{x}(f_A(x)\leq f_B(x))$ + +semantics -- multivalued fuzzy logic + * v(¬ A) = 1-v(A) + * v(A ∨ B) = max(v(A), v(B)) + * v(A ∧ B) = min(v(A), v(B)) + * v(A → B) = min(1, 1 - v(A) + v(B)) + +### Fuzzy relations +fuzzy sets can denote fuzzy relations between objects. e.g. approximately equal, close to, much larger than, etc. + +fuzzy composition: + +$f_{R \circ S} (\langle x,z\rangle ) = \max_{y \in Y} \min(f_R (\langle x,y\rangle ), f_S (\langle y,z\rangle ))$ + +hands-on example: + + + +### Evaluation + * good -- flexible, coincides with classical set theory, sever successful applications of fuzzy control + * bad -- requires many arbitrary choices, tends to blur differences between probabilistic uncertainty/ambiguity/vagueness + +## Uncertainties: Probability Theory +### General +main interpretations of probability theory: + * optivist (frequentist) probability + * frequentism: probability is only property of repeated experiments + * probability of event: limit of _relative frequency_ of occurrence of event, as number of repetitions goes to infinity + * subjective probability + * Bayesianism: probability is an expression of our uncertainty and beliefs + * probability of event: _degree of belief_ of idealized rational individual + +sample space Ω: set of single outcomes of experiment + +event space E: things that have probability (subsets of sample space). if sample space is finite, event space is usually power set. + +### Axioms of probability +for any event A, B: + * $0 \leq P(A) \leq 1$ + * $P(\Omega) = 1$ + * $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ + +can derive: + * $P({}) = 0$ + * $P(\Omega) = 1$ + * $\text{if} A \subset B, P(A) \leq P(B)$ + +conditional probability ("A given B"): + +$P(A|B) = \frac{P(A \cap B)}{P(B)}$ + +### Joint probability distributions +for a set of random variables, it gives probability of every atomic even on those random variables. + +e.g. P(Toothache, Catch, Cavity): + +| | toothache | > | ¬ toothache | > | +|----------|-----------|---------|-------------|---------| +| | catch | ¬ catch | catch | ¬ catch | +| cavity | 0.108 | 0.012 | 0.072 | 0.008 | +| ¬ cavity | 0.015 | 0.064 | 0.144 | 0.576 | + +inference by enumeration: + * for any proposition Φ, sum atomic events where it's true -- $P(\Phi) = \sum_{\omega : \omega \models \Phi} P(\omega)$ + * compute conditional probability by selecting cells -- e.g. for P(¬ cavity | toothache), select toothache column and (¬ cavity) cells + +use Bayes' rule for opposite conditionals (like finding P(disease | symptom) from P(symptom | disease)) + +### Bayesian networks +simple graphical notation for + * conditional independence assertions + * compact specification of full joint distributions + +syntax: + * set of nodes, one per variable + * directed acyclic graph, with a link meaning "directly influences" + * conditional distribution for each node given its parents -- $P(X_i | Parents(X_i))$ + +topology example: + + + +what does it mean? + * _weather_ is independent of other variables + * _toothache_ and _catch_ are conditionally independent given _cavity_. + +### Evaluation of probabilities + * good -- sound theoretical basis, can be extended to decision-making, some good tools available + * bad -- not always computationally easy, need lots of data which may be hard to get + + diff --git a/content/is-notes/img/modifiers-hedges.png b/content/is-notes/probability-uncertainty/modifiers-hedges.png Binary files differ. diff --git a/content/is-notes/rational-agents.html b/content/is-notes/rational-agents.html @@ -1,166 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>rational-agents</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="Rational agents"><h1 id="Rational agents">Rational agents</h1></div> - -<p> -"A rational agent chooses whichever action maximizes the expected value of the performance measure given the percept sequence to date and prior environment knowledge." -</p> - -<div id="Rational agents-Agents"><h2 id="Agents">Agents</h2></div> -<p> -agent function maps percept sequence to actions (\(f: P* \rightarrow A\)) -</p> - -<p> -function is internally represented by agent program -</p> - -<p> -program runs on physical architecture to produce f -</p> - -<div id="Rational agents-Rationality"><h2 id="Rationality">Rationality</h2></div> -<p> -what is rational at a specific time depends on: -</p> -<ul> -<li> -expected value of performance measure -- heuristics - -<li> -actions and choices -- search - -<li> -percept sequence to date -- learning - -<li> -prior environment-- KR - -</ul> - -<p> -rationality is not omniscience or perfection -</p> - -<div id="Rational agents-Task environments"><h2 id="Task environments">Task environments</h2></div> - -<p> -to design rational agent, we must specify environment (PEAS): -</p> -<ul> -<li> -performance: safety, destination, profits, legality, comfort - -<li> -environment: streets, traffic, pedestrians, weather - -<li> -actuators: steering, accelerating, brake, horn, speaker/display - -<li> -sensors: video, sonar, speedometer, etc. - -</ul> - -<p> -environment types: -</p> -<ul> -<li> -observable: fully (can detect all relevant aspects with sensors) or partially - -<li> -deterministic: (yes or no) - -<li> -static: (yes, no, semi) - -<li> -discrete: (yes or no) - -<li> -single-agent: (yes or no) - -</ul> - -<p> -<img src="img/environment-types.png" alt="Environment types table" /> -</p> - -<p> -For Schnapsen: -</p> -<ul> -<li> -observable: not fully - -<li> -deterministic: yes - -<li> -static: yes - -<li> -discrete: yes - -<li> -single-agent: no - -</ul> - -<div id="Rational agents-Agent types"><h2 id="Agent types">Agent types</h2></div> - -<div id="Rational agents-Agent types-Simple Reflex"><h3 id="Simple Reflex">Simple Reflex</h3></div> -<p> -select action on basis of <em>only the current percept</em> -</p> - -<p> -large reduction in possible percept/action situations -</p> - -<p> -implemented using condition-action rules -</p> - -<p> -only works if environment is fully observable, otherwise may result in infinite loops. -</p> - -<div id="Rational agents-Agent types-Reflex & State"><h3 id="Reflex & State">Reflex & State</h3></div> -<p> -to tackle partially observable environments, maintain internal state -</p> - -<p> -over time, update state using world knowledge. -</p> - -<div id="Rational agents-Agent types-Goal-Based"><h3 id="Goal-Based">Goal-Based</h3></div> -<p> -agent needs a goal to know the desirable situations -</p> - -<p> -future is taken into account -</p> - -<div id="Rational agents-Agent types-Learning"><h3 id="Learning">Learning</h3></div> -<p> -teach agents instead of instructing them -</p> - -<p> -very robust toward initially unknown environments. -</p> - -</body> -</html> diff --git a/content/is-notes/img/environment-types.png b/content/is-notes/rational-agents/environment-types.png Binary files differ. diff --git a/content/is-notes/rational-agents/index.md b/content/is-notes/rational-agents/index.md @@ -0,0 +1,74 @@ ++++ +title = "Rational agents" +template = 'page-math.html' ++++ +# Rational agents + +"A rational agent chooses whichever action maximizes the expected value of the performance measure given the percept sequence to date and prior environment knowledge." + +## Agents +agent function maps percept sequence to actions ($f: P* \rightarrow A$) + +function is internally represented by agent program + +program runs on physical architecture to produce f + +## Rationality +what is rational at a specific time depends on: + * expected value of performance measure -- heuristics + * actions and choices -- search + * percept sequence to date -- learning + * prior environment-- KR + +rationality is not omniscience or perfection + +## Task environments + +to design rational agent, we must specify environment (PEAS): + * performance: safety, destination, profits, legality, comfort + * environment: streets, traffic, pedestrians, weather + * actuators: steering, accelerating, brake, horn, speaker/display + * sensors: video, sonar, speedometer, etc. + +environment types: + * observable: fully (can detect all relevant aspects with sensors) or partially + * deterministic: (yes or no) + * static: (yes, no, semi) + * discrete: (yes or no) + * single-agent: (yes or no) + + + +For Schnapsen: +* observable: not fully +* deterministic: yes +* static: yes +* discrete: yes +* single-agent: no + +## Agent types + +### Simple Reflex +select action on basis of _only the current percept_ + +large reduction in possible percept/action situations + +implemented using condition-action rules + +only works if environment is fully observable, otherwise may result in infinite loops. + +### Reflex & State +to tackle partially observable environments, maintain internal state + +over time, update state using world knowledge. + +### Goal-Based +agent needs a goal to know the desirable situations + +future is taken into account + +### Learning +teach agents instead of instructing them + +very robust toward initially unknown environments. + diff --git a/content/is-notes/src/assessment-info.wiki b/content/is-notes/src/assessment-info.wiki @@ -1,43 +0,0 @@ -= Assessment info = -check learning goals on canvas. - -everything in working groups (this means go through the sheets again) - * informed search (DF, BF, DFID) - * uninformed search (Hill Climbing, BF, A, A*) - * adversarial search (minimax with alpha-beta) - * logical representations - * DPLL - * uncertainty representations - * Bayesian learning - * NN/Deep learning - -research procedure - * take at least 4 bots you implemented - * compare performance -- play against each other, in different environments - * study results: outperforming, speed - * define interesting hypotheses and research questions, use analysis to verify/falsify them - -scientific paper structure: - * title page with abstract - * title and authors - * abstract of 2-3 paragraphs - * introduction: intro to problem, solution, some results (2 pages) - * background info - * describe game, challenge, IS framework, whatever else is needed (1-2 pages) - * research question - * describe approach - * what are: - * possible outcomes of setup and contribution - * e.g. whether one method works, whether it works better than others - * also, define "working better" - * experimental setup (2 pages) - * explain how experiments were set up - * what you did in terms of implementation - * compare different methods - * define metrics - * results (2 pages) - * describe results in overview tables - * point reader to most significant, interesting results - * findings - * conclusions - diff --git a/content/is-notes/src/ethics.wiki b/content/is-notes/src/ethics.wiki @@ -1,35 +0,0 @@ -= Ethics of AI = -three main questions: - * how do we encode ethical behavior? - * how should we behave towards AI? - * how does the existence of AI affects our daily lives? - - "Ethics begins when elements of a moral system conflict." - -Fundamental ethics: moral absolutism, you are not allowed to do something due to e.g. religion - -Pragmatic ethics: humans always have a choice, you have the freedom of choice at any point in time - -== Sci-fi ethics (problems down the road) == -Asimov's laws: - 1. A robot may not injure a human being or, through inaction, allow a human being to come to harm. - 2. A robot must obey the orders given to it by human beings except where such orders would conflict with the First Law. - 3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws. - -The trolley problem is a good example of an ethical dilemma, and can be extended to self-driving cars (should it kill the driver or bystanders?). - -How do we treat AI? How should we? - -== Today's problems == -* Autonomous weapons: weapons that decide what to do by themselves - * what are we allowing these systems to do? - * the Dutch government said it's fine "if there's a human in the wider loop"...but this is very vague, what is the wider loop? -* Privacy - * big companies have a bunch of data about people - * often, people give this data for free. -* Profiling (e.g. racial) - * e.g. a black person was stopped while driving in an expensive car because the system thought he could only be driving the car if he stole it. - -Prosecutor's fallacy: - * using probabilities incorrectly. $P(\text{black} | \text{uses drugs}) \neq P(\text{uses drugs} | \text{black})$ - diff --git a/content/is-notes/src/img/3d-hyperplane.png b/content/is-notes/src/img/3d-hyperplane.png Binary files differ. diff --git a/content/is-notes/src/img/activation-functions.png b/content/is-notes/src/img/activation-functions.png Binary files differ. diff --git a/content/is-notes/src/img/autoencoder-architecture.png b/content/is-notes/src/img/autoencoder-architecture.png Binary files differ. diff --git a/content/is-notes/src/img/backpropagation-calculation.png b/content/is-notes/src/img/backpropagation-calculation.png Binary files differ. diff --git a/content/is-notes/src/img/backpropagation.png b/content/is-notes/src/img/backpropagation.png Binary files differ. diff --git a/content/is-notes/src/img/bayes-calculation.png b/content/is-notes/src/img/bayes-calculation.png Binary files differ. diff --git a/content/is-notes/src/img/bayesian-topology.png b/content/is-notes/src/img/bayesian-topology.png Binary files differ. diff --git a/content/is-notes/src/img/boolean-satisfiability.png b/content/is-notes/src/img/boolean-satisfiability.png Binary files differ. diff --git a/content/is-notes/src/img/cross-validation.png b/content/is-notes/src/img/cross-validation.png Binary files differ. diff --git a/content/is-notes/src/img/curve-fitting.png b/content/is-notes/src/img/curve-fitting.png Binary files differ. diff --git a/content/is-notes/src/img/decision-making.png b/content/is-notes/src/img/decision-making.png Binary files differ. diff --git a/content/is-notes/src/img/derivative-rules.png b/content/is-notes/src/img/derivative-rules.png Binary files differ. diff --git a/content/is-notes/src/img/design-matrix.png b/content/is-notes/src/img/design-matrix.png Binary files differ. diff --git a/content/is-notes/src/img/environment-types.png b/content/is-notes/src/img/environment-types.png Binary files differ. diff --git a/content/is-notes/src/img/error-graph.png b/content/is-notes/src/img/error-graph.png Binary files differ. diff --git a/content/is-notes/src/img/error-surface.png b/content/is-notes/src/img/error-surface.png Binary files differ. diff --git a/content/is-notes/src/img/exist-instant.png b/content/is-notes/src/img/exist-instant.png Binary files differ. diff --git a/content/is-notes/src/img/feature-model-space.png b/content/is-notes/src/img/feature-model-space.png Binary files differ. diff --git a/content/is-notes/src/img/feature-space.png b/content/is-notes/src/img/feature-space.png Binary files differ. diff --git a/content/is-notes/src/img/feedforward.png b/content/is-notes/src/img/feedforward.png Binary files differ. diff --git a/content/is-notes/src/img/fuzzy-composition.png b/content/is-notes/src/img/fuzzy-composition.png Binary files differ. diff --git a/content/is-notes/src/img/games-chance.png b/content/is-notes/src/img/games-chance.png Binary files differ. diff --git a/content/is-notes/src/img/knn.png b/content/is-notes/src/img/knn.png Binary files differ. diff --git a/content/is-notes/src/img/logical-rewriting-rules.png b/content/is-notes/src/img/logical-rewriting-rules.png Binary files differ. diff --git a/content/is-notes/src/img/loss-plot.png b/content/is-notes/src/img/loss-plot.png Binary files differ. diff --git a/content/is-notes/src/img/loss-surface.png b/content/is-notes/src/img/loss-surface.png Binary files differ. diff --git a/content/is-notes/src/img/ml-vs-dl.png b/content/is-notes/src/img/ml-vs-dl.png Binary files differ. diff --git a/content/is-notes/src/img/modifiers-hedges.png b/content/is-notes/src/img/modifiers-hedges.png Binary files differ. diff --git a/content/is-notes/src/img/neurons-vs-nn.png b/content/is-notes/src/img/neurons-vs-nn.png Binary files differ. diff --git a/content/is-notes/src/img/perceptron.png b/content/is-notes/src/img/perceptron.png Binary files differ. diff --git a/content/is-notes/src/img/pretraining.png b/content/is-notes/src/img/pretraining.png Binary files differ. diff --git a/content/is-notes/src/img/search-alg-summary.png b/content/is-notes/src/img/search-alg-summary.png Binary files differ. diff --git a/content/is-notes/src/img/sound-rules-inference.png b/content/is-notes/src/img/sound-rules-inference.png Binary files differ. diff --git a/content/is-notes/src/img/univ-instant.png b/content/is-notes/src/img/univ-instant.png Binary files differ. diff --git a/content/is-notes/src/index.wiki b/content/is-notes/src/index.wiki @@ -1,123 +0,0 @@ -= Intelligent Systems = - -core topics: - * search & heuristics - * knowledge - * adaptivity - -{{file:img/decision-making.png|Decision making diagram}} - -Table of contents: - * [[/assessment-info|Assessment information]] - * [[/state-space-repr-intro#State Space Representations Intro|State Space Representations Intro]] - * [[/state-space-search#State space search|State space search]] - * [[/state-space-search#State space search#Uninformed search strategies|Uninformed search strategies]] - * [[/state-space-search#State space search#Uninformed search strategies#Breadth-first (BF) search|Breadth-first (BF) search]] - * [[/state-space-search#State space search#Uninformed search strategies#Depth-first (DF) search|Depth-first (DF) search]] - * [[/state-space-search#State space search#Uninformed search strategies#Depth-limited search|Depth-limited search]] - * [[/state-space-search#State space search#Uninformed search strategies#Iterative deepening search|Iterative deepening search]] - * [[/state-space-search#State space search#Informed search (heuristics)|Informed search (heuristics)]] - * [[/state-space-search#State space search#Informed search (heuristics)#A Search|A Search]] - * [[/state-space-search#State space search#Informed search (heuristics)#A* Search|A* Search]] - * [[/state-space-search#State space search#Adversarial search|Adversarial search]] - * [[/state-space-search#State space search#Adversarial search#Minimax|Minimax]] - * [[/state-space-search#State space search#Adversarial search#Minimax#Setup|Setup]] - * [[/state-space-search#State space search#Adversarial search#Minimax#Optimal strategies|Optimal strategies]] - * [[/state-space-search#State space search#Adversarial search#Minimax#Evaluation|Evaluation]] - * [[/state-space-search#State space search#Adversarial search#Reducing problems of complexity with Minimax|Reducing problems of complexity with Minimax]] - * [[/state-space-search#State space search#Adversarial search#Reducing problems of complexity with Minimax#Cutting off search:|Cutting off search:]] - * [[/state-space-search#State space search#Adversarial search#Reducing problems of complexity with Minimax#Alpha-Beta pruning (efficient Minimax)|Alpha-Beta pruning (efficient Minimax)]] - * [[/state-space-search#State space search#Adversarial search#Search with no or partial information|Search with no or partial information]] - * [[/state-space-search#State space search#Adversarial search#Search with no or partial information#Perfect information Monte Carlo sampling (rdeep)|Perfect information Monte Carlo sampling (rdeep)]] - * [[/state-space-search#State space search#Adversarial search#Games with chance|Games with chance]] - * [[/state-space-search#State space search#Summary (Schnapsen)|Summary (Schnapsen)]] - * [[/state-space-search#State space search#Search direction|Search direction]] - * [[/rational-agents#Rational agents|Rational agents]] - * [[/rational-agents#Rational agents#Agents|Agents]] - * [[/rational-agents#Rational agents#Rationality|Rationality]] - * [[/rational-agents#Rational agents#Task environments|Task environments]] - * [[/rational-agents#Rational agents#Agent types|Agent types]] - * [[/rational-agents#Rational agents#Agent types#Simple Reflex|Simple Reflex]] - * [[/rational-agents#Rational agents#Agent types#Reflex & State|Reflex & State]] - * [[/rational-agents#Rational agents#Agent types#Goal-Based|Goal-Based]] - * [[/rational-agents#Rational agents#Agent types#Learning|Learning]] - * [[/logical-agents#Logical agents|Logical agents]] - * [[/logical-agents#Logical agents#What is logic|What is logic]] - * [[/logical-agents#Logical agents#Syntax|Syntax]] - * [[/logical-agents#Logical agents#Syntax#Propositional logic (PL)|Propositional logic (PL)]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)|First order logic (FOL)]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Basic elements:|Basic elements:]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Sentences|Sentences]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Quantification|Quantification]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Quantification#Universal quantification|Universal quantification]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Quantification#Existential quantification|Existential quantification]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Quantification#Quantifier Duality|Quantifier Duality]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Decidability vs undecidability|Decidability vs undecidability]] - * [[/logical-agents#Logical agents#Syntax#First order logic (FOL)#Knowledge engineering in FOL|Knowledge engineering in FOL]] - * [[/logical-agents#Logical agents#Syntax#Choice of formalisms|Choice of formalisms]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL|Propositionalising FOL]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Reduction to propositional inference|Reduction to propositional inference]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Universal instantiation (UI):|Universal instantiation (UI):]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Existential instantiation (EI):|Existential instantiation (EI):]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Applying in Schnapsen - Strategies (examples)|Applying in Schnapsen - Strategies (examples)]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Applying in Schnapsen - Strategies (examples)#Play Jack|Play Jack]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Applying in Schnapsen - Strategies (examples)#Play cheap|Play cheap]] - * [[/logical-agents#Logical agents#Syntax#Propositionalising FOL#Applying in Schnapsen - Strategies (examples)#Play trump marriage|Play trump marriage]] - * [[/logical-agents#Logical agents#Semantics|Semantics]] - * [[/logical-agents#Logical agents#Semantics#Interpretations & Models|Interpretations & Models]] - * [[/logical-agents#Logical agents#Semantics#Entailment|Entailment]] - * [[/logical-agents#Logical agents#Semantics#Truth|Truth]] - * [[/logical-agents#Logical agents#Semantics#Validity|Validity]] - * [[/logical-agents#Logical agents#Semantics#Satisfiability|Satisfiability]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)|Calculus (algorithms for inference)]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Properties of inference|Properties of inference]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods|Proof methods]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search|Model checking & search]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#Truth Tables for inference|Truth Tables for inference]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#Effective proofs by model checking|Effective proofs by model checking]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#Clause Normal Form (CNF)|Clause Normal Form (CNF)]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#DPLL algorithm|DPLL algorithm]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#DPLL algorithm#Heuristic search in DPLL|Heuristic search in DPLL]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Model checking & search#Satisfiability modulo theory|Satisfiability modulo theory]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Rule-based reasoning|Rule-based reasoning]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Rule-based reasoning#Inference rules|Inference rules]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Rule-based reasoning#Searching for proofs|Searching for proofs]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Rule-based reasoning#Forward and backward chaining|Forward and backward chaining]] - * [[/logical-agents#Logical agents#Calculus (algorithms for inference)#Proof methods#Rule-based reasoning#Resolution|Resolution]] - * [[/probability-uncertainty#Probability and Uncertainty|Probability and Uncertainty]] - * [[/probability-uncertainty#Probability and Uncertainty#Vagueness: Fuzzy Set Theory|Vagueness: Fuzzy Set Theory]] - * [[/probability-uncertainty#Probability and Uncertainty#Vagueness: Fuzzy Set Theory#Fuzzy sets|Fuzzy sets]] - * [[/probability-uncertainty#Probability and Uncertainty#Vagueness: Fuzzy Set Theory#Fuzzy relations|Fuzzy relations]] - * [[/probability-uncertainty#Probability and Uncertainty#Vagueness: Fuzzy Set Theory#Evaluation|Evaluation]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory|Uncertainties: Probability Theory]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory#General|General]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory#Axioms of probability|Axioms of probability]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory#Joint probability distributions|Joint probability distributions]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory#Bayesian networks|Bayesian networks]] - * [[/probability-uncertainty#Probability and Uncertainty#Uncertainties: Probability Theory#Evaluation of probabilities|Evaluation of probabilities]] - - [[/machine-learning#Machine Learning|Machine Learning]] - - [[/machine-learning#Machine Learning#Learning problems|Learning problems]] - - [[/machine-learning#Machine Learning#Methodology|Methodology]] - - [[/machine-learning#Machine Learning#Methodology#Data|Data]] - - [[/machine-learning#Machine Learning#Methodology#Experimentation|Experimentation]] - - [[/machine-learning#Machine Learning#Methodology#Evaluation|Evaluation]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:|Machine Learning Steps:]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features|Choose the features]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features#Inductive learning method|Inductive learning method]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features#Classifying with naive Bayes|Classifying with naive Bayes]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features#Clustering with K-nearest neighbor|Clustering with K-nearest neighbor]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features#Linear classifier|Linear classifier]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the features#Support vector machine|Support vector machine]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the model (model search)|Choose the model (model search)]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the model (model search)#Regression|Regression]] - - [[/machine-learning#Machine Learning#Machine Learning Steps:#Choose the model (model search)#Gradient descent|Gradient descent]] - - [[/machine-learning#Machine Learning#Neural Networks|Neural Networks]] - - [[/machine-learning#Machine Learning#Neural Networks#Overview|Overview]] - - [[/machine-learning#Machine Learning#Neural Networks#Training neural networks|Training neural networks]] - - [[/machine-learning#Machine Learning#Neural Networks#Autoencoders: a NN architecture|Autoencoders: a NN architecture]] - - [[/machine-learning#Machine Learning#Neural Networks#Trying it out|Trying it out]] - - [[/machine-learning#Machine Learning#The promise of depth|The promise of depth]] - * [[/ethics#Ethics of AI|Ethics of AI]] - * [[/ethics#Ethics of AI#Sci-fi ethics (problems down the road)|Sci-fi ethics (problems down the road)]] - * [[/ethics#Ethics of AI#Today's problems|Today's problems]] - * [[/philosophy#Philosophy of AI|Philosophy of AI]] diff --git a/content/is-notes/src/logical-agents.wiki b/content/is-notes/src/logical-agents.wiki @@ -1,452 +0,0 @@ -= Logical agents = - -== What is logic == -logic: generic method to deal with partial/imperfect/implicit information - -we need: - * syntax to write statement about rules & knowledge of the game (a language) - * semantics to say what legal expressions mean, the meaning of each sentence with respect to interpretations - * calculus for how to determine meaning for legal expressions - -knowledge-based/logical agents must be able to: - * represent states & actions - * incorporate new percepts, update internal representation of world - * deduce hidden properties of the world & appropriate actions - -online/exploratory search: go to position, evaluate all options, possibly look ahead. have to re-evaluate current position. - -== Syntax == -=== Propositional logic (PL) === -assumes world contains facts - -uses proposition symbols to state these facts. - -pros: - * declarative - * allows partial/disjunctive/negated information - * is compositional - * meaning of statements is context-independent - -cons: - * very limited expressive power - -=== First order logic (FOL) === -an extension of propositional logic. - -allows variables to range over atomic symbols in the domain. - -assumes world contains: - * objects: people, houses, colors, baseball games, etc. - * relations: red, round, prime, brother of, comes between, bigger than, etc. - * functions: father of, best friend, one more than, plus, etc. - -==== Basic elements: ==== -- Constants: KingJohn, 2, UCB, ... -- Predicates: Brother, >, ... -- Functions: Sqrt, LeftLegOf, ... -- Variables: x, y, ... -- Connectives: ∧, ∨, ¬, ⇒, ⇔ - -==== Sentences ==== -{{{ -Atomic sentence = predicate (term_1,..., term_n) - or term_1 = term_2 -Term = function(term_1,..., term_n) - or constant - or variable -}}} - -Complex sentences are made from atomic sentences using connectives. - -==== Quantification ==== -===== Universal quantification ===== -∀ <variables> <sentence> - -∀x P is true in a model _m_ iff P is true with x being each possible object in the model - -(you can roughly translate that to conjunctions) - -typically used with ⇒ - -*CARE:* ∀x ∀y ≠ ∀y ∀x - -===== Existential quantification ===== -∃ <variables> <sentence> - -∃x P is true in a model _m_ iff P is true with x being some possible object in the model - -(you can roughly translate that to disjunction of instantiations of P) - -typically used with ∧ - -watch out, if you use it with ⇒, it works even if the LHS is false! - -*CARE*: ∃x ∃y ≠ ∃y ∃x - -===== Quantifier Duality ===== -each quantifier can be expressed in terms of the other - -e.g. these are the same: - * ∀x Likes(x, IceCream) -- "everyone likes ice cream" - * ¬∃x ¬Likes(x, IceCream) -- "there is nobody who doesn't like ice cream" - -==== Decidability vs undecidability ==== -undecidability - * Turing machine can calculate everything that can be calculated - * halting problem: $K := { (i,x) | \text{program i halts when run on input x})$ - -decidability - * validity of FOL is not decidable (but semi-decidable) - * if a theorem is logically entailed by an axiom, you can prove that it is. - * if not, you can't necessarily prove that it's not (because you can continue with your proof infinitely). - -==== Knowledge engineering in FOL ==== -1. Identify the task -2. Assemble relevant knowledge -3. Decide on vocabulary of predicates, functions, and constants -4. Encode general knowledge about the domain (terms that we want to use) -5. Encode description of the specific problem instance -6. Pose queries to the inference procedure and get answers - -=== Choice of formalisms === -first-order logic: represents knowledge - -propositional logic: used for reasoning ("propositionalisation") - -then use reasoner to check for entailment of propositional logic knowledge base an decision query - * Davis Putnam (DPLL) algorithm - * formulas have to be in clause normal form (CNF) - * calculus is proof by refutation: - * DPLL determines satisfiability of a KB - * entailment of KB |= a by "refutation": - * KB |= a if KB ∩ {~a} is unsatisfiable - * assume the opposite and prove it's impossible - -=== Propositionalising FOL === -==== Reduction to propositional inference ==== -every FOL KB can be propositionalised so as to preserve entailment - -if a sentence α is entailed by an FOL KB, it is entailed by a _finite_ subset of the propositionalised KB - -==== Universal instantiation (UI): ==== -every instantiation of a universally quantified sentence is entailed by it. - -{{file:img/univ-instant.png|Universal instantiation}} - -example: -{{{ -∀x King(x) ∧ Greedy(x) ⇒ Evil(x) -King(John) ∧ Greedy(John) ⇒ Evil(John) -etc. -}}} - -==== Existential instantiation (EI): ==== -{{file:img/exist-instant.png|Existential instantiation}} - -example: -{{{ -∃x Crown(x) ∧ OnHead(x,John) -Crown(C_1) ∧ OnHead(C_1, John) -}}} - -==== Applying in Schnapsen - Strategies (examples) ==== -===== Play Jack ===== - -check whether card is a jack: - -{{{ -KB |= PlayJack(x) ? -}}} - -represent strategy: - -{{{ -∀x PlayJack(x) ⇔ Jack(x) -}}} - -represent game information: - -{{{ -KB = {Jack(4), Jack(0), Jack(14), Jack(19)} -}}} - -===== Play cheap ===== -only play Jacks: check whether card is cheap - -{{{ -KB |= PlayCheap(x) ? -}}} - -represent strategy: - -{{{ -∀x PlayCheap(x) ⇔ Jack(x) ∨ Queen(x) ∨ King(x) -}}} - -represent game information: - -{{{ -KB = {Jack(4), Jack(9), Jack(14), Jack(19), Queen(5), ...} -}}} - -===== Play trump marriage ===== -{{{ -TrumpMarriage(x) ⇔ Q(x) & Trump(x) & ∃y: SameColor(x,y) & K(y) & MyCard(y) -SameColor(x,y) ⇔ (C(x) & C(y)) ∨ (D(x) & D(y)) ∨ (H(x) & H(y)) ∨ (S(x) & S(y)) -}}} - -== Semantics == -=== Interpretations & Models === -interpretation: assignment of meaning to symbols of formal language - -model: interpretation that satisfies defining axioms of knowledge base - -_m_ is a model of a sentence _α_ if _α_ holds in _m_. - -M(a) is the set of all models of a. - -each model specifies true/false for each proposition symbol (∧, ∨, ¬, ⇒, ⇐, ⇔) - -=== Entailment === -the knowledge base (KB) entails _α_: _α_ follows from the information in the knowledge base (KB |= _α_) - -KB entails _α_ iff _α_ holds in all worlds where KB is true. - -a knowledge base is the rules + observations. - -a sentence is: - * entailed by KB iff α holds in all models of KB - * valid if it is true in all models - * satisfiable if it is true in some model - * unsatisfiable if it is true in no models - -two statements are logically equivalent if they are true in same set of models: - -α ≡ β iff α |= β and β |= α - -=== Truth === -sentences are true with respect to model and interpretation. - -model contains objects and relations among them - -interpretation specifies referents for: -* constant symbols -- objects -* predicate symbols -- relations -* function symbols -- functional relations - -an atomic sentence $predicate(term_1, ..., term_n)$ is true -iff the objects referred to by $term_1,..., term_n$ -are in the relation referred to by $predicate$ - -=== Validity === -valid if it is true in all models. - -e.g. True, A ∨ ¬A, A ⇒ A, (A ∧ (A e.g. True, A ∨ ⇒ B)) ⇒ B) - -=== Satisfiability === -- satisfiable if it is true in _some_ model -- unsatisfiable if it is true in _no_ models - -== Calculus (algorithms for inference) == -=== Properties of inference === -sound: if an algorithm $|-$ only derives entailed sentences. - i.e. if KB $|-$ α also KB |= α - -complete: if an algorithm derives any sentence that is entailed. - i.e. KB |= α implies KB |- α - -a calculus terminates if it finds entailed sentences in finite time. - -a logic is _decidable_ if there is _sound and complete_ calculus that _terminates_. - -=== Proof methods === -1. Model checking and search - * truth table enumeration (exponential in n) - * improved backtracking (DPLL) - * heuristics for choosing right order -2. application of inference rules - * sound generation of new sentences from old - * proof = sequence of rule applications (actions) - -==== Model checking & search ==== -===== Truth Tables for inference ===== -enumerate interpretations and check that where KB is true, α is true. - -| $fact_1$ | $fact_2$ | $fact_3$ | $KB$ | $α$ | -|----------|----------|----------|--------|--------| -| false | false | false | false | true | -| false | false | false | false | true | -| false | true | false | _true_ | _true_ | - -algorithm: - -{{{ -for (m in truth assignments) { - if (m makes F true) return "satisfiable" -} -return "unsatisfiable" -}}} - -===== Effective proofs by model checking ===== - -Clever search (depth first, redundancy, heuristics) - -Two families of efficient algorithms for propositional inference based on model checking - * complete backtracking search algorithms -- DPLL (Davis, Putnam, Logemann, Loveland) - * incomplete local search algorithm (WalkSAT algorithm) - -===== Clause Normal Form (CNF) ===== - -memo technique: the C in CNF for _conjunction_ normal form - -A PL formula is in CNF if it is a conjunction of disjunctions of literals. - * e.g.: {{a,b}, {~a, c}, {~b, c}} - * equivalent to (a ∨ b) ∧ (~ a ∨ c) ∧ (~ b ∨ c) - -calculating CNF: - 1. Remove implications: - * (p ⇔ q) to ((p ⇒ q) ∧ (q ⇒ p)) - * (p → q) to (¬ p ∨ q) - 2. Move negations inward: - * ¬ (p ∨ q) to (¬ p ∧ ¬ q) - * ¬ (p ∧ q) to (¬ p ∨ ¬ q) - 3. Move conjunctions outward: - * (r ∨ (p ∧ q)) to ((r ∨ p) ∧ (r ∨ q)) - 4. Split up conjunctive clauses: - * ( (p1 ∨ p2) ∧ (q1 ∨ q2) ) to (p1 ∨ p2), (q1 ∨ q2) - -===== DPLL algorithm ===== - -when you have CNF, you can run the DPLL algorithm. determines if propositional logic sentence in CNF is satisfiable. - -returns true if F is satisfiable, false otherwise. - -basically assign values until contradiction, then backtrack. - -Improving DPLL: - * if a literal in a disjunction clause is true, the clause is true - * if a literal in a disjunction clause is false, the literal can be removed - * if a clause is empty, it is false - * a unit literal has to be true - * a pure literal (only appears non-negated) has to be true - -the algorithm: - -{{{ -dpll (F, literal) { - remove clauses containing literal - shorten clauses containing ¬literal - if (F contains no clauses) - return true - if (F contains empty clause) - return false - if (F contains a unit or pure literal) - return dpll(F, literal) - - choose P in F - if (dpll(F, ¬P)) - return true - - return dpll(F, P) -} -}}} - -====== Heuristic search in DPLL ====== - -used in DPLL to select proposition for branching - -idea: identify most constrained variable, likely to create many unit clauses - -MOM's heuristic: most occurrences in clauses of minimum length - -why is it better than truth table enumeration? - * early termination: clause is true if any literal is true. sentence is false if any clause is false. - * pure symbol heuristic: always appears with the same sign in all clauses, has to be true - * unit clause heuristic: only one literal in the clause, so it must be true - -proving entailment KB |= a by refutation: - 1. translate KB into CNF to get cnf(KB) - 2. translate ~a into CNF to get cnf(~a) - 3. add cnf(~a) to cnf(KB) - 4. apply DPLL until either satisfiable (model is found) or unsatisfiable (search exhausted) - 5. if satisfiable, not entailed. otherwise, entailed. - -===== Satisfiability modulo theory ===== - -Boolean satisfiability (SAT): is there an assignment to the $p_1, p_2, ..., p_n$ variables such that $\phi$ evaluates to 1? - -{{file:img/boolean-satisfiability.png|Boolean satisfiability diagram}} - -SAT vs SMT: - * SMT (satisfiability modulo theories) extend SAT solving by adding extensions. - * SMT solver can solve SAT problem, but not vice-versa. - * SMT is used in analog circuit verification, RTL, verification, and card games. - -SMT theories: - * real or integer arithmetic - * equality and uninterpreted functions - * bit vectors and arrays - * properties: - * decidable: an effective procedure exists to determine if formula is member of theory T - * often quantifier-free - * core theory: - * type boolean - * constants {TRUE, FALSE} - * functions {AND, OR, XOR, =>} - * integer theory: - * type int - * all numerals are int constants - * functions {+, -, x, mod, div, abs} - * reals theory: - * type real - * functions {+, -, x, /, <, >} - * -==== Rule-based reasoning==== -===== Inference rules ===== -inference rule: logical form consisting of function taking premises, analyzing their syntax, and returning one or more conclusions - -Modens Ponens: $\frac{\alpha\implies\beta,\;\alpha}{\beta}$ - -And-elimination: $\frac{\alpha\land\beta}{\alpha}$ - -logical equivalences used as rules: $\frac{\alpha\iff\beta}{(\alpha\implies\beta)\land(\beta\implies\alpha)}$ - -all logical equivalence rewriting rules: - -{{file:img/logical-rewriting-rules.png|Rewriting rules for logic}} - -===== Searching for proofs ===== -Finding proofs is like finding solutions to search problems. - -monotonicity: set of entailed sentences can only increase as info is added to the knowledge base. - * for any sentence α and β, - * if KB |= α, then KB ∧ β |= α - -===== Forward and backward chaining ===== -FC is data-driven, automatic, unconscious: - * derive all facts entailed by the KB - * may do lots of work irrelevant to the goal - -BC is goal-driven, appropriate for problem-solving - * specific fact entailed by the KB - * complexity of BC can be much less than linear in size of KB - -===== Resolution ===== -a rule is sound if its conclusion is evaluated to true whenever the premise is evaluated to true. - -can be shown to be sound using truth table: - -{{file:img/sound-rules-inference.png|Sound rules for inference}} - -properties resolution: - * resolution rule is sound - * resolution rule is complete (on its own) for formulas in CNF - * resolution can only decide satisfiability - -algorithm (again proof by refutation): - 1. Convert KB ∧ ¬ α into CNF - 2. Apply resolution rule to resulting clauses - 3. Continue until: - a) no new clauses can be added, hence α does not entail β - b) two clauses resolve to entail empty clause, hence α entails β - diff --git a/content/is-notes/src/machine-learning.wiki b/content/is-notes/src/machine-learning.wiki @@ -1,304 +0,0 @@ -= Machine Learning = - -design of a learning element is affected by: - * which components of performance element are to be learned - * what feedback is available to learn these components - * what representation is used for the components - -offline learning: learn based on some data, then apply results to situation - -feedback types (get input, make decision, learn based on feedback): - * supervised learning: correct answers for each example. - * only positive examples - * positive and negative examples - * unsupervised learning: no correct answers given - * semi-supervised learning: learn which questions to ask (active learning) - * reinforcement learning: occasional rewards - -{{file:img/neurons-vs-nn.png}} - -== Learning problems == - -Classification - * use: from data to discrete classes. - * examples: handwriting recognition, spam filtering, facial recognition. - -Regression - * use: predicting a numeric value - * examples: stock market, weather predictions - -Ranking - * use: comparing items - * examples: web search - -Collaborative filtering - * use: take some else's information, based on that, give prediction - * examples: recommendation systems (books, movies/shows) - -Clustering - * use: discovering structure/patterns in data - * examples: clustering images - -== Methodology == -=== Data === -labeled instances (like spam, not spam) - * training set - * held out set (e.g. for validation) - * test set (don't even look at this until you want to test your model) - -randomly allocate to data sets. - -features: attribute-value pairs characterizing each x - -=== Experimentation === -experimentation cycle: - 1. select hypothesis, tune hyperparameters on held-out/validation set - 2. compute accuracy of test set (never "peek" at test set itself) - -=== Evaluation === -accuracy -- fraction of instances predicted correctly - -Cross validation: - -{{file:img/cross-validation.png|Cross validation diagram}} - -create a confusion matrix (TODO: there's a diagram for this but not in the old slides) - -== Machine Learning Steps: == - 1. choose the features - 2. choose the model class - 3. choose a search method - -=== Choose the features === -create a feature space: features on x-y axes, points are individual data, classification would be a color scheme. - -{{file:img/feature-space.png|Feature space graph}} - - -==== Inductive learning method ==== - * construct/adjust h to agree with f (function predicting value) on training set - * h is consistent if it agrees with f on all examples - * for example, curve fitting: - - {{file:img/curve-fitting.png|Curve fitting graph}} - -Occam's razor: "one should not increase, beyond what is necessary, the number of entities required to explain anything" -basically, choose the simplest option. - -==== Classifying with naive Bayes ==== - -Binary classification -* input: email -* output: spam, not spam -* setup: - * get large collection of example emails, labeled "spam/not spam" - * someone has to hand-label that - * want to learn to predict label for new emails in future -* features: attributes used to make label decision - * words, text patterns (e.g. caps), non-text - -calculation for Bayesian classifier: $P(C|F_1,...,F_n)$ - -using Bayes' theorem: - -$P(C|F_1,...F_n)=\frac{P(C)P(F_1,...,F_n|C)}{P(F_1,...,F_n)}$ - -rewrite the numerator of the equation: - -$P(C)P(F_1,...,F_n |C) = P(C)P(F_1 | C)P(F_2 | C, F_1)P(F_3|C, F_1, F_2)P(F_4,...,F_n | C, F_1, F_2, F_3)$ - -that uses the chaining rule. but it's too computationally expensive. -so naively assume conditional independence: - -$P(F_i | C, F_j) = P(F_i | C)$ - -This simplifies the formula to: - -$P(C)P(F_1,...,F_n | C) = P(C) PI(0 to n) P(F_i | C)$ - -{{file:img/bayes-calculation.png}} - -Laplace smoothing helps with really small probabilities. -Naive Bayes often works. sometimes performs well even if the assumptions are badly violated. -classification is about predicting correct class label, _not_ about accurately estimating probabilities - -==== Clustering with K-nearest neighbor ==== -k nearest neighbor classification: find k most similar case, copy majority label - -e.g. to classify unlabeled document, find most similar document and copy label: - -{{file:img/knn.png|K-nearest neighbor example}} - -the _k_ helps get rid of noise which would lead to misclassification - -==== Linear classifier ==== -linear classifier: come up with a line that divides feature space, use that for prediction. - -works for stuff like $x \lor y$, but not if we want $x \oplus y$ or other things that are not linearly separable. - -you can build a design matrix of all the different features you want to include. here's an example with 5 different features *age, height, age², age × height, height²) that classifies a person as male/female: - -{{file:img/design-matrix.png|Design matrix}} - -if you go to more dimensions (so more features in a design matrix), you need hyperplanes. - -hyperplanes sound fancy af but it's just a line in some higher dimension. for example, this is how you would use a hyperplane in the third dimension to separate points: - -{{file:img/3d-hyperplane.png|3D hyperplane example}} - -==== Support vector machine ==== -k(x,y): "distance" function between instances x and y - -SVMs create a linear separating hyperplane - -they can embed that hyperplane into a higher dimensional domain using the kernel trick -- so long as _k_ is a kernel, you don't have to explicitly compute the design matrix (that drastically reduces the computation) - -try to achieve a good margin -- a large separation from the line for both classes (so reduce the blur between two classes, make a clear distinction). - -watch out for over-fitting -- you might end up with the model being trained extremely specifically to your data. - -=== Choose the model (model search) === - -so we have a lot of ways to put a line on a graph. but how do you choose the right one? - -==== Regression ==== -train a learner to produce a model (the model is the line/hyperplane). then you give the model a new instance, and it produces a new value based on a function. - -assign a value for each of the points in the feature space. - -evaluating regression -- what's a good model for a regression? - -you use an error function (the difference between predicted and real values, square to avoid negatives): - -$error(p) = \sum_i (f_p (x_i) - y_i)^2$ - -{{file:img/error-graph.png|Error graph}} - -in this example, each of the possible lines is represented by two parameters (s the slope, b the y-intercept), in the left graph. those parameters can be plotted on 2D axes, on the right graph. - -{{file:img/feature-model-space.png|Feature and model space}} - -Then you can take those points in the right graph, and plot their respective error rates (from the error function above) on the z axis, so you end up with a 3D graph -- an error surface: - -{{file:img/error-surface.png|Error surface}} - -now the point is to find the one with the lowest error (the lowest point in the surface, colored green). and that's what calculus is for, specifically differentiation. - -if you've never done calculus, it's not easy to explain, but basically taking the derivative means you're looking for the slope of a certain function at some point in that function. if you set the derivative to zero, you're looking for the point where the slope is zero -- specifically the minimum or maximum of a function. - -quick example: if you have a function $y = x^2 + 2$, there's a minimum at x = 0. you may know that by intuition, but you can also take the first derivative ($y' = 2x$), set $y'$ equal to zero, and solve for x -- you'll get the same result. it's trivial with a simple function, but once you get into cubic and quartic functions, you can't really do it by intuition.. - -so a derivative $f'(x)$ of a function $f(x)$ gives the slope of $f(x)$ at any point in the domain (where $f(x)$ has a value $y$). - -the rules for taking derivatives (don't need to memorize these, they will be provided on the exam): - -{{file:img/derivative-rules.png|Derivative rules}} - -the problems: - * not all derivatives that we find can be resolved to zero - * and we also have to consider that this can be in higher dimensions - -==== Gradient descent ==== -you use a variant of the hill climbing algorithm - -the steps: - 1. pick random parameters s (slope), b (intercept) - 2. repeat: - 1. compute the gradient - 2. move a small step in the opposite direction - -but there may be multiple zero points -- local optima. there's no guarantee of convergence. - -== Neural Networks == -=== Overview === -the difference between original machine learning and deep learning: - -{{file:img/ml-vs-dl.png}} - -the original perceptron: - * binary classifier - * bias node, always set to 1 - * n inputs for each feature, with weights - * $y=w_1 x_1 _ w_2 x_2 + b$ - -but chaining doesn't make it more interesting, the function collapses to a linear one - -{{file:img/perceptron.png}} - -So introduce an activation function instead of using a standard linear calculation. This puts the values in a certain range, and now the diagram looks like this: - -{{file:img/activation-functions.png}} - -Then you can build a feed-forward network with hidden layers between input and output: - -{{file:img/feedforward.png}} - - -=== Training neural networks === -Loss function determines how close a given network is to being correct for an input. -If you plot neural networks on x-y, and the amount of loss on z axis, you end up with a loss surface. Then you want to find a point in that surface where the loss is the lowest. - -{{file:img/loss-plot.png}} -{{file:img/loss-surface.png}} - -You can find the low point in the error surface with gradient descent (differentiation). - -Stochastic gradient descent: - 1. pick random weights w - 2. loop: - * $w = w - r \triangledown loss (w)$ - -where r is the learning rate. make sure to pick a good learning rate because if it's too high (like 0.1), it will be inaccurate, while if it's too low, it will take a long time. - -so in summary: - * get examples of input and output - * get a loss function - * work out the gradient of loss with respect to the weights - * use (stochastic) gradient descent to slowly improve the weights - -how do you calculate the gradient for complex data? - * symbolically? too computationally expensive - * numerically? too unstable, also expensive - * so settle for a middle ground -- backpropagation - -backpropagation: if the system is a composition of modules, the gradient is the product of the gradient of each module with respect to its arguments - * break computation down into chain of modules - * work out derivative of each module with respect to its input (_symbolically_) - * compute the gradient for a given input by multiplying these gradients for the current input - -{{file:img/backpropagation.png}} - -for a given input x, you do a forward pass (calculating the value for each part), then fill in into final calculation. - -so like this, with x = 0: - -{{file:img/backpropagation-calculation.png}} - -neural networks are just a way of thinking about differentiable computation. - -=== Autoencoders: a NN architecture === -bottleneck architecture: - -{{file:img/autoencoder-architecture.png}} - -input should be as close as possible to the output. but it must pass through a small representation - -autoencoders map data to a _latent representation_ - -=== Trying it out === -* code: https://github.com/pbloem/machine-learning/blob/master/code-samples/autoencoder/autoencoder.py -* setup: https://docs.google.com/document/d/1-LXG5Lb76xQy70W2ZdannnYMEXRLt0CsoiaK0gTkmfY/edit?usp=sharing - -== The promise of depth == -if you have many dimensions, the gradient isn't as easy to detect anymore. there's a huge number of parameters. - -solutions: - * Pretraining (no pre-classification by humans) - * train the network on itself in hidden layers - * similar to the autoencoder idea - * you can then stack the autoencoders (hidden layers) - - {{file:img/pretraining.png|Pretraining}} - - * Pruning the network - * convolutional neural network: combine multiple input nodes into one node of a hidden layer diff --git a/content/is-notes/src/philosophy.wiki b/content/is-notes/src/philosophy.wiki @@ -1,42 +0,0 @@ -= Philosophy of AI = -what is intelligence? - * classically, you test this using the Turing Test - * interrogation game - * interrogate two parties, the goal of both parties is to convince the interrogator that they are human - * if the interrogator can't tell who is the human, the computer is intelligent - * the objections: - * the test is subjective - * why are we basing intelligence on _human_ intelligence? metaphor with flight, we only managed to get off the ground once we stopped imitating natural flight - -intelligence is everything a computer can't do yet. - -can a computer be intelligent? - * substitution argument: if you replace one neuron at a time with a computer chip in the human brain, you would eventually change into a computer, without your conscience or thought process changing at any point. - * medium argument: no. "carbohydrate racism", there's something special about carbohydrates that allows us to do stuff that computers can't do. - * formal systems argument: no. mathematical systems are inherently limited in some way; since computers are just formal systems, therefore they inherently have some limitations. we are not formal systems (that's debatable) so we do not have those limitations. - * symbol-grounding: learning systems manipulate symbols - * symbols can only refer to other symbols, so how can a computer ever know what's "red", "heavy", "sad" in the 'real' world? - * so simulated intelligence ≠ real intelligence - * thought experiment - the Chinese Room: - * a room with Chinese symbols coming in - * there's one person inside that uses a book to translate Chinese symbols to other symbols - * there's nothing in this system that understands Chinese - -Mind-body problem: - * we have the physical body, and metaphysical thoughts - * what could be the relationship between the physical and the metaphysical? - * opinions: - * mind-body dualism, interactionism: we consist of two parts (physical _and_ metaphysical) -- Descartes - * materialism: the mind and body is one thing - * gradualism: we evolved the mind (intelligence, consciousness) over time - -Intentional stance: - * intelligence/consciousness is "attributed" and "gradual" - * so the question isn't "will computers ever be conscious?", but rather "will we ever use consciousness-related words to describe them?" - * if it's useful to talk about consciousness, motivation, feeling, etc., then we are allowed to (or should) do so equally for both humans and machines - * people have a strong tendency to take the intentional stance, so we will _call_ our computers "intelligent" - -Free will: - * reasons why it can't be true: - * physics is deterministic, you can predict the next states, so your brain doesn't _physically_ allow free will - * inconsistent with psychology and neuroscience -- motor areas begin activity 2 seconds before we think we want to do something ([[https://www.youtube.com/watch?v=IQ4nwTTmcgs|Libet's experiment]]) diff --git a/content/is-notes/src/probability-uncertainty.wiki b/content/is-notes/src/probability-uncertainty.wiki @@ -1,120 +0,0 @@ -= Probability and Uncertainty = -one often has to deal with info that is underspecified, incomplete, vague, etc. - -logic by itself is not sufficient for these problems. - -== Vagueness: Fuzzy Set Theory == -model theory often based on set theory - -fuzzy set theory allows something to be _to some degree_ an element of a set - -dominant approach to vagueness (mostly because wtf else can you do) - -=== Fuzzy sets === - * universe U, object x ∈ U - * membership function for fuzzy set A is defined to be function $f_A$ from U to [0,1]: - * $f_A(x)=y$: x is a member of A to degree y - * $f_A(x)=1$: x is certainly member of A - * $f_A(x)=0$: x is certainly not a member of A - * ${x | f_A(x)>0}$: support of A - -modifiers (hedges) - -{{file:img/modifiers-hedges.png|Example of modifiers' effects on graphs}} - -operations on fuzzy sets: - * complement: $f_{\sim{A}}(x)=1-f_A(x)$ - * union: $f_{A\cup B}(x)=\max(f_A(x),f_B(x))$ - * intersection: $f_{A\cap B}(x)=\min(f_A(x), f_B(x))$ - * subset: $A\subset B \iff \forall{x}(f_A(x)\leq f_B(x))$ - -semantics -- multivalued fuzzy logic - * v(¬ A) = 1-v(A) - * v(A ∨ B) = max(v(A), v(B)) - * v(A ∧ B) = min(v(A), v(B)) - * v(A → B) = min(1, 1 - v(A) + v(B)) - -=== Fuzzy relations === -fuzzy sets can denote fuzzy relations between objects. e.g. approximately equal, close to, much larger than, etc. - -fuzzy composition: - -$f_{R \circ S} (\langle x,z\rangle ) = \max_{y \in Y} \min(f_R (\langle x,y\rangle ), f_S (\langle y,z\rangle ))$ - -hands-on example: - -{{file:img/fuzzy-composition.png|Fuzzy composition table}} - -=== Evaluation === - * good -- flexible, coincides with classical set theory, sever successful applications of fuzzy control - * bad -- requires many arbitrary choices, tends to blur differences between probabilistic uncertainty/ambiguity/vagueness - -== Uncertainties: Probability Theory == -=== General === -main interpretations of probability theory: - * optivist (frequentist) probability - * frequentism: probability is only property of repeated experiments - * probability of event: limit of _relative frequency_ of occurrence of event, as number of repetitions goes to infinity - * subjective probability - * Bayesianism: probability is an expression of our uncertainty and beliefs - * probability of event: _degree of belief_ of idealized rational individual - -sample space Ω: set of single outcomes of experiment - -event space E: things that have probability (subsets of sample space). if sample space is finite, event space is usually power set. - -=== Axioms of probability === -for any event A, B: - * $0 \leq P(A) \leq 1$ - * $P(\Omega) = 1$ - * $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ - -can derive: - * $P({}) = 0$ - * $P(\Omega) = 1$ - * $\text{if} A \subset B, P(A) \leq P(B)$ - -conditional probability ("A given B"): - -$P(A|B) = \frac{P(A \cap B)}{P(B)}$ - -=== Joint probability distributions === -for a set of random variables, it gives probability of every atomic even on those random variables. - -e.g. P(Toothache, Catch, Cavity): - -| | toothache | > | ¬ toothache | > | -|----------|-----------|---------|-------------|---------| -| | catch | ¬ catch | catch | ¬ catch | -| cavity | 0.108 | 0.012 | 0.072 | 0.008 | -| ¬ cavity | 0.015 | 0.064 | 0.144 | 0.576 | - -inference by enumeration: - * for any proposition Φ, sum atomic events where it's true -- $P(\Phi) = \sum_{\omega : \omega \models \Phi} P(\omega)$ - * compute conditional probability by selecting cells -- e.g. for P(¬ cavity | toothache), select toothache column and (¬ cavity) cells - -use Bayes' rule for opposite conditionals (like finding P(disease | symptom) from P(symptom | disease)) - -=== Bayesian networks === -simple graphical notation for - * conditional independence assertions - * compact specification of full joint distributions - -syntax: - * set of nodes, one per variable - * directed acyclic graph, with a link meaning "directly influences" - * conditional distribution for each node given its parents -- $P(X_i | Parents(X_i))$ - -topology example: - -{{file:img/bayesian-topology.png|Bayesian network topology}} - -what does it mean? - * _weather_ is independent of other variables - * _toothache_ and _catch_ are conditionally independent given _cavity_. - -=== Evaluation of probabilities === - * good -- sound theoretical basis, can be extended to decision-making, some good tools available - * bad -- not always computationally easy, need lots of data which may be hard to get - - diff --git a/content/is-notes/src/rational-agents.wiki b/content/is-notes/src/rational-agents.wiki @@ -1,70 +0,0 @@ -= Rational agents = - -"A rational agent chooses whichever action maximizes the expected value of the performance measure given the percept sequence to date and prior environment knowledge." - -== Agents == -agent function maps percept sequence to actions ($f: P* \rightarrow A$) - -function is internally represented by agent program - -program runs on physical architecture to produce f - -== Rationality == -what is rational at a specific time depends on: - * expected value of performance measure -- heuristics - * actions and choices -- search - * percept sequence to date -- learning - * prior environment-- KR - -rationality is not omniscience or perfection - -== Task environments == - -to design rational agent, we must specify environment (PEAS): - * performance: safety, destination, profits, legality, comfort - * environment: streets, traffic, pedestrians, weather - * actuators: steering, accelerating, brake, horn, speaker/display - * sensors: video, sonar, speedometer, etc. - -environment types: - * observable: fully (can detect all relevant aspects with sensors) or partially - * deterministic: (yes or no) - * static: (yes, no, semi) - * discrete: (yes or no) - * single-agent: (yes or no) - -{{file:img/environment-types.png|Environment types table}} - -For Schnapsen: - * observable: not fully - * deterministic: yes - * static: yes - * discrete: yes - * single-agent: no - -== Agent types == - -=== Simple Reflex === -select action on basis of _only the current percept_ - -large reduction in possible percept/action situations - -implemented using condition-action rules - -only works if environment is fully observable, otherwise may result in infinite loops. - -=== Reflex & State === -to tackle partially observable environments, maintain internal state - -over time, update state using world knowledge. - -=== Goal-Based === -agent needs a goal to know the desirable situations - -future is taken into account - -=== Learning === -teach agents instead of instructing them - -very robust toward initially unknown environments. - diff --git a/content/is-notes/src/state-space-repr-intro.wiki b/content/is-notes/src/state-space-repr-intro.wiki @@ -1,22 +0,0 @@ -= State Space Representations Intro = - * real world is complex, state space must be _abstracted_ for problem solving - * abstract states map to sets of real states - * abstract action maps to combination of real actions - * abstract solution = set of real paths that are solutions in real world - * there may be multiple different state space representations - -Problem-solving agent uses this representation: - 1. what are actions to move between states? - 2. what are appropriate states & initial states? - 3. what is the cost of an action? - 4. goal: what are the successful world states? - 5. search: determine possible sequences of actions leading to goal, choose 'best' sequence - 6. execute: give solution, perform actions - -State space representation (example - vacuum cleaner): - * start with real-life problem - * formulate abstract problem (states, actions) - * formulate concrete (clean house) & algorithmic goal (be in state 7 and 8) - * find solution (sequence of actions to get to state 7 or 8) - * execute plan (clean house according to abstract solution) - diff --git a/content/is-notes/src/state-space-search.wiki b/content/is-notes/src/state-space-search.wiki @@ -1,222 +0,0 @@ -= State space search = -How do we find the solutions of previous problems? - * search the state space - * search through explicit tree generation: root is initial state, nodes/leaves generated through successor function - * search generates a graph - -state: representation of a physical configuration - -node: data structure in the search tree. it contains state, parent node, actions, etc. - -== Uninformed search strategies == -strategy defines picking order of node expansion - -uninformed methods: only use problem definition - -informed methods: use heuristic function to estimate cost of solution - -evaluating performance: - * does it always find a solution if there is one? (completeness) - * does it find least-cost solution? (optimality) - * how many nodes generated/expanded? (time complexity) - * how many nodes are stored in memory during search? (space complexity) - * complexity measured in terms of: - * b: max branching factor of search tree) - * d: depth of least cost solution - * m: max depth of state space, could be infinite - * time/space complexity measured in terms of max branching factor of search tree, depth of least cost solution, max depth of state space (could be infinite) - -{{file:img/search-alg-summary.png|Summary of uninformed search algorithms}} - -=== Breadth-first (BF) search === - * algorithm: - * expand shallowest unexpanded node - * implementation - fringe (nodes that have to be explored) is a FIFO queue - * evaluation: - * completeness: yes, if branching factor b is finite - * time complexity: if every state has b successors, and solution is at depth d, then $O(b^{d+1})$ because of number of nodes generated - * space complexity: shitty if every node has to be in memory - $O(b^{d+1})$ - * optimality: in general yes, unless actions have different cost - * memory requirements are bigger problem than execution time - -=== Depth-first (DF) search === - * algorithm: - * expand deepest unexpanded node - * implementation: fringe is a stack - * evaluation: - * completeness: no, unless search space is finite and no loops are possible - * time complexity: shitty if m is larger than d (depth of optimal solution) -- $O(b^m)$. but if many solutions, faster than BF - * space complexity: backtracking search uses less memory, one successor instead of all b -- $O(bm+1)$ - * optimality: no, same issues as completeness - -=== Depth-limited search === - * DF-search with depth limit l (nodes at depth l have no successors) - * solves infinite-path problem - * evaluation: - * time: $O(b^l)$ - * space: $O(bl)$ - * completeness: not if l < d - * optimality: not if if l > d - -=== Iterative deepening search === - * strategy to find best depth limit l - * often used in combination with DF search - * after each iteration, throw away everything and increase depth limit - * combines benefits of DF (space complexity) and BF search (time complexity) - * evaluation: - * completeness: yes (no infinite paths) - * time: $O(b^d)$ - * space: $O(bd)$ - -== Informed search (heuristics) == - -Heuristic function: "educated guess that reduces/limits search for solutions" - -informedness property of heuristics: - * two heuristics $h_1(n),\; h_2(n)$ with $0 \leq h_1(n) \leq h_2(n) \leq h*(n)$ - * then $h_2(n)$ is more informed than $h_1(n)$ - * with $h_1$ fewer nodes have to be searched with $h_2$ - * but $h_2$ is often more expensive to calculate - * perfect heuristics: $h(n) = h*(n)$ - * trivial heuristics: $h(n) = 0$ - -Best-first search - * the general approach of informed search - * node selected for expansion based on _evaluation function f(n)_ - * evaluation function measures distance to goal, choose node which appears best - * fringe is queue in order of decreasing desirability - -=== A Search === -best-known form of best-first search - -avoid expanding paths that are already expensive - -evaluation function: $f(n) = g(n) + h(n)$ - * g(n) the cost so far to reach node n - * h(n) estimated cost to get from node n to goal - * f(n) estimated total cost of path through node n to goal - -=== A* Search === - -A search, but with an admissible heuristic - * heuristic is admissible if it _never_ overestimates the cost to get to goal - * admissible heuristics are optimistic - * formally: $h(n) \leq h*(n)$ where $h*(n)$ is true cost from n to goal - -evaluation: - * complete: yes - * time: exponential with path length - * space: all nodes are stored - * optimal: yes - -== Adversarial search == -search has no adversary, solution is a (heuristic) method for finding a goal - -games have an adversary, solution is a strategy. time limits force an _approximate_ solution. - -you need a function to evaluate the "goodness" of a game position - -types of games: - -| | deterministic | chance | -|-----------------------|------------------------------|-------------------------------------| -| perfect information | chess, checkers, go, othello | backgammon, monopoly | -| imperfect information | | bridge poker, scrabble, nuclear war | - -=== Minimax === - -==== Setup ==== -two players: MAX, MIN - -MAX moves first, take turns until game is over. winner gets award, loser gets penalty. - -how does this relate to search? - * initial state: game configuration e.g. with chess - * successor function: list of <move, state> pairs with legal moves - * terminal test: game finished? - * utility function: numerical value of terminal states (win +1, lose -1, draw 0) - * MAX uses search tree to determine next move - -==== Optimal strategies ==== - -find contingent strategy for MAX assuming infallible MIN. - -assume that both players play optimally. - -given game tree, optimal strategy can be found with minimax value of each node: - -{{{ - minimax(n) = utility(n) if n is a terminal - minimax(max(successors of n)) if n is a max node - minimax(min(successors of n)) if n is a min node -}}} - -==== Evaluation ==== -- complete: yes -- time: $O(b^m)$ -- space: $O(bm)$ -- optimal: yes - -=== Reducing problems of complexity with Minimax=== - -==== Cutting off search: ==== -instead of `if TERMINAL(state) then return UTILITY(state)` do `if CUTOFF-TEST(state, depth) then return EVAL(state)` - -this introduces fixed-limit depth. also loses completeness! - -utility: value based on quality of state - -heuristics: value based on estimation of quality of state - -heuristic EVAL: - * produces estimate of expected utility of a game from a given position - * should order terminal nodes in same way as utility - * computation shouldn't take too long - -==== Alpha-Beta pruning (efficient Minimax) ==== - -with minimax, the number of states is exponential to number of moves - -so, don't examine every node and prune the subtrees you don't have to examine - -Alpha: value of best MAX choice so far - -Beta: value of best MIN choice so far - -you prune the rest of the level if, at any point, beta <= alpha. - -pruning doesn't affect final results, entire subtrees can be pruned - -good move ordering improves effectiveness of pruning - -with 'perfect ordering', time complexity is: $O(b^{m/2})$ - -=== Search with no or partial information === - -problems: - * contingency: percepts provide new info - * exploration: when states/actions of environment are unknown - * sensorless/conformant: agent may have no idea where it is - -==== Perfect information Monte Carlo sampling (rdeep) ==== -1. rollout: - * assume a belief state (with perfect info) - * play random game in that state. -2. average the rollouts -3. choose one with max average - -=== Games with chance === -{{file:img/games-chance.png|Games with chance}} - -== Summary (Schnapsen) == -Phase 2: minimax & alpha-beta pruning - -Phase 1: PIMC sampling - -what next? give the agent information about the game - -== Search direction == -Data-driven: start with initial state (e.g. a maze) - -Goal-driven: start with goal state, but has bigger branching factor (TODO confirm this) - diff --git a/content/is-notes/state-space-repr-intro.html b/content/is-notes/state-space-repr-intro.html @@ -1,78 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<link rel="Stylesheet" type="text/css" href="style.css"> -<title>state-space-repr-intro</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="State Space Representations Intro"><h1 id="State Space Representations Intro">State Space Representations Intro</h1></div> -<ul> -<li> -real world is complex, state space must be <em>abstracted</em> for problem solving - -<ul> -<li> -abstract states map to sets of real states - -<li> -abstract action maps to combination of real actions - -<li> -abstract solution = set of real paths that are solutions in real world - -</ul> -<li> -there may be multiple different state space representations - -</ul> - -<p> -Problem-solving agent uses this representation: -</p> -<ol> -<li> -what are actions to move between states? - -<li> -what are appropriate states & initial states? - -<li> -what is the cost of an action? - -<li> -goal: what are the successful world states? - -<li> -search: determine possible sequences of actions leading to goal, choose 'best' sequence - -<li> -execute: give solution, perform actions - -</ol> - -<p> -State space representation (example - vacuum cleaner): -</p> -<ul> -<li> -start with real-life problem - -<li> -formulate abstract problem (states, actions) - -<li> -formulate concrete (clean house) & algorithmic goal (be in state 7 and 8) - -<li> -find solution (sequence of actions to get to state 7 or 8) - -<li> -execute plan (clean house according to abstract solution) - -</ul> - -</body> -</html> diff --git a/content/is-notes/state-space-repr-intro.md b/content/is-notes/state-space-repr-intro.md @@ -0,0 +1,25 @@ ++++ +title = "State Space Representations Intro" ++++ +# State Space Representations Intro +* real world is complex, state space must be _abstracted_ for problem solving + * abstract states map to sets of real states + * abstract action maps to combination of real actions + * abstract solution = set of real paths that are solutions in real world +* there may be multiple different state space representations + +Problem-solving agent uses this representation: +1. what are actions to move between states? +2. what are appropriate states & initial states? +3. what is the cost of an action? +4. goal: what are the successful world states? +5. search: determine possible sequences of actions leading to goal, choose 'best' sequence +6. execute: give solution, perform actions + +State space representation (example - vacuum cleaner): +* start with real-life problem +* formulate abstract problem (states, actions) +* formulate concrete (clean house) & algorithmic goal (be in state 7 and 8) +* find solution (sequence of actions to get to state 7 or 8) +* execute plan (clean house according to abstract solution) + diff --git a/content/is-notes/state-space-search.html b/content/is-notes/state-space-search.html @@ -1,573 +0,0 @@ -<!DOCTYPE html> -<html> -<head> -<link rel="Stylesheet" type="text/css" href="style.css"> -<script type="text/javascript" async src="https://cdn.jsdelivr.net/gh/mathjax/MathJax@2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -<title>state-space-search</title> -<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> -</head> -<body> - -<div id="State space search"><h1 id="State space search">State space search</h1></div> -<p> -How do we find the solutions of previous problems? -</p> -<ul> -<li> -search the state space - -<li> -search through explicit tree generation: root is initial state, nodes/leaves generated through successor function - -<li> -search generates a graph - -</ul> - -<p> -state: representation of a physical configuration -</p> - -<p> -node: data structure in the search tree. it contains state, parent node, actions, etc. -</p> - -<div id="State space search-Uninformed search strategies"><h2 id="Uninformed search strategies">Uninformed search strategies</h2></div> -<p> -strategy defines picking order of node expansion -</p> - -<p> -uninformed methods: only use problem definition -</p> - -<p> -informed methods: use heuristic function to estimate cost of solution -</p> - -<p> -evaluating performance: -</p> -<ul> -<li> -does it always find a solution if there is one? (completeness) - -<li> -does it find least-cost solution? (optimality) - -<li> -how many nodes generated/expanded? (time complexity) - -<li> -how many nodes are stored in memory during search? (space complexity) - -<li> -complexity measured in terms of: - -<ul> -<li> -b: max branching factor of search tree) - -<li> -d: depth of least cost solution - -<li> -m: max depth of state space, could be infinite - -</ul> -<li> -time/space complexity measured in terms of max branching factor of search tree, depth of least cost solution, max depth of state space (could be infinite) - -</ul> - -<p> -<img src="img/search-alg-summary.png" alt="Summary of uninformed search algorithms" /> -</p> - -<div id="State space search-Uninformed search strategies-Breadth-first (BF) search"><h3 id="Breadth-first (BF) search">Breadth-first (BF) search</h3></div> -<ul> -<li> -algorithm: - -<ul> -<li> -expand shallowest unexpanded node - -<li> -implementation - fringe (nodes that have to be explored) is a FIFO queue - -</ul> -<li> -evaluation: - -<ul> -<li> -completeness: yes, if branching factor b is finite - -<li> -time complexity: if every state has b successors, and solution is at depth d, then \(O(b^{d+1})\) because of number of nodes generated - -<li> -space complexity: shitty if every node has to be in memory - \(O(b^{d+1})\) - -<li> -optimality: in general yes, unless actions have different cost - -</ul> -<li> -memory requirements are bigger problem than execution time - -</ul> - -<div id="State space search-Uninformed search strategies-Depth-first (DF) search"><h3 id="Depth-first (DF) search">Depth-first (DF) search</h3></div> -<ul> -<li> -algorithm: - -<ul> -<li> -expand deepest unexpanded node - -<li> -implementation: fringe is a stack - -</ul> -<li> -evaluation: - -<ul> -<li> -completeness: no, unless search space is finite and no loops are possible - -<li> -time complexity: shitty if m is larger than d (depth of optimal solution) -- \(O(b^m)\). but if many solutions, faster than BF - -<li> -space complexity: backtracking search uses less memory, one successor instead of all b -- \(O(bm+1)\) - -<li> -optimality: no, same issues as completeness - -</ul> -</ul> - -<div id="State space search-Uninformed search strategies-Depth-limited search"><h3 id="Depth-limited search">Depth-limited search</h3></div> -<ul> -<li> -DF-search with depth limit l (nodes at depth l have no successors) - -<li> -solves infinite-path problem - -<li> -evaluation: - -<ul> -<li> -time: \(O(b^l)\) - -<li> -space: \(O(bl)\) - -<li> -completeness: not if l < d - -<li> -optimality: not if if l > d - -</ul> -</ul> - -<div id="State space search-Uninformed search strategies-Iterative deepening search"><h3 id="Iterative deepening search">Iterative deepening search</h3></div> -<ul> -<li> -strategy to find best depth limit l - -<li> -often used in combination with DF search - -<li> -after each iteration, throw away everything and increase depth limit - -<li> -combines benefits of DF (space complexity) and BF search (time complexity) - -<li> -evaluation: - -<ul> -<li> -completeness: yes (no infinite paths) - -<li> -time: \(O(b^d)\) - -<li> -space: \(O(bd)\) - -</ul> -</ul> - -<div id="State space search-Informed search (heuristics)"><h2 id="Informed search (heuristics)">Informed search (heuristics)</h2></div> - -<p> -Heuristic function: "educated guess that reduces/limits search for solutions" -</p> - -<p> -informedness property of heuristics: -</p> -<ul> -<li> -two heuristics \(h_1(n),\; h_2(n)\) with \(0 \leq h_1(n) \leq h_2(n) \leq h*(n)\) - -<li> -then \(h_2(n)\) is more informed than \(h_1(n)\) - -<li> -with \(h_1\) fewer nodes have to be searched with \(h_2\) - -<li> -but \(h_2\) is often more expensive to calculate - -<li> -perfect heuristics: \(h(n) = h*(n)\) - -<li> -trivial heuristics: \(h(n) = 0\) - -</ul> - -<p> -Best-first search -</p> -<ul> -<li> -the general approach of informed search - -<li> -node selected for expansion based on <em>evaluation function f(n)</em> - -<li> -evaluation function measures distance to goal, choose node which appears best - -<li> -fringe is queue in order of decreasing desirability - -</ul> - -<div id="State space search-Informed search (heuristics)-A Search"><h3 id="A Search">A Search</h3></div> -<p> -best-known form of best-first search -</p> - -<p> -avoid expanding paths that are already expensive -</p> - -<p> -evaluation function: \(f(n) = g(n) + h(n)\) -</p> -<ul> -<li> -g(n) the cost so far to reach node n - -<li> -h(n) estimated cost to get from node n to goal - -<li> -f(n) estimated total cost of path through node n to goal - -</ul> - -<div id="State space search-Informed search (heuristics)-A* Search"><h3 id="A* Search">A* Search</h3></div> - -<p> -A search, but with an admissible heuristic -</p> -<ul> -<li> -heuristic is admissible if it <em>never</em> overestimates the cost to get to goal - -<li> -admissible heuristics are optimistic - -<li> -formally: \(h(n) \leq h*(n)\) where \(h*(n)\) is true cost from n to goal - -</ul> - -<p> -evaluation: -</p> -<ul> -<li> -complete: yes - -<li> -time: exponential with path length - -<li> -space: all nodes are stored - -<li> -optimal: yes - -</ul> - -<div id="State space search-Adversarial search"><h2 id="Adversarial search">Adversarial search</h2></div> -<p> -search has no adversary, solution is a (heuristic) method for finding a goal -</p> - -<p> -games have an adversary, solution is a strategy. time limits force an <em>approximate</em> solution. -</p> - -<p> -you need a function to evaluate the "goodness" of a game position -</p> - -<p> -types of games: -</p> - -<table> -<tr> -<th> - -</th> -<th> -deterministic -</th> -<th> -chance -</th> -</tr> -<tr> -<td> -perfect information -</td> -<td> -chess, checkers, go, othello -</td> -<td> -backgammon, monopoly -</td> -</tr> -<tr> -<td> -imperfect information -</td> -<td> - -</td> -<td> -bridge poker, scrabble, nuclear war -</td> -</tr> -</table> - -<div id="State space search-Adversarial search-Minimax"><h3 id="Minimax">Minimax</h3></div> - -<div id="State space search-Adversarial search-Minimax-Setup"><h4 id="Setup">Setup</h4></div> -<p> -two players: MAX, MIN -</p> - -<p> -MAX moves first, take turns until game is over. winner gets award, loser gets penalty. -</p> - -<p> -how does this relate to search? -</p> -<ul> -<li> -initial state: game configuration e.g. with chess - -<li> -successor function: list of <move, state> pairs with legal moves - -<li> -terminal test: game finished? - -<li> -utility function: numerical value of terminal states (win +1, lose -1, draw 0) - -<li> -MAX uses search tree to determine next move - -</ul> - -<div id="State space search-Adversarial search-Minimax-Optimal strategies"><h4 id="Optimal strategies">Optimal strategies</h4></div> - -<p> -find contingent strategy for MAX assuming infallible MIN. -</p> - -<p> -assume that both players play optimally. -</p> - -<p> -given game tree, optimal strategy can be found with minimax value of each node: -</p> - -<pre> - minimax(n) = utility(n) if n is a terminal - minimax(max(successors of n)) if n is a max node - minimax(min(successors of n)) if n is a min node -</pre> - -<div id="State space search-Adversarial search-Minimax-Evaluation"><h4 id="Evaluation">Evaluation</h4></div> -<ul> -<li> -complete: yes - -<li> -time: \(O(b^m)\) - -<li> -space: \(O(bm)\) - -<li> -optimal: yes - -</ul> - -<div id="State space search-Adversarial search-Reducing problems of complexity with Minimax"><h3 id="Reducing problems of complexity with Minimax">Reducing problems of complexity with Minimax</h3></div> - -<div id="State space search-Adversarial search-Reducing problems of complexity with Minimax-Cutting off search:"><h4 id="Cutting off search:">Cutting off search:</h4></div> -<p> -instead of <code>if TERMINAL(state) then return UTILITY(state)</code> do <code>if CUTOFF-TEST(state, depth) then return EVAL(state)</code> -</p> - -<p> -this introduces fixed-limit depth. also loses completeness! -</p> - -<p> -utility: value based on quality of state -</p> - -<p> -heuristics: value based on estimation of quality of state -</p> - -<p> -heuristic EVAL: -</p> -<ul> -<li> -produces estimate of expected utility of a game from a given position - -<li> -should order terminal nodes in same way as utility - -<li> -computation shouldn't take too long - -</ul> - -<div id="State space search-Adversarial search-Reducing problems of complexity with Minimax-Alpha-Beta pruning (efficient Minimax)"><h4 id="Alpha-Beta pruning (efficient Minimax)">Alpha-Beta pruning (efficient Minimax)</h4></div> - -<p> -with minimax, the number of states is exponential to number of moves -</p> - -<p> -so, don't examine every node and prune the subtrees you don't have to examine -</p> - -<p> -Alpha: value of best MAX choice so far -</p> - -<p> -Beta: value of best MIN choice so far -</p> - -<p> -you prune the rest of the level if, at any point, beta <= alpha. -</p> - -<p> -pruning doesn't affect final results, entire subtrees can be pruned -</p> - -<p> -good move ordering improves effectiveness of pruning -</p> - -<p> -with 'perfect ordering', time complexity is: \(O(b^{m/2})\) -</p> - -<div id="State space search-Adversarial search-Search with no or partial information"><h3 id="Search with no or partial information">Search with no or partial information</h3></div> - -<p> -problems: -</p> -<ul> -<li> -contingency: percepts provide new info - -<li> -exploration: when states/actions of environment are unknown - -<li> -sensorless/conformant: agent may have no idea where it is - -</ul> - -<div id="State space search-Adversarial search-Search with no or partial information-Perfect information Monte Carlo sampling (rdeep)"><h4 id="Perfect information Monte Carlo sampling (rdeep)">Perfect information Monte Carlo sampling (rdeep)</h4></div> -<ol> -<li> -rollout: - -<ul> -<li> -assume a belief state (with perfect info) - -<li> -play random game in that state. - -</ul> -<li> -average the rollouts - -<li> -choose one with max average - -</ol> - -<div id="State space search-Adversarial search-Games with chance"><h3 id="Games with chance">Games with chance</h3></div> -<p> -<img src="img/games-chance.png" alt="Games with chance" /> -</p> - -<div id="State space search-Summary (Schnapsen)"><h2 id="Summary (Schnapsen)">Summary (Schnapsen)</h2></div> -<p> -Phase 2: minimax & alpha-beta pruning -</p> - -<p> -Phase 1: PIMC sampling -</p> - -<p> -what next? give the agent information about the game -</p> - -<div id="State space search-Search direction"><h2 id="Search direction">Search direction</h2></div> -<p> -Data-driven: start with initial state (e.g. a maze) -</p> - -<p> -Goal-driven: start with goal state, but has bigger branching factor (<span class="todo">TODO</span> confirm this) -</p> - -</body> -</html> diff --git a/content/is-notes/img/games-chance.png b/content/is-notes/state-space-search/games-chance.png Binary files differ. diff --git a/content/is-notes/state-space-search/index.md b/content/is-notes/state-space-search/index.md @@ -0,0 +1,226 @@ ++++ +title = "State space search" +template = 'page-math.html' ++++ +# State space search +How do we find the solutions of previous problems? +* search the state space +* search through explicit tree generation: root is initial state, nodes/leaves generated through successor function +* search generates a graph + +state: representation of a physical configuration + +node: data structure in the search tree. it contains state, parent node, actions, etc. + +## Uninformed search strategies +strategy defines picking order of node expansion + +uninformed methods: only use problem definition + +informed methods: use heuristic function to estimate cost of solution + +evaluating performance: +* does it always find a solution if there is one? (completeness) +* does it find least-cost solution? (optimality) +* how many nodes generated/expanded? (time complexity) +* how many nodes are stored in memory during search? (space complexity) +* complexity measured in terms of: + * b: max branching factor of search tree) + * d: depth of least cost solution + * m: max depth of state space, could be infinite +* time/space complexity measured in terms of max branching factor of search tree, depth of least cost solution, max depth of state space (could be infinite) + + + +### Breadth-first (BF) search +* algorithm: + * expand shallowest unexpanded node + * implementation - fringe (nodes that have to be explored) is a FIFO queue +* evaluation: + * completeness: yes, if branching factor b is finite + * time complexity: if every state has b successors, and solution is at depth d, then $O(b^{d+1})$ because of number of nodes generated + * space complexity: shitty if every node has to be in memory - $O(b^{d+1})$ + * optimality: in general yes, unless actions have different cost +* memory requirements are bigger problem than execution time + +### Depth-first (DF) search +* algorithm: + * expand deepest unexpanded node + * implementation: fringe is a stack +* evaluation: + * completeness: no, unless search space is finite and no loops are possible + * time complexity: shitty if m is larger than d (depth of optimal solution) -- $O(b^m)$. but if many solutions, faster than BF + * space complexity: backtracking search uses less memory, one successor instead of all b -- $O(bm+1)$ + * optimality: no, same issues as completeness + +### Depth-limited search +* DF-search with depth limit l (nodes at depth l have no successors) +* solves infinite-path problem +* evaluation: + * time: $O(b^l)$ + * space: $O(bl)$ + * completeness: not if l < d + * optimality: not if if l > d + +### Iterative deepening search +* strategy to find best depth limit l +* often used in combination with DF search +* after each iteration, throw away everything and increase depth limit +* combines benefits of DF (space complexity) and BF search (time complexity) +* evaluation: + * completeness: yes (no infinite paths) + * time: $O(b^d)$ + * space: $O(bd)$ + +## Informed search (heuristics) + +Heuristic function: "educated guess that reduces/limits search for solutions" + +informedness property of heuristics: +* two heuristics $h_1(n),\; h_2(n)$ with $0 \leq h_1(n) \leq h_2(n) \leq h*(n)$ +* then $h_2(n)$ is more informed than $h_1(n)$ +* with $h_1$ fewer nodes have to be searched with $h_2$ +* but $h_2$ is often more expensive to calculate +* perfect heuristics: $h(n) = h*(n)$ +* trivial heuristics: $h(n) = 0$ + +Best-first search +* the general approach of informed search +* node selected for expansion based on _evaluation function f(n)_ +* evaluation function measures distance to goal, choose node which appears best +* fringe is queue in order of decreasing desirability + +### A Search +best-known form of best-first search + +avoid expanding paths that are already expensive + +evaluation function: $f(n) = g(n) + h(n)$ +* g(n) the cost so far to reach node n +* h(n) estimated cost to get from node n to goal +* f(n) estimated total cost of path through node n to goal + +### A* Search + +A search, but with an admissible heuristic +* heuristic is admissible if it _never_ overestimates the cost to get to goal +* admissible heuristics are optimistic +* formally: $h(n) \leq h*(n)$ where $h*(n)$ is true cost from n to goal + +evaluation: +* complete: yes +* time: exponential with path length +* space: all nodes are stored +* optimal: yes + +## Adversarial search +search has no adversary, solution is a (heuristic) method for finding a goal + +games have an adversary, solution is a strategy. time limits force an _approximate_ solution. + +you need a function to evaluate the "goodness" of a game position + +types of games: + +| | deterministic | chance | +|-----------------------|------------------------------|-------------------------------------| +| perfect information | chess, checkers, go, othello | backgammon, monopoly | +| imperfect information | | bridge poker, scrabble, nuclear war | + +### Minimax + +#### Setup +two players: MAX, MIN + +MAX moves first, take turns until game is over. winner gets award, loser gets penalty. + +how does this relate to search? +* initial state: game configuration e.g. with chess +* successor function: list of <move, state> pairs with legal moves +* terminal test: game finished? +* utility function: numerical value of terminal states (win +1, lose -1, draw 0) +* MAX uses search tree to determine next move + +#### Optimal strategies + +find contingent strategy for MAX assuming infallible MIN. + +assume that both players play optimally. + +given game tree, optimal strategy can be found with minimax value of each node: + +``` + minimax(n) = utility(n) if n is a terminal + minimax(max(successors of n)) if n is a max node + minimax(min(successors of n)) if n is a min node +``` + +#### Evaluation +- complete: yes +- time: $O(b^m)$ +- space: $O(bm)$ +- optimal: yes + +### Reducing problems of complexity with Minimax + +#### Cutting off search: +instead of `if TERMINAL(state) then return UTILITY(state)` do `if CUTOFF-TEST(state, depth) then return EVAL(state)` + +this introduces fixed-limit depth. also loses completeness! + +utility: value based on quality of state + +heuristics: value based on estimation of quality of state + +heuristic EVAL: +* produces estimate of expected utility of a game from a given position +* should order terminal nodes in same way as utility +* computation shouldn't take too long + +#### Alpha-Beta pruning (efficient Minimax) + +with minimax, the number of states is exponential to number of moves + +so, don't examine every node and prune the subtrees you don't have to examine + +Alpha: value of best MAX choice so far + +Beta: value of best MIN choice so far + +you prune the rest of the level if, at any point, beta <= alpha. + +pruning doesn't affect final results, entire subtrees can be pruned + +good move ordering improves effectiveness of pruning + +with 'perfect ordering', time complexity is: $O(b^{m/2})$ + +### Search with no or partial information + +problems: +* contingency: percepts provide new info +* exploration: when states/actions of environment are unknown +* sensorless/conformant: agent may have no idea where it is + +#### Perfect information Monte Carlo sampling (rdeep) +1. rollout: + * assume a belief state (with perfect info) + * play random game in that state. +2. average the rollouts +3. choose one with max average + +### Games with chance + + +## Summary (Schnapsen) +Phase 2: minimax & alpha-beta pruning + +Phase 1: PIMC sampling + +what next? give the agent information about the game + +## Search direction +Data-driven: start with initial state (e.g. a maze) + +Goal-driven: start with goal state, but has bigger branching factor (TODO confirm this) + diff --git a/content/is-notes/img/search-alg-summary.png b/content/is-notes/state-space-search/search-alg-summary.png Binary files differ. diff --git a/content/is-notes/style.css b/content/is-notes/style.css @@ -1,38 +0,0 @@ -@charset 'UTF-8'; -@font-face{font-family:'FontAwesome';src:url('font/fontawesome-webfont.eot?v=4.0.1');src:url('font/fontawesome-webfont.eot?#iefix&v=4.0.1') format('embedded-opentype'),url('font/fontawesome-webfont.woff?v=4.0.1') format('woff'),url('font/fontawesome-webfont.ttf?v=4.0.1') format('truetype'),url('font/fontawesome-webfont.svg?v=4.0.1#fontawesomeregular') format('svg');font-weight:normal;font-style:normal} - -body { - margin: 0px; - padding: 1em; - background: #f3f2ed; - font-family: 'Lato', sans-serif; - font-size: 12pt; - font-weight: 300; - color: #8A8A8A; - padding-left: 50px; -} -h1 { - margin: 0px; - padding: 0px; - font-weight: 300; - text-align: center; -} -ul.toc li { - margin: 8px 0; -} -h3.name { - font-style: italic; - text-align: center; - font-weight: 300; - font-size: 20px; -} -a { - color: #D1551F; - } -a:hover { - color: #AF440F; -} - strong { - font-weight: 700; - color: #2A2A2A; - }
