	Computer Science:Artificial Intelligence - eMyTextBooks		Search:
	Free online books - just read it!		See live article • Computer Science:Artificial Intelligence

Computer Science:Artificial Intelligence

This is where I will be dumping the notes from an graduate AI course I'm taking this semester (Spring 2005).

Introduction

With a bit of oversimplification, AI is:

simulated intelligent behavior
symbolic processing

Main techniques include:

rule-based or tree-based knowledge representation.
logic programming
heuristics

AI has influenced a number computer scientific areas:

databases
software engineering, include object-oriented design
distributed computing
graphics
user interfaces
simulation

Search

Search is a classical AI topic. Many AI problems reduce to searching for solutions in the problem state space. The basic idea:

initial state
apply an operator to transform state.

Example: symbolic integration

To find this integral: $\int{{x^4 \over (1-x^2)^{5/2}} dx}$ , you can try different tricks, and not all will work.

Example: 8-puzzle

If a bunch of tiles are arranged like this:

$\begin{bmatrix} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 & \Box & 5 \end{bmatrix}$

And this is the correct order:

$\begin{bmatrix} 1 & 2 & 3 \\ 8 & \Box & 4 \\ 7 & 6 & 5 \end{bmatrix}$

and the $\Box$ is a blank tile you can slide around, then you can use search to figure it out. Each state will have at most four resulting states, because you can slide $\Box$ up, left, right, and down.

Heuristic search

You can use DFS (Depth-first search) or BFS (Breadth-first search) to explore a graph, but it may require O( $b m$ ) node visits, but if you want to search more efficiently, it might better to check out the promising leads first. With a heuristic search, at each step of the way, you use an evaluation function to choose which subtree to explore. You can think of a heuristic search like a "best-first" search.

It is important to remember that a heuristic search is best at finding a solution that is "good enough" rather than the perfect solution. Some problems are so big that finding the perfect solution is too hard.

To do a heuristic search you need an evaluation function that lets you rank your options.

Sliding tile puzzle aka 8-puzzle Example

