Home

Daily notes

Table of Contents

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
  • Three wolves and three chicks on same side
  • Put a chick on the boat, put a wolf on the boat, move the boat across
  • A function from state to [list of states] and for this problem, the list of states are those that do not kill the chicks
  • All on other side
  • 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*

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:
x y x∨y ¬(x ∨ y)
T T T F
T F T F
F T T F
F F F T
  • 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

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
  • 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

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

  1. Robot cannot harm a human, or by inaction, allow a human to come to harm.
  2. Has to obey orders of a human, unless it violates first rule.
  3. 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)
Intro to AI material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.