Daily notes

Day 1

What is AI?

[act/think] [rationally/humanly]
- act rationally: do the correct things in the world
- act humanly: do the things the human would do in the world
- think rationally: use the best algorithms to get the correct results
- think humanly: the AI system has internal representations and algorithms like human cognition

Examples of AI

system that designs video games
IBM’s Watson: won Jeopardy!, healthcare
Siri
IBM Deep Blue, beat Kasparov 1997, “Game Over”, used specialized chips that play chess
Google’s autonomous vehicles
Google bought Boston Dynamics
Amazon Air (drones)
Video game AI
robots that learn new languages like toddlers do
drone fighting drones
military drones
Google Glass
Google Search
Google Ads
Google Now
Google Then
Google Future
Machine Learning, Data Mining
Fraud detection

Day 2

How do we test for AI?

put it in a human situation and see if it comes to the same decisions as a human
- maybe just report its decisions, not act on them
- maybe also physically does the same things (if it has arms and legs, etc.)
give it human tests for intelligence, IQ tests, SATs, LSAT, behavioral tests
Voigt-Kampff test
Turing Test
interact with people who don’t know it’s a robot
mock tests of certain scenarios
see if you can tell the difference between human and machine
human-robot chat
see if it has self-preservation tendencies
ask how it feels, emotions
listen to a song with it, then ask it how the song makes it feel
put it in a paradoxical situation, ethical conundrum
- save your dog or the child
ask any question about any topic to see how it responds
job interview
meet the president, or the Queen

The Turing Test

The imitation game

A man (A), a woman (B), and a judge (C)
The judge cannot see A or B (or hear them)
The judge must determine who is the woman
The man (A) wants to convince the judge that he is a woman
- AND, (harder) that the woman is NOT a woman
And the woman (B) is trying to convince the judge that she is the woman
If the man succeeds, then we can say he is intelligent

Replace the man with a machine

now the machine (A) is trying to convince the judge that it is the woman
- woman still trying to say she is the woman
we often think of it as the machine trying to convince the judge that it is the human

What’s “success”?

How often (%) must the man convince the judge that he is the woman to be considered a good woman imitator?
- about 25%
- Turing said 30% would be good enough

Dennett’s weaker versions

Chess (beating Kasparov)
- doesn’t cover range of intelligence
- isolatable skill
Solves the Arab-Israeli conflict
- harder than the TT
- unrepeatable
- slow
- not clear what is considered winning
Steals the crown jewels
- might be able to find security vulnerabilities
- luck
- ethically dubious

Langley’s challenges

Synthetic entertainer
- American AIdoll
Synthetic attorney
Synthetic politician

Day 3

Python

This is the code we played with. Try it out yourself at the “REPL” (just run python from your console).

x = 5
print x
while x > 0:
    print x
    x -= 1

mylist = ["bob", "jane", "alice"]
print mylist

for name in mylist:
    print name

print enumerate(mylist)
print list(enumerate(mylist))
for (i, name) in enumerate(mylist):
    print "index is", i, "and name is", name

mylist2 = [(1, 2, 3), (4, 5, 6)]
for (x, y, z) in mylist2:
    print x, y, z

mystack = []
mystack.append('A')
print mystack
mystack.append('B')
print mystack
print mystack.pop()
print mystack

from collections import deque
myqueue = deque()
print myqueue
myqueue.append('A')
myqueue.append('B')
print myqueue
print myqueue.popleft()
print myqueue
print myqueue.pop()
print myqueue

mylist = ["bob", "jane", "alice"]
print mylist[0]
print mylist[0:1]
print mylist[0:2]
print mylist[0:3]
print mylist[1:3]
print mylist[1:2]
print mylist[1:-1]
print mylist[1:-2]
print mylist[0:-2]
print mylist[-1]
print mylist[-2]
print mylist[-2:0]

# This page describes "list splicing":
# http://stackoverflow.com/questions/509211/pythons-slice-notation

# reverse a string or list:
mystring = "mystring"
print mystring[::-1]

def myfunc(x):
    return x+1

print myfunc(52)

def myfunc(x):
    return (x, x+1)

print myfunc(52)