This website (http://scv.bu.edu/~aarondf/java/puzzle9.html) has an example of a sliding tile puzzle if you are unfamiliar with what these are. Some people call these sliding tile puzzles, others (mostly AI nerds) call these things 8-puzzles. They provide a problem that can be solved more efficiently with a heuristic search (like A*) vs. DFS and BFS.

For the 8-puzzle, we could use this as a simple evaluation function:

$f = g + w$

where $g$ is the distance from the root, and $w$ is the number of misplaced tiles, not counting the $\Box$ tile.

The evaluation function $f = g + w$ would score the initial state

$\begin{bmatrix} 5 & 4 & \Box \\ 6 & 1 & 8 \\ 7 & 3& 2 \end{bmatrix}$

$4 = 0 + 4$

A better heuristic is known as the Manhattan distance. This heuristic value is determined by the sum of the distance for each tile from its goal location. This heuristic is admissible, such that it does not overestimate the cost to reach the goal node.

TODO: draw search tree for 8-puzzle and show heuristic search path solution, vs. DFS and BFS search solution.

The above evaluation function is just one possible guess. We could play with other evaluation functions, like:

$f = g + p$ , where g is the same, and p is the sum of distances that each tile is from the root.

Or we could use $f = g + p + 3 S$ , where $g$ and $p$ are the same, and $S$ is the sum of sequence scores $Σ s$ . $s$ is calculated for each tile like so:

$s = \begin{cases} 1, & \mbox{if the tile is the central tile} \\ 0, & \mbox{if the tile is the noncentral tile and is followed by the proper successor} \\ 2, & \mbox{if the tile is non-central and is not followed by its proper successor} \end{cases}$

Tic Tac Toe and minimax

to be done later

Tic Tac Toe and alpha beta

Knowledge discovery and machine learning

Probability is probably going to be boring.

Example 1: tossing a coin once

$ω 1 = H E A D S$

$ω 2 = T A I L S$

$\Omega = \left \{ \omega_1, \omega_2 \right \}$

$X (ω)$ can be a function like the number of heads. $X (ω 1) = 1$ , and $X (ω 2) = 0$ .

Example 2: tossing a coin twice.

$\Omega = \left \{ HH, HT, TH, TT \right \}$

Potiential outputs from our $X (ω)$ function:

$X(\omega) = \left \{ 2, 1, 1, 0 \right \}$

On to probability.

$P (H H)$ should return the probability of getting two heads.

Often we denote $P (X (ω) = x)$ as $P (x)$ .

Logarithms refresher

The logarithm L of a number N, in a given base B, is such that $N = B L$

For instance, make $N = 8$ and $B = 2$ . Then, you would have $L = 3$ , as you can see: $l o g 2 8 = 3$

Another example:

$log_2 ( \frac {1}{4} ) = log_2 ( 2^ {-2} ) = -2 log_2 ( 2^1 ) = -2$

Emacs SLIME appendix

Emacs SLIME User Manual (http://common-lisp.net/project/slime/doc/slime.pdf)

The recommended way to use lisp (according to the #lisp crew) is to use SBCL and emacs with the SLIME extension. Below are some useful commands:

Command                what it does
M-x slime              starts slime session
C-x b                  switches to another buffer
C-c C-l                load current file into SLIME
C-c C-k                compile current file
C-c C-c                compile current function
C-x C-s                save current buffer
C-x C-c                quit emacs
C-c C-z                jump to slime buffer
C-x C-f                open a new buffer
C-x 2                  view two frames, horizontally stacked.
C-x 1                  return to a one-frame view
C-x o                  move to other frame

Common lisp resources

useful links

Wikipedia page for Common Lisp

This page (http://www.unmutual.info/startingwithcl.html) has links to lots of free lisp tools.

Common Lisp HyperSpec (http://www.lisp.org/HyperSpec/FrontMatter/index.html) online documentation for common lisp.

Lisp in a box (http://common-lisp.net/project/lispbox/) seems to be the easiest way for a total n00b to get set up to use common lisp on windows and linux.

SLIME User Manual (http://common-lisp.net/project/slime/doc/slime.pdf)

Practical Common Lisp, by Peter Seibel (http://www.gigamonkeys.com/book/) This book is really good.

a few lisp coding examples

CL-USER> (loop for e in '(a b c)
               do (format t "e is ~a.~%" e)
               collect e)
e is A.
e is B.
e is C.
(A B C)
CL-USER> (let ((x 0)
               (y 1)
               (z 2))
           (format t "x: ~a y: ~a z: ~a~%" x y z)
           (+ x y z))
x: 0 y: 1 z: 2
3
CL-USER> (if (< 3 1) 0 1)
1
CL-USER> (if (< 3 5) 1 2)
1
CL-USER> (cond ((< 3 1) 1)
               ((< 9 10) 2)
               (t 3))
2

class notes on lisp

Lisp is made of symbolic expressions. Everything descends from them.

symbolic expression
- atom
  - number
    - float
    - fixed-point
  - symbol
- list

A lisp program is an ordered set of lists. In lisp, programs and data have the same form. Programs can be manipulated by programs.

(+ 8 3)

In the above computation, + is an operator, and 8 and 3 are arguments.

Some example computations:

CL-USER> (- 8 3)
5
CL-USER> (- 8 3 4)
1
CL-USER> (1+ 8)
9
CL-USER> (1- 8)
7
CL-USER> (* 8 (+ 3 7))
80
CL-USER> (expt 2 3)
8
CL-USER> (expt 3.3 2.2)
13.827086
CL-USER> (sqrt 9)
3
CL-USER> (abs -5)
5

Symbols and setq

x is a symbol, which is sort of like a variable.

(setq x 5) ; assigns 5 to symbol x.

setq does not evaluate its first argument.

Symbols and variables are different; e.g., x is a symbol throughout the program. However, x can be bound to different variables, e.g., a global and a local. The global x may have a value of 5, while the local x has the value 8.

setq can make multiple assignments:

CL-USER> (setq x 5 y 6 y 7)
7

quote

CL-USER> (quote (a b c))
(A B C)
CL-USER> '(a b c)
(A B C)
CL-USER> (setq x '(+ 3 4))
(+ 3 4)
CL-USER> (setq x (+ 3 4))
7
CL-USER> (setq x '(+ 3 (* 4 5)))
(+ 3 (* 4 5))
CL-USER> (setq x `(+ 3 ,(* 4 5) (- 6 7)))
(+ 3 20 (- 6 7))

setq vs set

CL-USER> (setq x 'y)
Y
CL-USER> x
Y
CL-USER> (set x 'z)
Z
CL-USER> x
Y
CL-USER> y
Z

set, rather than setq, evaluates the first argument. setq stands for set quote.

setf, remove, cons

assignment of lists:

CL-USER> (setf friends '(dick jane))
(DICK JANE)
CL-USER> friends
(DICK JANE)
CL-USER> (setf enemies '(grinch ghost))
(GRINCH GHOST)
CL-USER> (setf friends (remove 'ghost enemies))
(GRINCH)
CL-USER> (setf friends (cons 'ghost friends))
(GHOST GRINCH)
CL-USER> friends
(GHOST GRINCH)

first, second, third, etc.

CL-USER> (first '(a b c))
A
CL-USER> (second '(a b c))
B
CL-USER> (third '(a b c))
C

car and cdr: old-school flavor.

CL-USER> (cdr '((a b) c))
(C)
CL-USER> (car (cdr '(a b c)))
B

You can combine car and cdr:

CL-USER> (car (cdr '(a b c)))
B
CL-USER> (cadr '(a b c))
B
CL-USER> (caddr '(x y z w))
Z
CL-USER> (car (cdr (cdr '(x y z w))))
Z

Fun with cons:

CL-USER> (cons 'a '(b c))
(A B C)
CL-USER> (cons '(a b) '(c d))
((A B) C D)
CL-USER> (cons 'a (cons 'b (cons 'c NIL)))
(A B C)
CL-USER> (list 'a 'b 'c)
(A B C)
CL-USER> (append '(a b) '(c d))
(A B C D)
CL-USER>

cons, list, and append do not alter symbol values.

CL-USER> (setq x 'a L '(b c))
(B C)
CL-USER> (cons x L)
(A B C)
CL-USER> L
(B C)
CL-USER> (setq x 'a L '(b c))
(B C)
CL-USER> (setq L (cons x L))
(A B C)
CL-USER> L
(A B C)

Inserting an element at the end of a list:

CL-USER> (append '(a b) '(c))
(A B C)
CL-USER> (setq x 'c)
C
CL-USER> (append '(a b) (list x))
(A B C)
CL-USER> (length '(a b c))
3
CL-USER> (length '((a b) (c d)))
2

Reverse only reverses the order of the top list elements:

CL-USER> (reverse '(a b c))
(C B A)
CL-USER> (reverse '((a b) (c d)))
((C D) (A B))

alists and assoc

CL-USER> (setf apple '((ako fruit)
                       (color red)
                       (shape sphere)))
((AKO FRUIT) (COLOR RED) (SHAPE SPHERE))
CL-USER> (assoc 'color apple)
(COLOR RED)

three rules of evaluation

1. Symbols are replaced by their current bindings

CL-USER> (setq x 2)
2
CL-USER> (+ x x)
4

2. Lists are evaluated as function calls. 3. Everything else evaluates to itself.

It may not look particularly significant, but the above illustrates an important characteristic. You can write symbols rather than only reserved words and variables.

Generations of computer languages

Machine language -> assembly -> high-level languages -> very high-level languages -> symbolic languages

Functions

CL-USER> (defun addthree (x) (+ x 3))
ADDTHREE

In addthree, x is a formal parameter, meaning that x is in the function definition, rather than the function call.

CL-USER> (defun sum-average (x y)
           (setq sum (+ x y))
           (/ sum 2))
SUM-AVERAGE

sum is a non-formal parameter. non-formal parameters are free rather than bound. x and y are formal parameters, which are bound. free parameters are global, and bound parameters are local.

CL-USER> (sum-average 3 5)
4
CL-USER> sum
8
CL-USER> (sum-average 10 20)
15
CL-USER> sum
30

Notice that sum in the top level has its value changed. Use free symbols with great care. It is conventional to set off global parameters with asterisks, like *PS*.

CL-USER> (defun sum-ave-caller (sum x y)
           (sum-average x y) sum)
SUM-AVE-CALLER
CL-USER> (sum-ave-caller 0 10 20)
0
CL-USER> sum
30

Take a look at the above code carefully. It may be confusing but the code listed below is equivalent.

CL-USER> (defun sum-ave-caller (sum_name_substitute x y)
           (sum-average x y) sum_name_substitute)
SUM-AVE-CALLER
CL-USER> (sum-ave-caller 0 10 20)
0
CL-USER> sum
30
CL-USER> sum_name_substitute
ERROR

Theory

The discipline of artificial intelligence potentially provides answers to unsolved problems in neuroscience because AI must devise and test theories of how mind emerges from brains.

I hope you got the idea.

Also helps finding: ComputerScienceArtificialIntelligence, ComputerScience, ScienceArtificial, ArtificialIntelligence, compter, scince, artifical, comptuer, scence, artificiial, comuter, sience, artificiel, computar, scienc

Add to bookmarks

Main Page (table free)
Main Page (text only)
Main Page/test
Main Page

Computer Science:Artificial Intelligence - eMyTextBooks

Free online books - just read it!