Knowledge Representation and Reasoning
- 1. Knowledge Representation and Reasoning (KRR) The new Machine Learning? - Dhananjay Pandit
- 2. Agenda for today A whirlwind tour of KRR intended to instil interest What is intelligence? AI and KRR Whats wrong with Machine Learning? Encoding KRR Code Examples Applications
- 3. Intelligence The ability to acquire and apply knowledge to manipulate ones environment or to think abstractly as measured by objective criteria. Capacity for learning, reasoning, understanding, and similar forms of mental activity; aptitude in grasping truths, relationships, facts, meanings, etc.
- 4. AI and KRR AI can now be described as the study of intelligent behavior achieved through computational means. Knowledge Representation and Reasoning can be viewed as the study of how to reason (compute) with knowledge in order to decide what to do Think about knowledge, rather than data
- 5. Representation v/s Reasoning -> Smile / Happy John -> John John likes Math -> Proposition that John likes mathematics Field of study concerned with representations of propositions which are believed by some agent If it is raining and Jane does not have her umbrella with her, then she will get wet. Jane is not wet. It is raining Form of calculation over symbols standing for propositions rather than numbers
- 6. Whats wrong with Machine Learning? Googles TensorFlow alone will not revolutionize AI https://www.wired.com/2015/11/tensorflow-alone-will-notrevolutionize-ai/ When AI systems make bad decisions, we need to be able to understand why they made those decisions and communicate with them to fix the problem Heres an event sequence for cooking as learned by a machine learning system: A boil B, A slice B, A peel B, A saut辿 B, A cook B, A chop B.
- 7. Why should you be excited about KRR? Satisfiability solvers (SAT solvers) are becoming better every year www.satcompetition.org Encoding and debugging KRR rules is easier and more intuitive SAT solvers have been consistently beating imperative programming languages for the past few years The medical and auto industry has started to take notice of this field of AI
- 8. Encoding KRR Most imperative programming languages are ill-equipped to encode KRR Languages used to encode KRR: Logic Programming: Prolog Constraint Programming: Prolog and Clingo Answer Set Programming: Clingo, BC+ Probabilistic Logic: Alchemy Semantic Web: OWL, RDF Lets see an example
- 9. 8-Queens Problem Constraint Programming using Clingo can solve it faster and in fewer lines of code. 1. Define N * N board 2. Each column has exactly one queen 3. Each row has exactly one queen 4. Each diagonal has exactly one queen All 92 solutions found in less than 1/1000th of second
- 10. Graph Coloring c(1..n). % Each vertex is mapped to a color 1{color(vert,col) : c(col)}1 :- vertex(vert). % Adjacent vertices should be different color :- color(v1,c), color(v2,c), edge(v1,v2).
- 11. Reasoning about Actions Missionaries and Cannibals Puzzle How can they cross the river? Monkey and Bananas How can the monkey grab the bananas?
- 12. Monkey and Bananas Solution
- 13. Applications Jeopardy Solver IBM Watson QA System for DIY: Can I use a table saw instead of a jigsaw? IoT Reasoning: Insulin pump, Home security Cognitive Robotics Combinatorial Search Problems: Wire Routing Access Control Policy and Security Protocol Analysis Resource Description Framework: Knowledge Graph
- 14. Theres more where that came from Classes at ASU involving KRR: CSE 579 Knowledge Representation SER 502 Languages and Programming Paradigms SER 5** Semantic Web Read my article on Medium
Editor's Notes
- #4: What is intelligence, according to you?
- #5: KRR is at the heart of the great challenge of AI: to understand the nature of intelligence and cognition so that computers can be made to exhibit human-like abilities.
- #6: Knowledge is necessary for intelligent behaviour. We will not try to answer the question What is knowledge?. Lets talk about representations of knowledge. What can you tell from the statements on the right? JANE HAS HER UMBRELLA WITH HER.
- #7: Recent self-driving car incidents Uber, Tesla. Suppose we a train an ANN to recognize cats. When it recognizes a previously unseen cat in an image, it cannot explain to us why or how it did this. And if the ANN fails to recognize the spotted cat, its hard for us to fix the problem. Cant tell change element 341375s value from 0.3265 to 0.4271, etc. To a human cook, many of these tasks appear to be out of order (one typically peels before slicing, and chops before cooking). These are top-ranked results generated by state-of-the-art machine learning systems. Lower ranked results are worse.
- #8: Samsung Researcher position requirements
- #9: You could use imperative languages but you wont be able to harness the power of either concept. Various subdomains under KRR just like imperative is divided into procedural, OO, etc.
- #10: Who knows the 8-queens problem? Least number of lines of code you think youll need in your favorite language.
- #11: No 2 adjacent vertices should have the same color
- #12: If number of cannibals on a bank is more than the number of missionaries, the cannibals will eat the missionaries. Though the problems may seem like toy problems without any significance in the real world they in fact encode a very important problem called The Frame Problem. How do you encode common sense logic into the robot? Yale Shooting Problem
- #13: Without getting into the details of the encoding, heres the result which the language BC+ generates. It shows the initial state, the action taken and the effect of the action
- #14: In addition to this, there are many opportunities in the auto industry with extremely high pay scales. This is literally the tip of the iceberg. You can do a lot more things with KRR.