def myfunc(x=5):  # default value for x
    print x

myfunc()
myfunc(10)

class MyClass:
    def myclassfunc(self, x):
        print x

myobj = MyClass()
myobj.myclassfunc(10)

class MyClass:
    # the constructor
    def __init__(self):
        self.timesExecuted = 0
    def myclassfunc(self):
        self.timesExecuted += 1
        print self.timesExecuted

myobj = MyClass()
myobj.myclassfunc()  # prints 1
myobj.myclassfunc()  # prints 2
myobj.myclassfunc()  # prints 3

Search

Example: Wolves & chicks

Take three chicks and three wolves across the river
If there is a wolf on one side, it will eat the chicks
Boat only holds two animals

Initial state: Three wolves and three chicks on same side
Possible actions: Put a chick on the boat, put a wolf on the boat, move the boat across
Transition model: A function from state to [list of states] and for this problem, the list of states are those that do not kill the chicks
Goal criteria: All on other side
Path cost: A function from list of states/actions to some kind of cost; sometimes you want the least-cost solution

Basic BFS algorithm:

- openset = [start] # places I know about, but haven't been to
- closedset = [] # places I have been to
- while len(openset) > 0:  # i.e., openset not empty
  - state = openset.popleft() # I want a queue/deque
  - closedset.append(state)
  - if state == goal:
    - done
  - else:
    - for next_state in possible_moves(state):
      - if next_state not in closedset:
          - openset.append(next_state)

Basic DFS algorithm:

- openset = [start] # places I know about, but haven't been to
- closedset = [] # places I have been to
- while len(openset) > 0:  # i.e., openset not empty
  - state = openset.pop() # I want a stack  <------- ONLY DIFFERENCE FROM BFS
  - closedset.append(state)
  - if state == goal:
    - done
  - else:
    - for next_state in possible_moves(state):
      - if next_state not in closedset:
          - openset.append(next_state)

Day 4

Informed search

what is a “better” solution to the Goodale problem?
- faster i.e. less time
what information would you use to solve the Goodale problem better?
- traffic information: how long it takes to make the next move
- distance
- speed limits
- stop lights

Day 5

Pacman

your function should return something like: [NORTH, SOUTH, SOUTH, WEST]

parents[next_state] = (state, action)
later, to reconstruct the path:
- you know the goal, call it “state”
- create an empty list of actions:
  - actions = []
  - then put stuff in it iteratively, by referring to the parents map:
    - while state in parents:
      - (prior_state, action) = parents[state]

Heuristics for 8-puzzle

number of pieces out of place
sum of manhattan distances for each piece to where it needs to go

Heuristics for Goodale routing

straight-line distance from state to goal
- calculate with lat/lon
length of street & speed limit
- factor in traffic
manhattan distance from state to goal

Hill-climbing

take “best” according to heuristic, then delete the openset

Best-first search

take “best” according to heuristic, but use openset as usual

Again with the heuristics

“admissible”: ALWAYS underestimates or is perfect
impact: if it’s admissible, the search will always find the best path
when h(s) is admissible, it’s called h*(s)

Goodale

is straight-line distance “admissible”?
- yes, can’t go faster than straight-line
road distance * speed limit: admissible?
- no, might get there faster (drive over the speed limit)
manhattan distance is not admissible

A*

The search algorithm that uses f*(s) = g(s) + h*(s) is called A*

Websites

http://qiao.github.io/PathFinding.js/visual/
https://www.youtube.com/watch?v=g418BSF6XBQ (SimCity)
https://www.youtube.com/watch?v=WTDS3EhGH4w (SimCity)

Day 6

A*

1. create an empty list called "closedset"; this list will contain
   states that have been visited

2. create a list called "openset" that contains just the starting
   state; this list contains states that have not been visited but are
   known to exist

2.a. create a list called "openset_states" that contains just the states
     that would otherwise be in openset

3. create an empty map (key/value pairs) called "parents"; this map
   contains the previous state of each state that has been visited

