Automating Commonsense Reasoning with ASP and s(CASP)

Notes

While machine learning technologies have had tremendous successes, they alone are not enough. Intelligent behavior includes both learning and (commonsense) reasoning, and automating commonsense reasoning is equally important.

NOTER_PAGE: (1 . 0.49288389513108616)

Automation of commonsense reasoning requires formalizing the human thought process

NOTER_PAGE: (1 . 0.5632958801498128)

The quest to formalize the human thought process led to the founding of the field of Logic.

NOTER_PAGE: (1 . 0.5730337078651686)

which has proven to be hard

NOTER_PAGE: (1 . 0.5775280898876405)

it is hard to use these logics to faithfully model the human thought process in an elegant manner

NOTER_PAGE: (1 . 0.6591760299625469)

Meta-reasoning within the logic was disallowed due to fears of unsoundness and circularity. Thus, classical logics do not have the ability to derive a conclusion based on failure of a proof in that logic itself.

NOTER_PAGE: (2 . 0.2696629213483146)

In the late 1970s and 1980s considerable effort started to being invested in adding negation to logic programming. The concept of negation as failure [12, 13] was added to logic programming along with notion of stable model semantics

NOTER_PAGE: (2 . 0.4157303370786517)

Negation-as-failure is frequently employed by us humans. It allows us to take an action if proof of a goal fails.

NOTER_PAGE: (2 . 0.4614232209737828)

Being able to work with incomplete knowledge, arguably, is the essence of commonsense reasoning.

NOTER_PAGE: (2 . 0.5280898876404495)

humans employ non-monotonic reasoning.

NOTER_PAGE: (2 . 0.5932584269662922)

Progress was still limited by the type of implementations available for ASP that only admitted propositional logic programs.

NOTER_PAGE: (2 . 0.7692883895131086)

How humans actually think is the realm of cognitive psychology. We believe that any specific way in which a human may (rationally) think can be elegantly simulated with (goal-directed) ASP.

NOTER_PAGE: (3 . 0.4307116104868914)

main characteristics of human commonsense reasoning

NOTER_PAGE: (3 . 0.5340823970037454)

(i) perform non-monotonic reasoning

NOTER_PAGE: (3 . 0.549063670411985)

(ii) perform assumption-based or circular reasoning

NOTER_PAGE: (3 . 0.5827715355805244)

(iii) reason with constraints

NOTER_PAGE: (3 . 0.597752808988764)

giving this rule an operational semantics to perform computation becomes complicated.

NOTER_PAGE: (5 . 0.20823970037453185)

Coinduction and coinductive logic programming, based on greatest fixpoint semantics, can be used to give operational semantics to such circular rules containing predicates

NOTER_PAGE: (5 . 0.22172284644194756)

Constraints can be generally stated as declaring that the conjunction of a set of propositions or predicates is false

NOTER_PAGE: (5 . 0.3797752808988764)

each rule is quite easy to understand by itself, however, it is hard to understand what these rules mean when put together,

NOTER_PAGE: (5 . 0.6576779026217229)

We generally ignore the models where the antecedent bird(tweety) is false.

NOTER_PAGE: (6 . 0.15655430711610488)

Wason’s selection task [19] indeed shows that humans interpret an if as an if and only if

NOTER_PAGE: (6 . 0.25842696629213485)

Wason’s selection task also demonstrates that we are only interested in supported models, as the models arising out of false ⇔ false are ignored by the subjects.

NOTER_PAGE: (6 . 0.5647940074906367)

The goal in ASP is to compute an answer set given an answer set program, i.e., compute the set that contains all propositions that if set to true will serve as a model of the program

NOTER_PAGE: (7 . 0.4426966292134832)

The two types of negation allow us to realize various “shades" of truth, namely, definitely true, maybe true, unknown, maybe false, and definitely false.

NOTER_PAGE: (7 . 0.6734082397003746)

assumes that the programs are completed with the caveat that cyclical programs that do not involve negation will be assigned only a single model in which the propositions involved in the cycle are assigned false.

NOTER_PAGE: (7 . 0.7063670411985019)

Humans use default reasoning [22, 15] to jump to conclusions. These conclusions may be revised later in light of new knowledge.

NOTER_PAGE: (8 . 0.2359550561797753)

expert knowledge is nothing but a set of default rules about a specialized topic

NOTER_PAGE: (8 . 0.41273408239700377)

Humans do not use probabilities in their day to day life.

NOTER_PAGE: (9 . 0.5438202247191012)

Humans can represent multiple possible worlds in parallel in their minds and reason over each.

NOTER_PAGE: (10 . 0.19850187265917604)

Abduction: Given the observation q and the premise p ⇒ q, we abduce p.

NOTER_PAGE: (12 . 0.26666666666666666)

Generally, the set of abduced literals is fixed in advance.

NOTER_PAGE: (12 . 0.3243445692883895)

it is a challenging task to implement ASP

NOTER_PAGE: (13 . 0.1550561797752809)

The s(CASP) system can be thought of as Prolog extended with negation-as-failure based on the stable model semantics.

NOTER_PAGE: (14 . 0.1348314606741573)

if we ask a query in s(CASP), it will give a partial answer set that is a subset of the world in which the query is true.

NOTER_PAGE: (14 . 0.4209737827715356)

In the s(CASP) system, a variable can only be disequality-constrained against ground terms

NOTER_PAGE: (14 . 0.751310861423221)

while realizing constructive negation is challenging, it’s an essential element

NOTER_PAGE: (15 . 0.12808988764044946)

Essentially, the dual rule states that a non-red car is anything other than mycar as well as anything that is not red, and among red things those that are not cars.

NOTER_PAGE: (15 . 0.601498127340824)

for the goal not p(a) to succeed, we must prove that q(a, Y) holds for every possible value of Y.

NOTER_PAGE: (16 . 0.10936329588014981)

The execution of the forall, however, is non-trivial, as often times the foralls are nested.

NOTER_PAGE: (16 . 0.15805243445692885)

Constraints in ASP can be expressed directly

NOTER_PAGE: (16 . 0.21423220973782772)

justification for each element of an answer set can be generated

NOTER_PAGE: (16 . 0.702621722846442)

search may be non-terminating or may take too long

NOTER_PAGE: (17 . 0.11310861423220975)

9. Applications

NOTER_PAGE: (19 . 0.23146067415730337)

none of the existing proposals are able to represent the ambiguity and/or administrative discretion present in contracts and/or applicable legislation

NOTER_PAGE: (20 . 0.14382022471910114)

requirements specifications for cyber physical systems can be directly represented in s(CASP). As a result, they are executable, and their safety and liveness properties can be studied

NOTER_PAGE: (20 . 0.42322097378277157)

use machine learning for translating an image into a set of predicates that capture the objects in the image, their characteristics, and their spatial relationships. Commonsense knowledge about the domain that the image is about can be coded in ASP.

NOTER_PAGE: (20 . 0.5558052434456929)

s(CASP) allows for approaches to AI that use both learning and reasoning, very similar to how humans operate.

NOTER_PAGE: (20 . 0.6898876404494382)

For a commonsense reasoning system to be successful, it has to be modeled in a very simple way and very simple inference processes must be used. Otherwise, it will be hard to determine which decision procedure to apply.

NOTER_PAGE: (22 . 0.6734082397003746)

simplicity of inference procedures is extremely important.

NOTER_PAGE: (22 . 0.7722846441947566)