Introduction to AI - concepts Flashcards
current trends in AI
exploit the strengths of the computer and don’t model human thought processes
focus on particular tasks and not on solving AI as a whole
strong scientific standards
conference series
Biennial International Joint Conference on AI
Annual National Conference on AI
Biennial European Conference on AI
The birth of AI
1956, Dartmouth Conference
symbolic AI
model knowledge and planning in a way that is understandable to programmers
subsymbolic AI
model intelligence similar to a neuron
Why did the initial expectations of AI not work out?
lack of scalability
difficulty of knowledge representation
limitations on techniques and representations
Forward checking
Search
Keeping track of remaining legal values for unassigned variables
Terminate search if any variable has no more legal values
Local search for CSP
search
Work with complete states
Allow unsatisfied constraints
Min-conflict heuristic: select a conflicted variable and choose the value that violates the fewest constraints
Zermelo
Game-playing
One player can force a win or both players can force a draw
Retrograde analysis
Zermelo, game-playing
Generate all possible positions
Mark all positions where A would win…
Horizon effect
Game-playing
The catastrophy can be delayed by a sequence of moves that don’t make any progress
Forward pruning
Game-playing
Alpha-beta only prunes search trees when it is safe to do so
Null-move-pruning
game-playing
add a “null-move” to the search (assume the current player does not make a move)
if the null-move results in a cutoff, assume that making a move will do the same
Iterative deepening
game-playing
repeated fixed-depth search which works well for transposition tables
move ordering - heuristics
game-playing
domain-dependent heuristics:
capture moves first
forward moves first
domain-independet heuristics:
killer heuristics (manage a list of moves that produced cutoffs at the current level of search)
history heuristics (maintain a table of all possible moves; if a move produces a cutoff, its value is increased)
transposition tables - what does an entry store?
game-playing
state evaluation value
search depth of the stored value
hash key of the position
best move from the position (optional)
What techniques does AlphaGo use?
game-playing
deep learning
reinforcement learning
monte-carlo tree search
Inductive learning
Machine learning
Learn a function from examples
Ignores prior knowledge
Assumes examples are given
Credit assignment problem
Machine learning games
Delayed reward
Knightcap
Machine learning games
Learned to play expertly in chess
Improvements over TD gammon:
Temporal difference learning with deep searches
Played against partners on the internet (instead of self-play)
Simulation search
Machine learning games
Estimate the expected value of each move by counting the number of wins
At each chance node select one of the options at random
Make all move choices quicky
Often works well even if the move selection is not that strong - fast algorithm
UCT Search
Machine learning games
Best-known formulation of MCTS
Combines a UCB-based tree policy with random roll-outs
Exploitation vs Exploration
Choose move that has been visited most often (reliability) not necessarily the one with the highest value (high variance)
AlphaGo
MCTS, deep learning, reinforcement learning from self-play
MCTS: roll-out policy, learned evaluation function instead of real game outcomes
Policy networks
Machine learning games
How “good” is it to move to a position
Input position
Output position
Value networks
Machine learning games
How desirable is it to be in this position
Input position
Output single value
AlphaGo Zero
Learned only from self-play
Much less training data
forward chaining
knowledge
derive new facts from known facts
elementary production principle:
for every rule and a set of facts and a substitution (which maps the body to the set of facts) one can derive one proof step
can be iterated until no further facts can be derived
Resolution principle
knowledge
backward chaining
for disproving a statement, assume its opposite and show that it leads to a contradiction
RDF
knowledge
resource description framework
allows for deductive reasoning (given facts and rules, we can derive new facts)
opposite: induction
deriving models from facts
ontology
knowledge
explicit specification of a conceptualization
encode the knowledge about a domain
form a common vocabulary and describe the semantics of its terms
logical theory
OWL
knowledge
Web ontology language
syntactic extensions of RDF
Freebase
knowledge
2000s, collaborative editing
no fixed schema
acquired and shut down by Google
Wikidata
knowledge
goal: centralize data from wikipedia
collaborative
imports other datasets
one of the largest public knowledge graphs
DBPedia
knowledge
extraction frmo Wikipedia
using maps & heuristics
together with YAGO one of the most used knowledge graphs
NELL
knowledge
never ending language learner
input: ontology, seed examples, text corpus
output: facts, text patterns
large degree of automation
occasional human feedback
Linked open data
knowledge
many dataset are publicly available and connected to each other
using standards like RDF andd URIs for identification of entries
Which fields have contributed to AI research?
history
philosophy
mathematics
psychology
economics
linguistics
neuroscience
control theory
Why is NLP so hard? highly ambiguous at multiple levels…
lexical: same word, different meanings
syntactic: same sentence, different interpretations
semantic: the interpretation depends on its context, requires understanding of our world
discourse: the meaning of a sentence depends on the previous sentences
Traditional NLP tasks
word segmentation (divide the input text into small semantic entities)
part-of-speech-tagging (assign each word its most probable role in a sentence)
syntactic analysis (find the most probable grammatical interpretation of the sentence)
semantic analysis (find the most probable meaning of a sentece and resolve references)
Word2Vec
NLP
every word is represented as a lower-dimensional, non-sparse vector
train a deep neural network in a supervised way, using context of a word as additional input
2 variants:
continuous bag of words
skip-gram
POS tagging is a process of tagging words in a sentece based on…
NLP
the definition of the word (thesaurus)
the context of the word (sequence learning task, Hidden Markov Models, Conditional Random Fields)
N-gram model
NLP
language model, uses only n-1 words of prior context
unigram, bigram, trigram
GPT
General Pre-trained Transformer
Loebner competition
Philosophy
Modern day version of the turing test
Mitsuki
Philosophy
Also known as Kuki
Successor of Eliza
Five-time winner of the Loebner competition
Sussman anomaly
Planning
Subgoals are not independent
