In Natural Language

• Refining:
• A page that has the extended spelling of Google
• A page that contains  Gooogle
• A page that contains a substring Gooo
• A page that has a substring Goo followed by one or more os, then by gle
Issues:
• Vagueness and imprecision
• We can work on this
• Useless to a computer
• We have a spec, not a recognizer!

As Computer Code

i = indexOf('G', page)
oCount = 0
flag = true
while flag
   i += 1
   if page[i] == o
      oCount +=1
   else
      flag = false
if oCount < 3
   then print("Not a results page!")
if page[i:i+3] == 'gle'
   then print("A results page!")

A Formalism

• We could design a language for strings
• Basic characters: a-zA-Z 
• * for zero or more
• This allows us to represent a class of strings, i.e.:
• Goooo*gle (the Google search bar)
• To exploit the representation, we use search
• search("Goooo*gle", "Gogle") ⇒ false
• search("Goooo*gle", "Google") ⇒ false
• search("Goooo*gle", "Gooogle") ⇒ true
• search("Goooo*gle", "Goooooogle") ⇒ true
• Our code becomes much shorter:
• if search("Goooo*gle", page) then print...else print...
• And more portable

Extending the Formalism

• We could add expressivity
• More characters: 0-9!
• | for alternation
• (Parens for grouping)
• This allows us to say more about strings
• (Ya|G)oooo*(gle|!)
• (Supposing Yahoo! used the same indicator)
• We might design other services
• equiv("(Ya|G)oooo*(gle|!)","Yahoooo*!|Goooo*gle")
• contained_in("Yahooo*!","Ya|G)oooo*(gle|!)")
• Or other tools
• Optimizers
• http://www.let.rug.nl/~vannoord/fsademo/

Knowledge Representation

• Four aspects
• Domain (the subject matter)
• Representation (what can you say)
• Reasoning (what follows from what you said?)
• Application
• In our example
• The domain covers web pages
• The represenations were expressed as regexps
• The reasoning was  regexp matching
• The application...

3 Foci of KR

Represent commonsense knowledge
• Cyc project
• Naive physics mainfesto
Represent scientific knowledge
• A branch of scientific computing
• Big in bio-informatics
• Other specialized areas: law, medical-informatics, mathematics, etc.
Conceputal modeling
• UML, CRC cards, ER diagrams
• Related to Formal Methods
These do not differ so much in domain but in style
• also, purpose, detail, application, use

Next Class

• We'll start on the knowledge acquisition problem
• Specifically, on acquiring knowledge from human experts
• How to conceptualize a domain
• Analogous to our attack of the search results page problem