4. while the openset is not empty:

   a. grab a state from the openset (and remove it from both sets);
      put it in the closedset (since we're now looking at it)

      - we need to prefer better states first

   b. if that state is the goal, hey we're done!

      i. return a reconstructed path from the goal state to the start
         state (this is easy: recursively grab parent states from the
         "parents" map)

   c. it's not the goal state; for each next state that is accessible
      from here:

       i. if this next state is in the closedset (it has been visited
          before), ignore it

      ii. if this next state is not in the openset, put it in the
          openset and record its parent

          - if state not in openset_states:

   d. (repeat the loop)

5. if the openset is empty and we never found the goal, oops!

Heaps

heaps are ordered lists
- stuff is sorted by what its value is:
  - best to use: (score, state) tuples

Cost functions (path-cost + heuristic)

What’s the number associated with a state?

You can get BFS behavior if you do this:
- cost = number of steps in the path
- i.e., cost of path to here, + 1
- bottom-up approach:
  - when you find successors,
    - record in another map, path cost + 1

for (next_state, action, cost) in problem.getSuccessors(state):
    # next_state is something like (4, 2) (coordinates)
    # action is something like WEST
    # cost is not used for depth-first search

    path_cost = 0
    if state in path_costs:
        path_cost = path_costs[state] + cost
    path_costs[next_state] = path_cost

    # path_cost is g(s) in the formula f*(s) = g(s) + h*(s)

    # btw, BFS is f(s) = g(s)
    # btw, DFS is f(s) = -g(s)
    # btw, best-first is f(s) = h(s)
    # btw, A is f(s) = g(s) + h(s)
    # btw, A* is f*(s) = g(s) + h*(s)

    # two options for h*(s): manhattanHeuristic, euclideanHeuristic,
    #                        nullHeuristic

    total_cost = path_cost + heuristic(next_state, problem)

    heappush(openset, (total_cost, next_state))
    openset_states.push(next_state)

Day 8

Zero-sum games

A game where, in the end, all the players’ utilities add up to zero
Examples:
- Chess
- Tug-o-war
- Poker
- Trading card game competitions
- Rock-paper-scissors-lizard-spock
- Go
- Tic-tac-toe
- Checkers
Non-examples:
- Scrabble
- FPS with co-op
- Soccer, football, baseball

Tic-tac-toe

Initial state: blank board
Possible actions: put an x, put an o
Transition model: how a board changes after putting an x/o
Players: x and o
Terminal tests: three in a row for either x/o or a full board (tie)
Utility function (always for x):
- suppose x has three in a row: 1
- suppose o has three in a row: -1
- suppose there is a tie: 0

Day 9

Connect-four code with depth-limited minimax

def create_grid():
    # grid is 6x7 so we'll create a list of size 42
    return [' ' for _ in range(42)]

def print_grid(grid):
    s = ""
    s += "---------------\n"
    for i in range(6):
        for j in range(7):
            s += "|%c" % grid[i*7+j]
        s += "|\n"
    s += "---------------\n"
    s += " 0 1 2 3 4 5 6 \n\n"
    print s

def column_full(grid, col):
    return (grid[col] != ' ')

def add_to_column(grid, col, player):
    newgrid = grid[:]
    pos = -1
    for i in range(5,-1,-1):
        if(grid[i*7+col] == ' '):
            pos = i
            break
    if pos != -1:
        newgrid[pos*7+col] = player
    return newgrid

def win_horizontal(grid, player):
    for i in range(6):
        player_count = 0
        for j in range(7):
            if grid[i*7+j] == player:
                player_count += 1
            else:
                player_count = 0
            if player_count == 4:
                return True
    return False

def win_vertical(grid, player):
    for j in range(7):
        player_count = 0
        for i in range(6):
            if grid[i*7+j] == player:
                player_count += 1
            else:
                player_count = 0
            if player_count == 4:
                return True
    return False

def win_downleft(grid, player):
    for i in range(6):
        for j in range(7):
            player_count = 0
            for (ii,jj) in zip(range(i, 6), range(j, -1, -1)):
                if grid[ii*7+jj] == player:
                    player_count += 1
                else:
                    player_count = 0
            if player_count == 4:
                return True
    return False

def win_downright(grid, player):
    for i in range(6):
        for j in range(7):
            player_count = 0
            for (ii,jj) in zip(range(i, 6), range(j, 7)):
                if grid[ii*7+jj] == player:
                    player_count += 1
                else:
                    player_count = 0
            if player_count == 4:
                return True
    return False

def won(grid, player):
    return (win_vertical(grid, player) or win_horizontal(grid, player) or \
                win_downleft(grid, player) or win_downright(grid, player))

def is_terminal(grid):
    free_moves = False
    for i in range(7):
        if not column_full(grid, i):
            free_moves = True
            break
    return (won(grid, 'A') or won(grid, 'B') or not free_moves)

def next_moves(grid, player):
    moves = {}
    for i in range(7):
        if not column_full(grid, i):
            moves[i] = add_to_column(grid, i, player)
    return moves

def utility(grid):
    if won(grid, 'A'):
        return 1.0
    if won(grid, 'B'):
        return -1.0
    else:
        return 0.0

def estimate_utility(grid, depth):
    return -1.0/depth

def switch_player(player):
    if player == 'A':
        return 'B'
    else:
        return 'A'

def minimax(grid, player, depth = 0):
    # player is A (computer) or B (opponent)
    best_u = None
    best_move = None
    trans = next_moves(grid, player)
    for (move, nextstate) in trans.iteritems():
        if is_terminal(nextstate):
            u = utility(nextstate)
        elif depth > 3:
            u = estimate_utility(grid, depth)
        else:
            # look deeper in the game search tree
            (u, _) = minimax(nextstate, switch_player(player), depth+1)
        # find best utility & move
        if best_u == None or (player == 'A' and u > best_u) \
           or (player == 'B' and u < best_u):
            best_u = u
            best_move = move

    return (best_u, best_move)


def game():
    grid = create_grid()
    player = 'A'
    while True:
        print_grid(grid)

        if player == 'A':
            print "Searching..."
            (u, col) = minimax(grid, 'A')
            print "I choose %d with value %.2f" % (col, u)
            grid = add_to_column(grid, col, player)
        else:
            col = input("Player %c, which column (0-6)? " % player)
            if column_full(grid, col):
                print "\n\nCan't, column full.\n\n"
                continue
            else:
                grid = add_to_column(grid, col, player)

        if won(grid, player):
            print_grid(grid)
            print "\n\nPlayer %c wins!!" % player
            return
        player = switch_player(player)

game()

Day 10

Knowledge representation

Procedural knowledge: the steps of a process; building a bike; a python program; a recipe
Declarative knowledge: factual knowledge, universally true knowledge; the sky is blue; etc

How they differ: declarative knowledge does not include knowledge about how to use it, and it is difficult to get declarative knowledge from procedural knowledge

Properties of declarative knowledge representations:
- surrogates for real world entities, so thinking can be done “in the head” rather than physically manipulating entities in the world
- ontological commitment about what entities matter (i.e., what entities exist)
- theory of intelligent reasoning
- medium for computation, gotta keep it a bit unexpressive (if it’s too powerful, e.g., first order logic, it becomes impossible to reason about efficiently)
- medium for human expression

Boolean logic

True / False, variables x, y, z, …
connectives:
- not x: ¬x
- x or y: x ∨ y
- x and y: x ∧ y
truth tables:

some equivalences:
- x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z)
- ¬(x ∧ y) ≡ ¬x ∨ ¬y
- x ∧ (x ∨ y) ≡ x
- x ∨ (x ∧ y) ≡ x
simplify: z ∨ ¬(y ∧ z) ≡ z ∨ (¬y ∨ ¬z) ≡ (z ∨ ¬z) ∨ ¬y ≡ T ∨ ¬y ≡ T

