CS621: Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept., IIT Bombay
Lecture–8: (a) Some Proofs in Formal System;(b) How to read research papers
5th August, 2010
Hilbert's formalization of propositional calculus 1. Elements are propositions : Capital letters
2. Operator is only one : (called implies) 3. Special symbol F (called 'false')
4. Two other symbols : '(' and ')'
5. Well formed formula is constructed according to the grammar WFF P|F|WFFWFF
WFF P|F|WFFWFF 6. Inference rule : only one
Given AB and A
write B
known as MODUS PONENS
7. Axioms : Starting structures A1:
A2:
A3
This formal system defines the propositional calculus ))
(
(A → B → A
))) (
) ((
)) (
((A → B → C → A → B → A → C
) )
)
(((A → F → F → A
Notion of proof
1. Sequence of well formed formulae 2. Start with a set of hypotheses
3. The expression to be proved should be the last line in the sequence
4. Each intermediate expression is either one of the hypotheses or one of the axioms or the result of modus ponens
5. An expression which is proved only from the axioms and inference rules is called a THEOREM within the system
Example of proof
From P and and prove R H1: P
H2:
H3:
i) P H1
Q P →
Q P →
R Q →
R Q →
ii) H2
iii) Q MP, (i), (ii)
iv) H3
v) R MP, (iii), (iv)
Q P →
R Q →
Prove that is a THEOREM
i) A1 : P for A and B
ii) A1: P for A and for B
iii)
A2: with P for A, for B and P for C
iv) MP, (ii), (iii)
) (P → P
) )
((P P P
P → → →
)
(P P
P → →
))]
( ))
( ((
)) )
((
[(P → P → P → P → P → P → P → P → P
) (P → P ))
( )
(
(P → P → P → P → P
) (P → P
v) (P → P) MP, (i), (iv)
Shorthand
1. is written as and called 'NOT P'
2. is written as and called 'P OR Q’
3. is written as and called
'P AND Q'
¬P P → F
) )
((P → F →Q (P ∨Q)
) ))
(
((P → Q → F → F (P ∧Q)
'P AND Q' Exercise: (Challenge)
- Prove that A → ¬(¬(A))
A very useful theorem (Actually a meta theorem, called deduction theorem)
Statement If
A1, A2, A3 ... An ├ B then
A1, A2, A3, ...An-1├
├ is read as 'derives'
B An →
Given
A1 A2 A3 . . . . An
B Picture 1
A1 A2 A3 . . . . An-1
Picture 2
B An →
Use of Deduction Theorem Prove
i.e.,
├ F (M.P)
A├ (D.T)
)) (
( A
A → ¬ ¬
) )
((A F F
A → → →
F A
A, →
F F
A → ) → (
├ (D.T)
Very difficult to prove from first principles, i.e., using axioms and inference rules only
) )
((A F F
A → → →
Prove i.e.
├ F
├ (D.T)
├ Q (M.P with A3)
) (P Q
P → ∨
) )
((P F Q
P → → →
F Q
F P
P, → , →
F P
P, → (Q → F) → F
├ Q (M.P with A3)
P├
├
Q F
P → ) → (
) )
((P F Q
P → → →
More proofs
) (
) (
.
1 P ∧ Q → P ∨ Q
) )
((
) (
. 3
) (
) (
. 2
) (
) (
. 1
Q P
Q Q
P
P Q
Q P
Q P
Q P
→
→
¬
→
→
¬
→
¬
→
→
∨
→
∧
Proof Sketch of the Deduction Theorem
To show that If
If
A1, A2, A3,… An |- B Then
A1, A2, A3,… An-1 |- An B
Case-1: B is an axiom
One is allowed to write A1, A2, A3,… An-1 |- B
|- B(A B)
|- B(AnB)
|- (AnB); mp-rule
Case-2: B is A
n
AnAn is a theorem (already proved) One is allowed to write
A , A , A ,… A |- (A A ) A1, A2, A3,… An-1 |- (AnAn)
i.e. |- (AnB)
Case-3: B is A
i where (i <>n)
Since Ai is one of the hypotheses One is allowed to write
A , A , A ,… A |- B A1, A2, A3,… An-1 |- B
|- B(AnB)
|- (AnB); mp-rule
Case-4: B is result of MP
Suppose
B comes from applying MP on E and E
Ei and Ej
Where, Ei and Ej come before B in A1, A2, A3,… An |- B
B is result of MP
(contd)If it can be shown that
A1, A2, A3,… An-1 |- An Ei and
and
A1, A2, A3,… An-1 |- (An (EiB)) Then by applying MP twice
A1, A2, A3,… An-1 |- An B
B is result of MP
(contd)This involves showing that If
A , A , A ,… A |- E A1, A2, A3,… An |- Ei Then
A1, A2, A3,… An-1 |- An Ei
(similarly for AnEj)
B is result of MP
(contd)Adopting a case by case analysis as before,
We come to shorter and shorter length We come to shorter and shorter length
proof segments eating into the body of A1, A2, A3,… An |- B
Which is finite. This process has to terminate. QED
Important to note
Deduction Theorem is a meta-theorem (statement about the system)
PP is a theorem (statement belonging to the system)
PP is a theorem (statement belonging to the system)
The distinction is crucial in AI
Self reference, diagonalization
Foundation of Halting Theorem, Godel Theorem etc.
Example of ‘ of-about’
confusion
“This statement is false”
Truth of falsity cannot be decided
HOW TO READ RESEARCH PAPERS
PAPERS
Before that: How to read a book
1940 classic by Mortimer Adler
Revised and coauthored by Charles Van Doren in 1972
Doren in 1972
Guidelines for critically reading good and great books of any tradition
Three types of Knowledge
• Practical
– though teachable, cannot be truly mastered without experience
• Informational
• Informational
– that only informational knowledge can be gained by one whose understanding equals the author's
• Comprehensive
– comprehension (insight) is best learned from who first achieved said understanding — an "original communication
Three Approaches to Reading (non-fiction)
• Structural
– Understanding the structure and purpose of the book
– Determining the basic topic and type of the book
– Distinguish between practical and theoretical books, as well as determining the field of study that the book addresses.
– Divisions in the book, and that these are not restricted to the divisions laid out in the table of contents.
the table of contents.
– Lastly, What problems the author is trying to solve.
• Interpretative
– Constructing the author's arguments
– Requires the reader to note and understand any special phrases and terms
– Find and work to understand each proposition that the author advances, as well as the author's support for those propositions.
• Syntopical
– Judge the book's merit and accuracy
• AKA, Structure-Proposition-Evaluation (SPE) method
VERY PRACTICAL
From Wikihow!
Steps
Find a book
Buy/rent it and take it home
Settle into a comfortable chair or get comfortable on the couch
Be calm and alert
Start the book by turning the pages
Read and enjoy it
Close book
Warnings
Do not forget about your daily life.
Check the time and take a break every once in a while.
If the book is rented, then be very
If the book is rented, then be very
careful to not damage it, and return it on time.
You will pay for lateness, and is not fun.
If you read the book in a bus/subway, then be careful to not miss the station where you should go off.
Reading research papers
From Philip W. Fong
http://www2.cs.uregina.ca/~pwlfo ng/CS499/reading-paper.pdf
Comprehension: what does the paper say
A common pitfall for a beginner is to focus solely on the technicalities
Technical content is no way the only
Technical content is no way the only focus of a careful reading
Question-1: What is the research problem the paper attempts to
address?
What is the motivation of the research work?
Is there a crisis in the research field that the paper attempts to resolve?
paper attempts to resolve?
Is the research work attempting to overcome the weaknesses of existing approaches?
Is an existing research paradigm challenged?
In short, what is the niche of the paper?
How do the authors substantiate their claims?
What is the methodology adopted to substantiate the claims?
What is the argument of the paper?
What are the major theorems?
What experiments are conducted? Data
What experiments are conducted? Data analyses? Simulations? Benchmarks? User studies? Case studies? Examples?
In short, what makes the claims scientific (as opposed to being mere opinions (science as opposed to science fiction)
What are the conclusions?
What have we learned from the paper?
Shall the standard practice of the field be changed as a result of the new
findings?
Is the result generalizable?
Is the result generalizable?
Can the result be applied to other areas of the field?
What are the open problems?
In short, what are the lessons one can learn from the paper?
VVIMP
Look first to the abstract for answers to previous questions
The paper should be an elaboration of the
The paper should be an elaboration of the abstract.
Every good paper tells a story
ask yourself, “What is the plot?”
The four questions listed above make up a plot structure
Evaluation
An integral component of scholarship:
critical of scientific claims
Fancy claims are usually easy to make but difficult to substantiate]
but difficult to substantiate]
Solid scholarship involves careful validation of scientific claims
Reading research paper is
therefore an exercise of critical thinking
Evaluation question-1: Is the research problem significant
Is the work scratching minor itches?
Are the authors solving artificial problems
problems
Does the work enable practical applications, deepen
understanding, or explore new design space?
Are the contributions significant?
Is the paper worth reading?
Are the authors simply repeating the state of the art?
state of the art?
Are there real surprises?
Are the authors aware of the relation of their work to existing literature?
Is the paper addressing a well-known open problem?
Are the claims valid?
Have the authors been cutting corners (intentionally or unintentionally)?
Has the right theorem been proven? Errors in proofs? Problematic experimental setup?
Confounding factors? Unrealistic, artificial Confounding factors? Unrealistic, artificial
benchmarks? Comparing apples and oranges?
Methodological misunderstanding?
Do the numbers add up?
Are the generalizations valid?
Are the claims modest enough?
Synthesis: your own research agenda coming from the reading of the
paper
Creativity does not arise from the void.
Interacting with the scholarly
community through reading research community through reading research
papers is one of the most effective way for generating novel research agendas
When you read a research paper, you should see it as an opportunity for you to come up with new research projects
Cautionary note
Be very skeptical of work that is so
“novel” that it
bears no relation to any existing work,
builds upon no existing paradigm, and yet addresses a research problem so
addresses a research problem so
significant that it promises to transform the world
Such are the signs that the author might not be aware of existing literature on the topic
Repeat of work done decades ago?
Questions to help formulate research agenda
What is the crux of the research problem?
What are some alternative approaches to address the research problem?
What is a better way to substantiate the claim of the authors?
authors?
Questions to help formulate research agenda
What is a good argument against the case made by the authors?
How can the research results be improved?
Can the research results be applied to another context?
context?
What are the open problems raised by this work?
Bottomline: Can we do better than the authors?
