representations
Contents
6.9. representations#
Some notes on knowledge representation based on Berkeley’s CS 188 course and “Artificial Intelligence” Russel & Norvig 3rd Edition
6.9.1. intro#
AI - field of study which studies the goal of creating intelligence
intelligent agent - system that perceives its environment and takes actions that maximize its chances of success
expert task examples - medical diagnosis, equipment repair, computer configuration, financial planning
formal systems - use axioms and formal logic
ontologies - structuring knowledge in graph form
statistical methods
turing test - is human mind deterministic { turing1950computing }
chinese room argument - rebuts turing test { cite searle1980minds }
china brain - what if different people hit buttons to fire individual neurons
Polanyi’s paradox: “we can know more than we can tell”
6.9.2. symbol search#
computer science - empirical inquiry
6.9.2.1. symbols and physical symbol systems#
intelligence requires the ability to store and manipulate symbols
laws of qualitative structure
cell doctrine in biology
plate tectonics in geology
germ theory of disease
doctrine of atomism
“physical”
obey laws of physics
not restricted to human systems
designation - then given the expression, the system can affect the object
interpretation - expression designates a process
6.9.2.2. heuristic searching#
symbol systems solve problems with heuristic search
Heuristic Search Hypothesis - solutions are represented as symbol structures. A physical symbol system exercises its intelligence in problem solving by search–that is, by generating and progressively modifying symbol structures until it produces a solution structure
from { cite newell1976computer }
there are practical limitations on how fast computers can search
To state a problem is to designate
a test for a class of symbol structures (solutions of the problem)
a generator of symbol structures (potential solutions).
To solve a problem is to generate a structure, using (2), that satisfies the test of (1).
searching is generally in a tree-form
6.9.3. knowledge representation#
physical symbol system hypothesis - a physical symbol system has the necessary and sufficient means for general intelligent action
computers and minds are both physical symbol systems
symbol - meaningful pattern that can be manipulated
symbol system - creates, modifies, destroys symbols
want to represent
meta-knowledge - knowledge about what we know
objects - facts
performance - knowledge about how to do things
events - actions
two levels
knowledge level - where facts are described
symbol level - lower
properties
representational adequacy - ability to represent
inferential adequacy
inferential efficiency
acquisitional efficiency - acquire new information
two views of knowledge
logic
a logic is a language with concrete rules
syntax - rules for constructing legal logic
semantics - how we interpret / read
assigns a meaning
multi-valued logic - not just booleans
higher-order logic - functions / predicates are also objects
multi-valued logics - more than 2 truth values
fuzzy logic - uses probabilities rather than booleans
match-resolve-act cycle
associationist
knowledge based on observation
semantic networks - objects and relationships between them - like is a, can, has
graphical representation
equivalent to logical statements
ex. nlp - conceptual dependency theory - sentences with same meaning have same graphs
frame representations - semantic networks where nodes have structure
ex. each frame has age, height, weight, …
when agent faces new situation - slots can be filled in, may trigger actions / retrieval of other frames
inheritance of properties between frames
frames can contain relationships and procedures to carry out after various slots filled
statistical
distributed - usually different from sparse code (sparser generally less robust)
opposite of sparse code = dense code
have to check multiple indexes
penti’s work: distributed
usually want these to be robust
nlp is main place where unsupervised pretraining widely used
hierarchical
good representations - linearly separable
representation that factors
information bottleneck method: want simple representation that keeps class but throws away lots of extraneous info
6.9.4. expert systems#
expert system - program that contains some of the subject-specific knowledge of one or more human experts.
problems
planning
monitoring
instruction
control
need lots of knowledge to be intelligent
rule-based architecture - condition-action rules & database of facts
acquire new facts
from human operator
interacting with environment directly
forward chaining
until special HALT symbol in DB, keep following logical rule, add result to DB
conflict resolution - which rule to apply when many choices available
pattern matching - logic in the if statements
backward chaining - check if something is true
check database
check if on the right side of any facts
CLIPS - expert system shell
define rules and functions…
explanation subsystem - provide explanation of reasoning that led to conclusion
people
knowledge engineer - computer scientist who designs / implements ai
domain expert - has domain knowledge
user interface
knowledge engineering - art of designing and building expert systems
determine characteristics of problem
automatic knowledge-acquisition - set of techniques for gaining new knowledge
ex. parse Wikipedia
crowdsourcing
creating an expert system can be very hard
only useful when expert isn’t available, problem uses symbolic reasoning, problem is well-structured
MYCIN - one of first successful expert systems { cite shortliffe2012computer }
Stanford in 1970s
used backward chaining but would ask patient questions - sometimes too many questions
advantages
can explain reasoning
can free up human experts to deal with rare problems
6.9.5. Godel, Escher, Bach#
Douglas Hofstadter, 1979
6.9.5.1. meta#
strange loop = paradox - self-referential
zen enlightenment
goal: transcend dualism = division into concepts (perception, words do this)
words give you some truth but always fail to describe some parts of the truth
6.9.5.2. music#
canons - repeat w/ subtle changes (e.g. pitch shift)
fugue - repeat w/ more substantial changes
6.9.5.3. ai#
essential abilities - can we do these things unsupervised?
to recognize the relative importance of different elements of a situation
to find similarities between situations despite differences which may separate them;
to draw distinctions between situations despite similarities which may link them
to synthesize new concepts by taking old concepts and putting them together in new ways
intelligence consists of rules at different levels
“just plain” rules - like reflexes which respond to stereotyped situations
metarules - when situations are mixtures of steretoyped situations, requires rules for deciding which “just plain” rules to apply
rules for inventing new rules - when situations can’t be classified
rules may have to change themselves
messages - comparison of DNA to a jukebox
where is info stored? records? buttons? smashed buttons?
what could constitute a Rosetta stone for DNA codes?
3 parts
frame - tells you that this is a message
outer - tells you how to read a message (e.g. language, style)
inner - actual content
if decoding is universal, we might call the outer message (e.g. the trigger) the message
memory - same bits can be used for different things - part of each message specifies the instruction type
6.9.5.4. brain#
intelligence involves a calculus of descriptions = symbols
symbols represent both classes + instances (maybe both depending on amount of activation / context) - def need some context
can have links to other symbols (+priors on these)
top-down logical structure??
different ways to combine symbols get blurry
symbols can be learned to branch, merge
can harness temporal firing rates to encode more
can grow incrementally (greedily)
analogy of thoughts as trips on a (poorly fleshed out) map
6.9.5.5. interpretation#
ex. top is decimal expansion of the sum of the second (\(\pi/4\))
7, 8, 5, 3, 9, 8, 1, 6, …
1, -1/3, +1/5, -1/7, +1/9, -1/11…
6.9.5.6. math / logic#
godel’s thm - limitation of any formal axiomatic system: cannot make a program to find a complete + consistent set of axioms
church-turing thesis - a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine
no system can do computation which cannot be broken down into simple elements
decision procedure - decides whether something is a theorem - must terminate
we can think of theorems as strings in a formal system
interpretation - correspondence between symbols and words
ideally, these are meaningful isomorphisms between codes and reality
not all interpretations imply meaningful (or valid) corresponding codes
there might be multiple, equally valid interpretations
consistency depends on interpretation:
consistency - when every theorem, upon interpretation, comes out true (in some imaginable world)
completeness - when all statements which are true (in some imageinable world), and which can be expressed as well-formed strings of the system, are theorems
slightly different axioms lead to elliptical/hyperbolic geometry instead of Euclidean geometry
godel numbering - can replace all symbols w/ numbers and all typographic rules w/ arithmetic rules
2 key idesas
strings can speak about other strings
self-scrutiny can be entire concentrated into a single string
every aspect of thinking can be viewed as a high-level description of a system which, on a low level, is governed by simple, even formal rules
6.9.5.7. causality#
what counterfactuals are the most realistic
different things are stable at different levels
6.9.5.8. biology#
dna -> rna -> proteins = sequence of amino acids
folds w/ valrious levels of structure (like music)
self-rep - what counts?
quine? instructions on jukebox? human reproduction?