x	y	x∨y	¬(x ∨ y)
T	T	T	F
T	F	T	F
F	T	T	F
F	F	F	T

Propositional logic

have T/F, x, y, z
also like to represent long formulas as φ, ρ, ψ, etc.
still have ¬, ∨, ∧
add: → (implies, “if”), ↔ (if-and-only-if)
truth table for →

φ ψ φ → ψ

T T T

T F F

F T T

F F T
truth table for ↔

φ ψ φ ↔ ψ

T T T

T F F

F T F

F F T
some equivalences:
- “contrapositive”: φ → ψ ≡ ¬ψ → ¬φ
- p → (q → r) ≡ (p ∧ q) → r

Rules of inference

suppose you have a “knowledge base,” such as:
1. p ∧ ¬q
2. r
3. ¬s → q
what else do you know?
¬q (from line 1)
s (¬q plus modus tollens)

Day 12

First-order logic

constants: jane, john, my_cat
variables: X, Foo, Cat
predicates: is-a-cat(my_cat), blue(sky)
rules: ∀X (is-a-cat(X) → meows(X)) ∀X (is-a-cat(X) ∧ meows(X)) (BAD) ∃X (is-a-cat(X) ∧ has-claws(X)) ∃X (is-a-cat(X) → has-claws(X)) (BAD)
“forall books, there exists an author” ∀X ∃Y (book(X) → author(X, Y))
here is a knowledge database:
- female(jane)
- male(john)
- parent(jane, john)
- ∀X ∀Y (female(X) ∧ parent(X, Y)) → mother(X, Y)
- ∀X ∀Y (mother(X,Y)) → mother(X)
- Horn clause: mother(X,Y) ← female(X) ∧ parent(X, Y) mother(X) ← mother(X,Y) pred(X,Y, …) ← foo(X, Y, …) ∧ bar(X, Y, …) ∧ baz(X, Y, …)

