Transcript Review - Columbia University

Class Wrap-up
Written HW 3 returned on Wednesday, my office. Or can
be picked up in final.
Paper returned in final exam
Grades will be posted before Christmas
Office hours this week and next:
Kathy: Wed 3:30-4:30 (12/12), Mon 1-2 (12/17), Tues 23 (12/18)
TAs will post a notice if there is any change. Otherwise
assume as usual.
FILL OUT CLASS EVALUATION FORM. MAKE COMMENTS.
1
Life After AI
Research Projects


Send email to
[email protected]
http://www.cs.columbia.edu/~proje
ct
3
Research Projects

Natural Language Processing







Kathy McKeown
Julia Hirschberg
Owen Rambow (CCLS)
Becky Passonneau (CCLS)
Mona Diab (CCLS)
Nizar Habash (CCLS)
Text Classification



Given a question, is a sentence in a relevant
document an answer?
Given a translated/transcribed sentence,
which English sentence is it closest in meaning
to?
NL/UI/Medical collaboration
4
Research Projects

Vision
Shree Nayar
 Peter Belhumeur
 John Kender


Data mining


Sal Stolfo, but on sabbatical this year
Machine Learning
Tony Jebara
 Rocco Serveddio (theoretical)

5
Stop by and visit

CS Advising

Recommendation letters

Research project

Advice on applying to graduate
school
6
Final Exam


Wednesday, December 19th, 833 Mudd
Cumulative exam


Slightly more focus on second half of class
 Knowledge Representation
 Logic and inference
 First order logic
 Probabilistic Reasoning and Bayes Nets
 Machine learning
 Vision
 Natural Language processing
But can expect search, game playing,
constraint satisfaction to be covered
7
Exam Format

Multiple Choice

Short answer

Problem solving

Essay
8
Problems






Proof by Refutation
FOL
Bayesian Nets
Machine learning
Vision/NLP
Essay
9
Refutation/Resolution




Introduce negated sentence
Convert to a CNF (disjunction of terms, or
“literals”)
Apply resolution search to determine
satisfiability (SAT) or unsatsifiability
(UNSAT)
SAT, then not entailed


Semi-decidability implies there may be a
SAT solution we can never find
UNSAT, then entailed
10
Inference Properties



Inference method A is sound (or truthpreserving) if it only derives entailed
sentences
Inference method A is complete if it can
derive any sentence that is entailed
A proof is a record of the progress of a
sound inference algorithm.
11
Resolution


Prove: (DVE)
KB: (A-> CVD)
(AVDVE)
(A-> ⌐C)
12
Negate Goal
13
Negate goal


⌐(DVE)
⌐DΛ⌐E
14
Convert to Conjunctive Normal Form
15
16
Convert to Conjunctive Normal Form
Equivalence: A->B = ⌐AVB
1.
2.
3.
4.
5.
(⌐AVCVD) Λ
(AVDVE) Λ
(⌐AV⌐C) Λ
⌐D Λ
⌐E
17
Apply resolution rule
18
Apply resolution rule
1.
2.
(⌐AVCVD)
(AVDVE)
(CVDVE)
2. (AVDVE)
3. (⌐AV⌐C)
(DVEV⌐C)

R1: (CVDVE)
R2: (DVEV⌐C)
(DVE)

R3: (DVE)
4. ⌐D
E

R4: E
5. ⌐E
contradiction
19
FOL

[4 points] Using First Order Logic,
write axioms describing the
predicates Grandmother, Cousin.
Use only the predicates Mother,
Father, sibling in your definitions.
20
x y w  z grandmother(x,y) ↔
mother (x,z)  ((father(z,y) V
mother z(y))
x y w  z cousin (x,y) ↔
(mother(z,x)  sibling(z,w) V
father(z,x)  sibling(z,w)) 
(mother(w,y) V father (w,y))
21
[4 points] Translate each of the following
English sentences into the language of
standard first-order logic, including quantifiers.
Use the predicates French(x), Australian(x),
Wine(x), , and the functions Price(x) and
Quality(x)



All French wines cost more than all Australian wines.
The best Australian wine is better than some French
wines.
22


wy French (w)  Australian (y) 
Price (w)  Price (y)
z  w  y Australian (z) 
Australian (w)  French (y) 
(quality (w)  quality (y))  (
quality(w)  quality (z))
23
Bayesian Networks:
What do you need to know?





Why are independence and conditional
independence important?
What is Bayes’ Rule used for? How?
How to construct a Bayesian net for a
given problem
What are the independence assumptions?
How to do inference using a Bayesian net
(i.e, what does it predict?)
24
An Example

Smoking causes cancer
Graph?
 Conditional Probability Tables?

25
26
How do we compute inferences?


What is the probability that a
person has a malignant tumor and
is not a smoker?
What is the probability that a
person has a benign tumor given
that she is a light smoker?
27
28
a
c
Converging
a
b
b
Diverging
b
Linear
c
a
c
31
D-separation (opposite of d-connecting)

A path from q to r is d-connecting with respect
to the evidence nodes E if every interior node
n in the path has the property that either



It is linear or diverging and is not a member of E
It is converging and either n or one of its
decendants is in E
If a path is not d-connecting (is d-separated),
the nodes are conditionally independent given
E
32
33




Are age and gender independent?
Is cancer independent of age and gender
given smoking?
Is serum calcium independent of lung
tumor?
Is serum calcium independent of lung
tumor given cancer?
34
35
36
37
Advanced approaches
NLP and vision

How much do you need to know?
Some idea of the applications
 Some idea of the approaches




Reduction to simpler problems: e.g. edge
detection
NLP: syntax, semantics, pragmatics,
statistics
How do these applications fit into our view
of artificial intelligence?
38
[2 points] Answer this question for
either the natural language problem or
the vision problem (not both):



Vision: You are writing a supervised learning
program to identify the handwritten digits 19. What would your training material be?
What features might your program use?
Natural language: You are writing a
supervised learning program to translate
from French to English. What would your
training material be? What features might
your program use?
39



3. Learning from Observations (10 points)
Ms Apple I. Podd is a Columbia University
Computer Science major who listens to music
almost everywhere she goes. She often has
homework due and many of them involve
programming. We’ve sampled her choice of music
genre over several points in time.
Naive Bayes is another machine learning method,
but is based on probabilities. The formula below
can be used to compute the most probable target
category given a new instance. Suppose a friend of
yours observes Ms. Podd in the morning. She has
homework due and it does not involve
programming. Use the formula to show what type
of music Naïve Bayes will predict she is listening to.
VNB = argmax P(vj)iP(ai|vj)
vjV
40
VNB = argmax P(vj)iP(ai|vj)
vjV
TimeOfDay
Morning
Morning
Morning
Morning
Afternoon
Afternoon
Evening
Evening
HomeworkDue?
Yes
No
No
Yes
Yes
No
No
Yes
Programming?
No
No
Yes
No
Yes
No
Yes
Yes
MusicType
Classical
Pop
Classical
Classical
Pop
Pop
Pop
Classical
41
Knowledge Representation



Given an entry in WordNet, show the
pieces of the ontology that are implied
Given a machine learning problem, show
how the ontology might be used to
improve accuracy of learning
Given a statement in English, show how
to represent it in semantic network
42
Thank you, good luck on the final
exam, and have a great winter
break!
See you on the 19th!
43