Automating Commonsense Reasoning

Key Takeaways

hello everyone um it is my utmost pleasure to welcome Dr gopal Gupta from UT Dallas um to give us an invited talk he is a professor of computer science at UT Dallas and the co-director of the Center for Applied Ai and machine learning at UT Dallas he was also the Eric Johnson chair of the Cs Department until like two years ago and uh he has also presided over many uh scientific organizations including Association for logic programming um I don't want to spend too much time in cut into the talk but uh his research area span like a huge Horizon from PL to logic programming to Ai and in recent times he has been interested in automated reasoning explainable Ai and AGI for example and his lab has published many papers and developed many uh actionable software systems that have become the basis of many startup companies um and one important thing is uh he his lab has won the best paper award for at iclp 2016. uh the test of time sorry not the best paper the test of time award for their co-inductive logic programming work and uh um the team was also selected to compete in the Amazon Alexa prize for social board challenge uh 20 20 21. and from a personal side he was a part of my PhD advisory committee the most important part and uh apart from all the technical things I know him as like this very calm very assuring person and uh there were there were times when I was uh very um you know tensed about things like filling up my form that I needed to submit I I'm I'm like a last-minute person so so I I was trying to fill up a form that you have to submit in order to schedule your thesis defense so I was very late I had like the deadline was in two days so he assured me don't worry we'll get it done we'll get it done so he was just leaving at 5 PM I went to him he's like what do I do now so so he assured me and we got the things done and uh happily I graduated in time anyway please over to him and today he's going to talk about his work on automating Common Sense reasoning uh and uh would you take questions in between yeah sure sure please please ask yeah so we hopefully we will not spill over one hour but you know if you if I spill over one hour feel free to leave you know whoever happens or anything okay okay the mic is with me uh whoever wants to ask a question I can run ahead and give the mic thank you thank you may you for the hospitality and for the generous introduction so my great pleasure to be here I was I actually gave a talk on co-inductive logic programming which actually relates to the work I'm going to talk about here as well I think maybe five years ago and in fact that talk is on uh on you know Microsoft server somewhere it's on the on the web and when people Google me it showed up and I actually use it for my logic programming class as well so it's nice I can miss one lecture and just play the video so that helps um okay so I'm going to talk about automating common sense reasoning so quick overview so what do we want to do we want to formalize the human thought process which essentially means automate common sense and reasoning right the reasoning we do is called Common Sense reasoning and the goal is Advanced general intelligence essentially we want to be able to reach that goal of AGI by formalizing the human thought process why if we can formalize the human thought process then pretty much everything can be automated from in automated medical treatment to self-driving cars to software certification you know you name it and we should be able to because as humans we're able to do it then obviously if I can formalize that thought process you know I can pretty much automate anything and how do we do it so we actually use something called answer set programming which is logic programming based system and I presume everyone is familiar with prologue or some familiarity with prologue and logic and stuff so I'll introduce answer set programming and then so the main thing that we have done is that we've designed this most of the implementations of answer set programming are based on Sat solver so you ground the program and I'm sure your family with sat solvers as well you ground the program you throw it to a sad solver it gives you models but here we actually designed goal driven or goal directed query driven implementations and that was a challenging task we'll talk about a lot of philosophy I'm going to present as well so humans are sophisticated and effective thinkers we operate with just 12 watts of power and we can perform deductive abductive and inductive reasoning right deductive is you're given P implies q and you're given P you deduce Q abductive is sort of the reverse you're given Q you are given FP then Q or P implies q and you abduce that possibly P holes and inductive reasoning of course is You observe you know pairs of P1 q1 P2 Q2 and you you know induce that P implies Q so it's sort of you have three things right you have the fact you have the implicant implication um and then you have the the consequent so you give two of them and you get the third you get the three forms of reasoning right so so we will you can actually model deductive and abductive reasoning using ASP and scasp in fact I should get my pointer so that everybody can see my pointer and in fact you know we will show that default rules which are part of asset programming are good way of representing inductive generalization so in fact I will show you in between a machine Learning System as well that is explainable that performs as well as XG boost or neural networks or multi-layer perceptrons so the problem that so so the long term goal of or essentially long shot whatever you want to call it major goal of AI is being to essentially simulate human intelligence right we as intelligent as humans and so what are the tools that we have we have used classical Logics and Logics for logic programming prologue whatever for modeling this reasoning unfortunately these Logics we have been stuck with only performing what is called well-founded or inductive reasoning you really need non-inductive reasoning or what's called co-inductive reasoning as well and I'll talk about that or it's essentially assumption-based reasoning and it might involve circular reasoning as well which sounds you know somewhat crazy that you know I'm talking about circular reasoning so as humans we employ both inductive reasoning which is well founded as well as circular assumption based reasoning so co-inductive or circular reasoning is nothing but assumption based reasoning you make some assumption then you draw some conclusions and these conclusions from these conclusions then you may draw your assumption as well but the whole system is consistent it's not grounded in anything you don't know anything as a fact but still consistent and we do that all the time and I'll give you examples we also draw conclusions from failures of proof so classical logic if a proof fails you know it can't do anything but as humans we try to prove a query or we try to answer a question and our proof fails we actually draw some conclusion from that as well again give the example so negation is failure whichever you try to prove something it fails and you assume that so you try to prove p p proof of P fails you assume that not of P holes so that's a key concept for emulating the human thought process so I'll talk a little bit about the scarce which is a gold record implementation of ESP that supports inductive co-inductive and abductive reasoning and that's actually a crucial component although much of the modeling technology is already there within ASP and in fact the answer set programming Community has is the one that has developed all these ways of modeling default rules and multiple worlds and constraints and all kinds of things so if you look at the history of formalizing human thought you know there's all these Boolean Logics and predicate Logics and other types of advanced logics and these Logics have not been able to model the effectiveness of human reasoning and lot of it is you know so so the way we are slotted into only thinking about uh in inductive structures is because of you know problems that were faced hundred years ago you're probably familiar with Russell's paradox so free gay invents predicate logic and then he writes the book and sends it to Russell and Russell immediately starts a problem and that where he can show that if you allow for arbitrary predicates to be defined then you can Define predicates that do not make any sense so you build this set where if R is an element of that set then R must not be arrangement of that set and if R is not an element so you can if you're not familiar read it up but that was one reason why uh why we stick to inductive uh structures uh as itself so Russell said so he was the problem was circularity in the reasoning so he said you cannot have circular reasoning everything should be well founded you you can only have inductive sets which means you start from the simplest of objects for example an empty set then you build larger and larger sets by you construct one element inside two elements at three elements and so on but unfortunately that cannot model Common Sense reasoning so the problem is that these systems of logic cannot reasons about reason about themselves and so turkey's tarsky suggested that we have metallogics and meta metallogic so a lot of that is philosophical um so in Crypt K in 1975 we're probably familiar with case structures showed that a language can have its own truth predicate and still be consistent so basically said you don't need these you can actually have circular statements and make sense out of them so this led to the idea of co-induction and modeling of circular reasoning which we do employ and from there so basically what so our work in conductive logic programming that we showed is a key part of being able to model the human thought process so why do you want to automate Common Sense reasoning so for example you know I also work with uh software uh verification people or sort of software certification people and they say that you know human human reasoning should be done manually for certifying a piece of software so there are good reasons for actually automating because human reasoning because humans can handle only four variables at a time and this actually been proven by researchers in Psychology where so I just put a quote if the number of variables to be considered exceeds human processing capacity then the worker will drop his or mental bundle and become unable to proceed so we basically simplify if it's too complicated we just give up so the problem is that you know we can when we reason we can make statements that are easy to comprehend but you put them together and we have no idea what they mean so here's my favorite example that I actually constructed so suppose you have these four statements Paul will go to Mexico Sally will not go to Mexico Sally will go to Mexico if no evidence Rob will go to Mexico Rob will not go to Mexico so the question is who will go to Mexico and I don't think you can answer that question so first of all what does negation mean here and there are circular statements here Paul will go if Sally will not go and Sally will go if Rob will not go and Rob will go if Paul will not go now you could model them in prepositional logic and actually compute a model right so who will go to Mexico we don't know so formalization automation is important and we will accomplish it via answer set programming so again Common Sense reasoning standard logic programming and logic fails in fact most formalisms have failed and the problem is that classical Logics are monotonic so common sense reasoning requires non-monotonicity which means if we discover new information then we may have to recruit retract our earlier conclusions so logic is monotonic it means that once you prove a theorem it stays there forever I mean Pythagoras Theorem has been there right for discover 2000 whatever years ago proved 2000 and it still is with us because the axioms of euclidean geometry don't change but in our day-to-day life our axioms keep changing and so since axioms change I may have to withdraw my conclusions that I I might have drawn today may not be or something that was not true today may be true tomorrow so so in non-monatonic logics if you discover contradictory information it should not break down things as it does in classical logic as you know in classical Logic the moment you have a contradiction everything can be proven everything and its negation can be proven so the way we operate is that we work with the knowledge we have whatever we know now we will make inferences with that and then if we discover new knowledge we will revise our conclusion right that's how we operate so for example I want to get to my home from here let's say I work here I don't think about all the problems that I might encounter and my way to home it could be things like you know there's an earthquake there is torrential rain maybe Kim Jong-un launched a missile that landed smack in the middle you know my path from here to my home and so on but we don't think about Visa I'll be able to get to my home normally and the classic example is that if we know that Tweety is a bird we conclude it can fly and this conclusion is to be retracted if treaties found to be penguin later right we also draw conclusions from absence of information this is a very critical thing so you can't tell if it's raining outside I see that no one is holding up a number it's a drizzly startup you can't tell but nobody's holding up up an umbrella so you conclude that it must not be raining for all we know those people like to get to it or you want to tell if it's cold outside you look out the window and see if no one is wearing a jacket you conclude but those people might be from you know North Pole or something and for them it's really you know warm so and then we also work with constraints Integrity constraints so we will not pursue reasoning that violates a global violates a constraint that we have in our mind and also we work with invariance we know that certain variants must hold so for example we know that it's impossible to walk and sit at the same time right so moment I tell you that you know person X is walking you know that that person implicitly you know quickly you can draw the conclusion that the person is not sitting or that a human the invariant human must breathe to stay alive so if I tell you somebody's alive then you can automatically conclude that must be breathing and so on so we need to be able to model that as well and then we also use cyclical or assumption based reasoning which allows for multiple words and that's where we get non-inductive semantics so an example is if I ask you can fish talk in real world you know animals can animals talk in real world like humans obviously the answer is no but there is a world cartoon world of children's books where animals do talk so fish can talk in the cartoon world but not in the real world so there are really two possible words the cartoon world and the real world and then we kind of switch context and we figure out are we am I in the cartoon world or am I in the real world and I will perform reasoning over there in that world and these words may have some things consistent so for example Nemo the fish can swim in both worlds the real world Nemo might be the name of your pet fish or Nemo might be the right the fish of the movie cartoon movie it it swims in both worlds but it talks in one world and not in the other right so there are things that are common consistent things that are inconsistent so so we need to be able to simulate this non-inductive reasoning so cyclical reasoning and we'll see how it's cyclical and we need to be able to model number one to one and two and for that we need this negation as failure concept so what is negation as failure so we have classical negation that you're very much familiar with will represent it as minus p so if I write minus sibling John comma Jim it states that John and Jim are not siblings we know for a fact I have a proof I know John's father and mother and I know Jim's father and mother I know they're different therefore they are not I actually have an explicit proof so explicit proof of falsehood of the predicate p is given to me only then I can conclude minus p so so you're probably familiar with the O.J Simpson murder story where he killed his wife might have seen the Netflix movie probably have heard about it so and apologize for the gruesome example but it drives the point home so if I want to prove minus murdered o j comma Nicole it holds true only if there's an X subset proof of his innocence for example he was I know for a fact that he was in Boston airport and you know the body was found in Los Angeles negation is failure in contrast is going to be represented as not p and it really means that I tried I made a good faith effort to prove P I failed therefore not peace true so you see the difference failure to prove versus explicitly knowing that something is false so not sibling John comma Jim I make an attempt about to show that John and Jim are siblings I for example don't know the parents of John and Jim and I might assume that not sibling John kamajim is true so there is no evidence that they are siblings and he assume that you know they are not so we try to prove a proposition if we fail and so we do this all the time we try to prove something we fail we conclude not p so no evidence of P then conclude not p so here we'll say not murder doj comma Nicole we try to prove that he murdered her and we fail which is what happened in the criminal trial and then you know we assume that he did not murder so failure to prove versus explicitly proving falsehood which is classical negation versus negation as failure so negation is failure plays a very important role in modeling incomplete knowledge so if we look at why classical reasoning has failed to model Common Sense reasoning the reason simply is that we basically get stuck if things don't work out in classical logic so if suppose we have axioms A1 through a n and we have a decision procedure based on classical logic that gives us a method for say proving theorems and we want to prove the theorem key and then this is how we'll write it right A1 through a n t is a logical consequence of a and A1 through a and x a 1 through a n we try to prove T and our proof fails we are stuck we really in logic you cannot you cannot do anything you just fail in many circumstances as humans we will say well if the proof failed then it must be false so most common sense reasoning is actually of this form if we fail to prove T now then T must be false but it may become true later but we worry about it then and it's dual if we prove T now then T is true for now but it may become false later because I discovered some contrary information so for example if I model reachability in logic so I say x can reach y if there's an edge from X to y and the transitivity Clause X can reach y if there's an edge from X to Z and Z can reach y I asked the query given this graph can a reach F and you can see that the answer is no but um but prolog proof will get stuck basically you won't be able to prove it so if you want to Define unreachability you need explicit axioms for minus reach when is one node unreachable from the other so you see the problem defining reachability does not define unreachability so it's really failure is it's not that the logic is failing it's just that we how we interpret the rules we could always interpret these rules as as these rules here as if and only if instead of if colon dash usually stands for if in prologue say x reaches y if there's an H from X to y turn that into an if and only if now we can say that if the right hand side doesn't hold conclude that the left hand side doesn't hold so it reach X Y is false and we actually do that all the time so so now what we could do for example is that so we have map of cities and you know some City you can from one city to another perhaps you can drive but from other you know other cities you there's no connectivity no road so you cannot drive then you could write a rule for you know how to go from one rules for how to going how you can go from one city to another but then if you fail you could say well I'm going to take a helicopter so you could actually write um a rule like this take helicopter to go from X to Y if not reachable X comma y so you see you can actually so that's the critical part I can write rules that draw a conclusion based on failure of a proof we do this all the time and that's the most critical thing that being able to draw a conclusion from failure of being able to prove something and so when we arrive so so most of the time we actually complete the rules ourselves so for example if I know that if I have this knowledge that if I drop an object it will break then I automatically complete it I will make it and if and only if I'll say basically conclude the Dual as well that if I don't drug if I don't drop the object it will not break which is true but of course it's in incomplete because the object may break in other ways it may be too brittle so that when you're handling it right it may break so we so we do this all the time we tend to complete the rules or make them if and only if so so again I think already talked about this uh that um that this this actually you know kind of engender circular reasoning but um but Circle reasoning was banned because Russell said so after what happened you know 100 years ago I think 1915 1916 time frame or maybe I think even earlier 1800 more than 100 years ago so the whole mathematics and logic Enterprises are obsessed with having only inductive structures inductive reasoning and that's the Crux of the problem that for 50 years or whatever that AI has been around we've been obsessed with inductive we need circular reasoning or co-inductive reasoning as well which essentially models circular reasoning um so for example I might have rules say that Jack and Jill are are very much in love with each other and we have Jack says I will eat there only Jill you eat dinner and Jill says same thing I will eat dinner only if Jack you eat dinner so question is will they eat or not eat what do you think so I have two rules Jack eats if G leads now if you put this as a query in prologue question mark Jack eats food it will go into an infinite Loop right keep calling so the inductive world will say there is no model is false both Jack eats food and Juliet's food is false but you can see there are two models One World in which both eat in one world in which none eat right so both eat or inductive semantics will say none eat because it's circular say oh I cannot basically say unknown or you know false this is not possible but in but in reality there's another model so now non-inductive semantics also has to deal with incomplete information so I might have rules which say for example John will teach databases if no evidence Mary will teach databases and vice versa variable teach databases if no evidence John will teach databases what is the meaning of these sentences so as a human you might imagine two possibilities in one word John will teach and Mary will not another world Mary will teach and John will not so if you look at the rules they engender circular reasoning right if you try to operationally execute jackets Jack eats food then you will get into an infinite Loop so you can actually find these multiple possible words if you stay in the realm of propositional logic because I could say right Jack eats food if and only if jar needs food or sorry Jill eats food so right so p and only if Q has two models right both p and Q are true or both p and Q are false so that's not a problem but the problem comes when you go to predicate world so propositional logic we allow for multiple worlds right you're given a formula and prepositional logic and you are willing to accept you know 200 000 models for that formula but when it comes to predicate logic we say no no you can only have one model only inductive semantics and I think that's the wrong thing that we have been doing for more than 100 years so so that's what we need to get over and for that you need co-induction and co-inductive semantics and multiple worlds so so even at the predicate level so for example I could write yeah I could actually write with predicate so expertise databases if no evidence y will X and Y are a distinct people and it's a dual but in this case you know since it's a variable the two rules are more or the same I should be able to find multiple worlds from you know this one rule so you see that we so we think both co-inductively and inductively and logic only allows you to model the inductive part so that's the problem and I would say that's one reason why logic has failed to model um Common Sense reasoning so as I said programming consists of rules of the form that you can see here p is the head of the rule if A1 through am holds and no evidence that B1 through b n holds hold and then you have you could assert a fact that P is unconditionally true is a popular formalism for non-monotonic reasoning has been around for a long time you can also read this rule as you're trying to construct an answer set or a model where you say p is in the answer set if A1 through am are not are in the answer set sorry A1 through M are in the answer set and B1 through b n are not if p is a fact it must be in the answer set so your goal is to construct this model or the answer set which subject to these constraints so that's another way that's why it's called answer set programming and you could actually have more general form where you have P if A1 through a m not B one through b n and then you could also have these classically negated predicates where you say minus C1 which means you must have a rule corresponding to minus C1 to prove it and then you could actually negate negate using negation as failure classically negated um predicates or propositions and this actually also has a meaning so these are called normal logic programs and there are applications to answer to non-representation reasoning planning constraint optimization I mean there's very Thirty forty years of research research and you know the semantics is given in a complicated way but we're not going to describe that and there are many implementations as models dlv clasp in fact class wins actually I believe all the SAT solver competition is really super efficient system um so more than 30 years of research so the semantics is based on possible world or what's called stable model semantics you're given a program there might be many worlds many models of this program and you will actually allow for all these these uh these words these models I'll give you examples so the problem is that you're given an answer set program how do you find its model and model is assignment of true false values to propositions or later we'll have predicates to make all the formulas true and these models are called answer sets and actually you can show it captures default reasoning exceptions preferences constraint optimization abductive reasoning all kinds of things in a natural way so again red part is caviar little bit technical so it's a better way to build automated reasoning systems and Export system you can actually you know model at least you know the human thought process with this okay we'll skip the caveats so let's consider a call The College admission process okay so we want to model the College admission process and that will sort of you know give you a good example so College admission process you know this is the United States so it's a little bit different from here no exam so students apply and if they have a high GPA you admit them but even though they have a high GPA there might be some abnormal situations like you know they might have a criminal record so then you want to say well if they are if they have high GPA by default will admit them unless they are ineligible due to some reason like you know they have a criminal record or likewise you know they might have a special skill so U.S universities will admit someone who's an athlete or good opera singer or you know good at fencing or whatever so they have a special talent and they have a fair GPA then also you admit them unless again there is some abnormal situations or exceptions criminal record for example then you also know who not to admit so now certain people are people are ineligible if they are not special I know for a fact they are not special and I know for a fact they do not have a high GPA so the minus high GPA and again there might be some abnormal situations here that even though they're not special and provably do not have a high GPA maybe the president of the University recommended the student and and you still have to admit that student so minus eligible will fail in that case now you could actually fail to prove both eligibility and ineligibility in that case what will you do you will interview them so you see the interesting rule you fail to prove that X is eligible you fail to prove that X is ineligible then you interview them so you see that you have this spectrum of possibilities so if John has a fair GPA does not have a high GPA you can show that John must be interviewed so essentially with the classical negation and negation as failure you can actually model hierarchy of truths which are shown here so P if you write P it means p is definitely true if you write not minus P what you're saying is I have no evidence that P is false which p means that P is possible or P may be true okay go to the bottom if I find minus P it means p is definitely false I must have a proof remember and if I write not P it means I have no evidence of P so P may be false but if I am unable to prove minus P or P then p is unknown so you see that I can so I have these five level hierarchy of modeling sort of the degree of Truth and this is what actually we do so we could say food is good food is bad but we may also say food is not bad not good or unknown quality right and in fact we humans do not use probability in our day-to-day life we use defaults and exceptions so we jump to a default and then we say and then if there are exceptional situations then we will take those into account we do not say Tweety flies with a 90 percent probability right we just say well Tweety flies and then we wait for exceptions so if you look at the ASP systems that are in existence now very sophisticated but they all work by first so you're giving a a program with variables you will bind the variables to all the constraints in the program in all possible ways which is called grounding ground the program turn it into a propositional program then you feed it to a SAT solver and some transformations to find the answer sets so so you can see that there are limitations to these ASP systems because they have to first ground the program turn it and then turn them sort of into data log and then use a set solver but there are many problems again I'm not gonna so you can only write Pro you can only write programs that have a finite grounding right if the grounding is infinite which you will have if you case if you have for example lists or terms also get exponential blow up so for example I have this simple Clause P of X comma a if Q of y b c where X and Y variables a b c are constants then if I ground it it will turn into nine clauses now imagine a knowledge base with you know 50 000 Clauses and ten thousand constants and 20 000 variables this is unsustainable process so what you need is a query driven implementation just like prologue you can write pose a query and that's what we did we designed but it's a non-trivial process because you need things like constructive negation and all sorts of advances so I'm going to skip you know give not give you other problems so the solution is to build these goal directed execution systems where you're given a predicate answer set program and you pose a query and you're able to get an answer which is how we work we have a goal we have the rules and we're able to reason sort of backwards so so only part of the knowledge base that is only relevant to the queries explored in the grounding based systems you compute the entire model which is completely useless that's not what we do right we don't compute the entire model all possible you know conclusions you could draw given a set of rules we only work our way backwards and sort of prove the query that we have in our mind so that's what you need um so we actually you know so co-inductive logic programming is what allowed us to um essentially build these predicate answer set programming system so we have actually the scas system that we've designed and many many people actually use it now for things like uh treatment Automation and in fact it's available as part of swi prologue um they've Incorporated it if you go there you can and you use their switch interface then there is a tab for writings cast programs as well but you can actually write these ASP programs with negation as failure and classical negation and execute them it will also give you justification for the query and you can perform abductive reasoning and all sides all sorts of neat things so so the key concept for realizing this execution Gold Records execution of ASP is the concept of co-induction which is the Dual of induction and again you may not be familiar with all this programming language terminology greatest fixed points and least fixed points so when you do inductive reasoning you're basically operating with the least fixed Point semantics for co-induction you need the greatest fixed Point semantics so the idea here is that you detect cycles and if you see a cycle you know that if you assume so for example in the process of proving P if P appears again then P succeeds and what we're really saying is if I assume P then P holds so for example if I have this these two rules that you have seen before each put Jack if he's put it and eat food chill if it's who Jack and right there are two possibilities both Jack and Jilly and neither one needs so both both heat is in the greatest fixed Point 98 is in the least fixed point so if I query does will Jack eat food we reduce it to eat food Jill and that reduces by the second rule to eat food Jack now we see that we are that a goal that basically you see something appeared that's also present in the ancest as one of the ancestors in one of the ancestor nodes at this point you say oh I'm in a cycle this is part of the greatest fixed point you stop and then you say everything that is in my in the path that in my proof tree actually holds so you find this co-inductive hypothesis set which is the model that both Jack and Jill will eat what about the other model I can ask its negation will Jack not eat reduce it to not eat food gel to reduce it to not eat food Jack and again you have a cycle and you'll stop and now you have a model in which both Jack doesn't eat and Jill doesn't need so you can see it's very simple but then it should introduce variables it becomes complicated so that's the idea that I can execute inductively so this is so this part is inductive proof that none eat and the previous one was the co-inductive one so so we there's something called cosl dnf again I'm going to spare you the details I've already described them um but you can also have okay so so human thought process can be largely modeled with default rules with exception and preferences and I think I mentioned default tools a little bit to manage incomplete information multiple possible worlds which needs cyclical reasoning and Global constraints so examples already seen right I can write X flies if x is a bird unless it's an abnormal bird and penguins are abnormal Birds so if I have twities about Sam is a bird and I ask does Tweety fly does Sam fly they will both succeed because I do not know anything about Tweety and Sam being a penguin so Tweety and Sam must be able to fly I conclude that not abnormal bird is false not abnormal bird is true birth treaty is true therefore flies tweet is true now suppose we add the fact that Tweety is a penguin and now you can no longer conclude that Tweaky flies because the not abnormal Bird Tweety will succeed will fail abnormal birth Tweety succeeds because Tweety is a penguin so not abnormal but Tweety will fail and therefore flies treaty will fail but Sam can still fly so this is default reasoning with exception so default reasoning is that normally birds fly Treatise a bird it can fly unless exception it's a penguin and then you have cyclical reasoning which is these databases John if not teach database is married teach database married if not and here you have two models One World in which Mary teaches John does not otherwise John teaches and Mary does not and then you can also have constraints which says marry teaching databases is always false so it will kill the world in which Mary teaches databases so if I put these three rules together I will get only one answer which is that John teaches and Maddie does not right so constraints actually kill worlds okay all right so let's now see how we can model various types of reasoning that we do so in example is aggressive and conservative default reasoning so here for example you go to your doctor and doctor prescribe your medicine but this medicine may have side effects so what are you going to do what or what is your doctor going to do the doctor May say well you know just go ahead and take this medicine I think very few people have side effects we're gonna assume that you're not gonna have a side effect but who knows that medicine might right kill someone so you're you're performing you're doing default reasoning but you're aggressive in making your decisions your conclusions jumping to conclusions saying even though this medicine may have side effects I recommend you take it but on the other side I could be conservative I could say doctor could say well I am not you know there might be side effects so let's perform some tests so what are we trying to do we're trying to prove that this medicine will not cause any harm to you only after I have proved that it does not cause any harm I will recommend that you take it so now my con reasoning is conservative so aggressive reasoning again coming back to our bird example you'll write X flies if x is the bird not an abnormal bird penguins are abnormal births treaties are penguin tweet is a bird but Sam is a bird and now if I ask does Tweety fly it will say no the Sam fly it aggressively reasons and says yes without thinking about trying to prove that Sam may be a penguin it says let's jump jump to this aggressive conclusion but then if I want to model conservative reasoning where I say well I don't know anything about Sam Sam could possibly be a penguin let's try to prove that it's not a penguin first only if I fail to prove that Sam is not a penguin I will say that Sam cannot fly so you'll model it in this way like you can see here x flies if x is a bird not an abnormal bird but now it's an abnormal bird only if I fail to prove that it's not a penguin and now if twities are penguin Tweety's a bird Sam is a bird then for both Tweety and Sam it will say no because now we're being conservative in saying that so first we'll try to prove that Sam is not a penguin since I have no information about Sam being a penguin or not being a penguin it fails and we conclude that Sam since I am conservative Sam cannot fly you can also have strong exceptions where you might actually say explicit you have explicit reason to conclude that minus flies hold that X never flies effects of the North Street it never flies you can also have nested exceptions so I might say animals normally don't fly right you see here minus flies X if Animal X and not and but abnormal animals which are birds do fly but there are abnormal Birds penguins that do not fly and possibly there could be suppose we discover a subset of penguins called Super Penguins that can fly then there's an exception to Penguins as well so you can model this and in fact most of our knowledge is default conclusion um exception exception to exception exception dude and in fact you can actually Channel this into uh to um what we're really doing is we are doing inductive generalization from observations and you can actually Channel this into building um explainable AI systems machine Learning Systems which we have done so we observe that many birds fly so here are samples of individual birds and these birds fly so I write the rule I sort of look at bird one flies but two flies but three flies and so on so I write the rule X flies if x is a bird but then I discovered that there are birds that are penguins that do not fly so I have my first decision boundary so I have birds that do not fly on the right and birds that fly so then I extend I say well birds fly but there are exceptions namely penguins but then I suppose hypothetically there is there are super penguins that can fly so but super I then observe oh there are exceptions to exceptions and so what you're really doing is moving right samples or maybe adding samples and sort of trying trying to revise the decision boundary as you go along so you say well there's a super penguin Green Dot that can fly so I have to move it from the right hand side to the left hand side so I sort of change my decision boundary right very much like a machine Learning System neural network whatever and and now you will write X plus if x is a bird unless it's an abnormal bird penguins are abnormal Birds but there might be abnormal penguins that are super penguins so as I said this can be basis for machine learning and which you actually have done so we have this family of algorithms actually explainable algorithms called first order learner of default Theory so it's a little bit of a digression so um so the these algorithms actually will learn given a tabular data they will learn default rules and they they perform as well as as I said XG boost and so you can actually download them so so it learns rules very much in like in inductive logic programming right so you can use Information Gain heuristics or you can base it on shap shapley values or lime but we actually have better heuristics that are based on Genie impurity and in fact it produces what we an algorithm called fold SC where SC stands for scalable explainability which means no matter your data set size it'll explain it in very small number of rules so I'll just give you examples if you take for example the famous adult data set so okay so what we're doing is given data which is described in a tabular form we're learning default rules so we learn so we first try to cover the default conclusion then we try to okay things that were not covered see if there's a pattern there learn that as an exception then those things that did not get covered as an exception see if we can learn exception to exception exception to exception to exception and keep going and surprisingly it actually works very well so not only it competes with XG boost and MLPs it's also explainable so we can actually explain the adult data set in just two rules with an accuracy of 0.84 which is comparable to and then made in Australia these are all from UCI or our kaggle um also in two groups you can see 145 000 rows 32 000 rows 24 features 15 features and so here is the comparison table where it Compares full testing which is so so the predecessors of forwardnessy are available freely online I mean on GitHub on my okay feel free to try it but they will produce more rules for let's see you know we got green using a file a patent of that um it only produces very small number of rooms because of the heuristics it uses um so you can see that sometimes um XG boost will win the accuracy it's in pink whoever wins sometimes MLPs will win and sometimes the B will win but they're all pretty close but the interesting thing is that so the other interesting thing about this algorithm is that it does not need one hot encoding or any data preparation label the features you know and just push it to the algorithm and it will actually learn the rules so the execution time is yeah the hypothesis spaces yes yeah it's the same but so decision trees it I mean it performs better than decision trees as well an interest interesting thing is that we thought this Genie impurity uh heuristic will help decision trees perform better as well but it does not the number of I mean the size of the tree is huge whereas here you can actually explain things in two rules and six predicates whereas decision tree might take you know three 100 I mean hundred Branch tree and you know 600 predicates things like that so but the interesting thing is the time you see that it's very efficient so we look at the average 77 seconds on average for XG boost 42 for MLPs and 1.3 seconds for four deci so you can see the orders of magnitude faster because so again why is it this way because of using this idea of default rules the default rules actually represent knowledge very well and you could say that that's what nature discovered and that's why we think in terms of default rules and not in terms of conjunctive normal formulas of the decision tree right because we always think let's work with what we have as we encounter you know and then we say well we'll cross that bridge when we get there will change our rule at an exception as we get there so you can I'm sure you've seen this picture right if you're in machine learning so you can see that fold will sit there so this year decision trees sit somewhere here deep learn this is explainability versus accuracy but you know forward family but again you know this is a sort of a digression where I'm trying to show that if you try to emulate the human thought process okay so I'm coming towards the end of my talk now so I'll just give you example because this talk is about automating common sense reasoning so we have this you know pieces of information and I want to draw some common sense conclusion so can I automate that so we said George is a bachelor George was born in Boston and collects stamps son of someone is a child who is male George is the only son of Mary and Fred a man is an adult male person a bachelor is a man who has never been married traditional marriage is a contract between a man and a woman enacted by a wedding and dissolved by divorce while the contract is in effect the man is called the husband the woman called the wife are said to be married and wedding is a ceremony where you have bridegroom bouquet and I want to conclude that George has never been the groom at a wedding now if you read these statements can you prove it well you see that George is a bachelor and a bachelor is a man who has never been married and what is a marriage is a contract between um yeah it marries the contract husband and woman to be married and somehow wedding has to be there yeah tricks number seven tradition marries the contract between naked by a wedding and a wedding has a bride and a groom so you see that it's kind of kind of long-winded if you want to prove that George has never been groomed at a wedding right so so can we automatically infer this truly commonsensical yes yeah Mary has an unmarried son born in Boston so how would we prove that we say well George is a bachelor George was born in Boston George is the only son of Mary and Fred and George is a bachelor who is unmarried so you can say the answer is yes and then then I asked so this is actually from Hector Le West's logic programming book where he poses this but remember that there are no answers to these questions I mean how do you automate automatically answer these questions no one is the wife of any of Fred's children so Fred has a single child George and George is unmarried therefore doesn't have a wife and no woman is the wife of so the answer to all these so how would we model this so we can actually model it straightforward manner in answer set programming and run it on our scav system George is a bachelor birth city George you know like predicates hobby Jarred stem collecting Sun exit son of wife access child of YX is male um and then the important part is the constraints that show that he's George is the only son so what is the concept of an only son if x is son of Fred there's another son that Fred has that then another son not equal x must be false so this is a constraint that declares what is false and likewise for Mary so with this you are saying that George is the only son and the rest of it is actually quite straightforward but notice the introduction of time that you need because marriage and wedding and divorce are time sensitive events somebody could be married divorced married divorce marry divorced at infinite term right how we model that so X is a bachelor if x is a man and X never married somebody called Y at any time t so you see the challenge now negation standing in front of an existentially Quantified variables we'll get you have to sort that show that for every five y for every time t X George did not marry them so you see the challenge of the proof right that you have to but you can do all this in scasp I mean our system so that's the the power that it brings is just enormous so here is X married Y at time T if x is a groom wiser bride The Divided a Time T1 and time T is greater than T1 and they did not they were not divorce at the instant t and then you have to Define divorced X's husband y's wife it is all and then you have to write a constraint that wedding always precedes a divorce so so you see that it's non-trivial to represent