p → q ≡ ¬p ∨ q
∀x(Person(x) → ¬Likes(x, ice-cream)) “all people don’t like ice cream”
¬∀x(Person(x) → Likes(x, ice-cream)) “not all people like ice cream”
¬∀x(¬Person(x) ∨ Likes(x, ice-cream))

∃x(Person(x) ∧ ¬Likes(x, ice-cream))
∃x(Person(x) ∧ ¬Likes(x, ice-cream)) “some people don’t like ice cream”

Prolog

there is a “closed world assumption”: whatever is not stated, is false

Day 13

Prolog

parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).


male(tom).
male(bob).
male(jim).

female(pam).
female(liz).
female(pat).
female(ann).

mother(X) :- parent(X, _), female(X).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

sister(X, Y) :- parent(Z, Y), parent(Z, X), female(X), X \= Y.

%% lists

first(Head, [Head|_]).
second(X, [_,X|_]).

member(E, [E|_]).
member(E, [_|Tail]) :- member(E, Tail).

sum(0, []).
sum(Sum, [X|Tail]) :- sum(SumRest, Tail), Sum is X + SumRest.

average(Avg, List) :- sum(S, List), length(List, L), Avg is S / L.


%% negation?

not_a_mother(X) :- \+(mother(X)).


%% databases

family(10392,
       person(tom, fox, born(7, may, 1960), works(cnn, 152000)),
       person(ann, fox, born(19, april, 1961), works(nyu, 65000)),
       % here are the children...
       [person(pat, fox, born(5, october, 1983), unemployed),
        person(jim, fox, born(1, june, 1986), unemployed),
        person(amy, fox, born(17, december, 1990), unemployed)]).

family(38463, 
       person(susan, rothchild, born(13, september, 1972), works(osu, 75000)),
       person(jess, rothchild, born(20, july, 1975), works(nationwide, 123500)),
       % here are the children...
       [person(ace, rothchild, born(2, january, 2010), unemployed)]).

person(Person) :- family(_, Person, _, _).
person(Person) :- family(_, _, Person, _).
person(Person) :- family(_, _, _, Children), member(Person, Children).

born(Person, Year) :- person(Person),
                      Person = person(_, _, born(_, _, Year), _).

born_between(Year1, Year2, Person) :-
    person(Person),
    born(Person, Year),
    Year =< Year2,
    Year1 =< Year.

all_born_between(Year1, Year2, ThePeople) :-
    findall(P, (person(P),
                born(P, Year),
                Year =< Year2,
                Year1 =< Year),
            ThePeople).

even(N) :- M is N mod 2, M = 0.

keep_only_evens([], []).
keep_only_evens([Head1|Tail1], [Head1|Tail2]) :-
    even(Head1),
    keep_only_evens(Tail1, Tail2).
keep_only_evens([_|Tail1], Tail2) :-
    keep_only_evens(Tail1, Tail2).


filter([], _, []).
filter([Head1|Tail1], Pred, [Head1|Tail2]) :-
    call(Pred, Head1), !,
    filter(Tail1, Pred, Tail2).
filter([_|Tail1], Pred, Tail2) :-
    filter(Tail1, Pred, Tail2).

Day 14

Prolog unification

“unify” a query or goal with something from the source file
- female(X) needs to be unified with something in the file
  - female(pam) looks like it might work.
  - just make X = pam, now they are equivalent
- parent(X, Y) unifies with parent(bob, ann) if X=bob and Y=ann
- family(Id, person(FirstName, _, _, _, _), _, _) would unify with the first family fact if Id=10392 and FirstName=tom

Day 22

Planning

Still a search problem
Purpose: generate a list of actions that take you from starting state to goal state
Consider:
- 10 airports
- 50 planes
- 200 pieces of cargo
- All cargo starts at SFO, needs to be at JFK
- Planes have infinite capacity
- Actions:
  - load cargo into plane: load(p, c)
  - fly to airport: fly(p, a1, a2)
  - unload cargo: unload(p, c)
- 50*200*9*50 = 4.5million possible actions at the start
Solution:
- represent states as partial configurations of the world
- search backwards from the goal

literal: a singular fact with no fluents, e.g., on(monkey, floor); could have negation: not(on(monkey, floor))

Features of a planning problem

Initial state

a conjunction of positive literals (no fluents), e.g.,

on(monkey, floor), at(monkey, 5, 2),
    on(box, floor), at(box, 3, 0), on(bananas, box)

Actions

each action has a name, relevant variables (fluents), preconditions, effects

preconditions can refer to the variables (fluents)
effects have positive and negative parts
- also called add-lists and delete-lists
- these can refer to the variables (fluents)
here is an example action:

action: climb(A, X)
  preconditions: on(A, floor), near(A, X)
  effects:
    add: on(A, X)
    delete: on(A, floor)

Goal state criteria

conjunction of literals, no fluents, can have positive and negative literals

e.g., not(on(monkey, floor)), has(monkey, bananas), ...

Typical assumptions

atomic time (every action is indivisible)
no concurrent actions
deterministic actions
agent is the sole source of change (frame problem)
agent is omniscient
closed world assumption

Day 22

Boids

“birds” – flocking behavior
each boid has these rules:
- cohesion: try to approach other boids
- separation: try to keep a minimum distance
- imitation: try to move the same way as other boids

Altruism model

each patch’s calculation:
- if patch is altruistic:
  - F = 1 + (# of altruists nearby / 5) * benefit-from-altruism - cost-of-altruism
- if patch is selfish:
  - F = 1 + (# of altruists nearby / 5) * benefit-from-altruism
higher harshness: reduces the chance of a patch turning either altruistic or selfish. Limits population growth.

Termite collecting

predesignated collection spot:
- check: is all sand in the pile?
  - if not, do I have sand?
    - if yes, take it to pile, drop off
    - else, pick up sand not in pile, then start over
use flocking behavior to group together,
- if encounter sand, pick up along the way,
- drop off after flocking behavior is terminated
  - (all sand should be in nearly same spot)
what actually happens:
- each termite wanders randomly
- if it bumps into sand and has none in its mouth, it picks it up
- if it bumps into sand and has some, it finds a nearby empty space and drops its sand

Principles of designing multi-agent systems

agents not functions (i.e., independent acting entities)
keep them small in size (not much knowledge)
keep them small in time (forgetful)
keep agents small in scope (look only locally, etc.)
decentralized system control

Day 23

HCOMP 2014

http://www.humancomputation.com/2014/

In the news

http://www.computerworld.com/s/article/9226851/Crowdsourcing_game_helps_diagnose_infectious_diseases

Ant sorting

wander randomly
sense nearby objects and maintain a small queue of what has been seen
if not carrying anything, and at an object, decide stochastically whether or not to pick it up
- probability of picking it up decreases if this color has been seen recently
- p = (K+ / (K+ + F))^2
  - F is the fraction of items in memory of same color
  - K+ is a constant
  - if F becomes small compared to K+, p trends up (certainty)
if carrying something, drop according to:
- p = (F / (K- + F))^2
- if seen this color recently, more chance that you’ll drop it

Prisoner’s dilemma

if you screw over a nice person you win
you and your partner committed a crime
- you are both arrested
- the cops don’t have much on you
- if you defect (rat out your partner), AND your partner stays silent, you get no jail time, partner gets 5 years
- if you cooperate (stay silent), AND your partner cooperates, you both get 1 year
- if you both defect, you both get three years
what is your best option (if you don’t communicate)
- if you never see your partner again
- always defect

Y	P	Y	P
D	D	-3	-3
D	C	0	-5
C	D	-5	0
C	C	-1	-1

Day 24

Machine learning

clustering: grouping data, without really having a clue what the right groups are
classification: take a single data point and predict its class
why use clustering?
- Wolfram Alpha, connect to facebook
- marketing: get an idea of demographics, are there distinct groups of consumers
- exploratory analysis
why use classification?
- facebook tags faces automatically
- finding porn, and filtering it out
- detect copyrighted videos
- spam
- separating email by promotions, social, etc.
- xbox kinect detecting gameplay speaking vs. other speaking
  - and various motions
- cheating analysis
with clustering, you don’t have predefined groups (classes)
- you also don’t have the answers
with classification, you do
- you also have some training set

K-means clustering

groups data into clusters
you have to decide k, i.e., how many clusters (decide a priori)
“closest” – Euclidean distance, Manhattan distance
- each of these require that all dimensions are numeric
  - not all features are necessarily numeric
    - e.g., ethinicity, gender, country-of-residence, etc.
the centroids live in the feature space
- must be able to generate new centroids as averages of points
algorithm:
- randomly select k centroids
- now loop:
  - for each point, determine the closest cluster
  - recompute centroids as averages of points for each cluster
  - repeat, until centroids don’t change
k-means assumes clusters have “spherical” distributions
- actually, the partition of the space is not spherical, it’s a Voronoi diagram
  - every possible point is closest to some cluster (or equidistant)
  - can ask about a new point, which cluster is it in?

Day 25

k-nearest neighbor is a way to do classification (not clustering)
scenario for classification:
- you’ve got a lot of example points (with known classes)
- you’ve got a new example, with an unknown class
- what do you do?
  - figure out which point of which class is closest
    - according to, say, euclidean distance
  - or better, give each k closest points a “vote”
    - problems with large/small k:
      - if k is too small, noise has too great of an impact
      - if k is too large, the dominant class has too large of an impact
k-nearest neighbor algorithm:
- for new point X, find k closest known points
- give each point a vote for that class
- X gets class of most votes
variations:
- weigh the vote by closeness: closer points get bigger vote
  - vote is worth 1/distance(p, X)

Classification evaluation

we have one dataset with known classes
- let’s split it into a training and testing set (say, 90/10%)
what are we interested in when we classify a set of points?
- true positive (TP): the predicted class is the true class
- false positive (FP): the predicted class is false
- false negative (FN): failed to predict the true class
- precision: tp/(tp+fp) – fraction of times it said “A class” and got it right; in other words, fraction of responses about A class that were correct
- recall: tp/(tp+fn) – fraction of times it said “A class” over number of things in A class; in other words, fraction of A class things it correctly identified (recalled)
- these measures come from information retrieval (e.g., search engines)
  - imagine searching for “machine learning”
  - get high precision but lose on recall by doing:
    - it gives you just a couple good articles about ML, but misses many
  - get high recall but lose on precision by doing:
    - give back the internet (surely it gets all the ML articles in there)
- so we have two metrics (precision/recall) that somewhat compete
  - it’s a tradeoff
  - another metric: precision/recall
  - another metric: the arithmetic average
  - another metric: the harmonic average (F-score)

Day 26

Chinese room argument (Searle)

Weak AI

Can help test psychological theories
Not positing that the software is conscious or understands something

Strong AI

The program is a mind
It truly understands things
Is the psychological theory

Schank’s scripts

Here’s a story:

A man went into a restaurant and ordered a hamburger. When the hamburger arrived it was burned to a crisp, and the man stormed out of the restaurant angrily, without paying for the hamburger or leaving a tip.

Did the man eat the hamburger? No

A man went into a restaurant and ordered a hamburger; when the hamburger came he was very pleased with it; and as he left the restaurant he gave the waitress a large tip before paying his bill.”

Did the man eat the hamburger? Yes

Scripts

Are templates for stories; depending on the story, a certain template is activated (e.g., the restaurant template), and can fill in missing details.

If it answers correctly, consistently, we can say the software understands what happened in the story.

Searle’s counterargument

The setup

The assumption: Searle does not understand Chinese
Searle is stuck in a room
Three books:
- Book 1: Chinese symbols
- Book 2: Chinese symbols + English rules that utilize books 1 & 2
- Book 3: Chinese symbols + English rules that utilize books 1 & 2
What happens?
- Searle gets a message from the outside, in Chinese
- He looks in books 1 & 2 & 3 and follows the English rules for matching and correlating symbols, and spits out another Chinese symbol
Clearly,
- Searle is the computer
- The English rules are the program
- The books are the data

What if I told you that:

Searle was responding correctly, in Chinese, to Chinese questions about Chinese stories?

Questions

Does Searle understand Chinese?
- No
Does this program (the whole room) explain human understanding?
- No, there is no understanding anywhere
What does Searle “have” in the case of English that he doesn’t have in the case of Chinese?

Possible replies

Brain simulator reply

The point

formal symbols and their manipulation will never produce “understanding” or mental states
while on the other hand, when I think about “rain”, I’m thinking about rain, not the string “r a i n”

Robot ethics

Scenario: a self-driving car will hit a bus with children inside, or it can swerve into traffic and hit a mother
What are the ethical issues, from a computational standpoint?
- What is the right action?
- How to compute it?
- Who is responsible?
What are the ethical dimensions of an elevator?

Asimov’s three laws

Robot cannot harm a human, or by inaction, allow a human to come to harm.
Has to obey orders of a human, unless it violates first rule.
Robot shall preserve itself unless that violates rule 1 or 2.

Issues with Asimov’s three laws

Are they computable?
No consideration of time
Curious question: Suppose you write a computer program for “ethical questions”, and then you ask it about abortion.
The harm may be “emergent” – e.g., telling a robot to forget what it just did.

Machine ethics (computable ethics)

Implicit ethical agents: e.g., ATM machine that gives the correct amount of money; or passwords, privacy, etc.
Explicit ethical agents: it actually reasons about ethical dilemmas and has “data” that represents ethical concepts
Bentham’s utilitarianism (1748-1832)

φ	ψ	φ → ψ
T	T	T
T	F	F
F	T	T
F	F	T

φ	ψ	φ ↔ ψ
T	T	T
T	F	F
F	T	F
F	F	T

Files

daily-notes.org

Latest commit

History

daily-notes.org

File metadata and controls

Daily notes

Day 1

What is AI?

Examples of AI

Day 2

How do we test for AI?

The Turing Test

The imitation game

Replace the man with a machine

What’s “success”?

Dennett’s weaker versions

Langley’s challenges

Day 3

Python

Search

Example: Wolves & chicks

Basic BFS algorithm:

Basic DFS algorithm:

Day 4

Informed search

Day 5

Pacman

Heuristics for 8-puzzle

Heuristics for Goodale routing

Hill-climbing

Best-first search

Again with the heuristics

Goodale

A*

Websites

Day 6

A*

Heaps

Cost functions (path-cost + heuristic)

What’s the number associated with a state?

Day 8

Zero-sum games

Tic-tac-toe

Day 9

Connect-four code with depth-limited minimax

Day 10

Knowledge representation

Boolean logic

Propositional logic

Rules of inference

Day 12

First-order logic

Prolog

Day 13

Prolog

Day 14

Prolog unification

Day 22

Planning

Features of a planning problem

Typical assumptions

Day 22

Boids

Altruism model

Termite collecting

Principles of designing multi-agent systems

Day 23

HCOMP 2014

In the news

Ant sorting

Prisoner’s dilemma

Day 24

Machine learning

K-means clustering

Day 25

Classification evaluation

Day 26

Chinese room argument (Searle)

Weak AI