Brave Induction Revisited

Abstract

Sakama and Inoue introduced brave induction as a novel logic framework for concept-learning. They showed that brave induction has potential applications for problem solving in many domains. In this paper, motivated from Shapiro's de nition of model inference problems, we provide an optimization of brave induction called proper brave induction, which prefers hypotheses resulting fewer minimal models. We rst propose formal de nitions of proper brave induction for clausal theories and nonmonotonic logic programs, then investigate corresponding properties and develop an optimization procedure. At last, we analyze computational complexity of decision problems for proper brave induction in propositional case.

Keywords

• Proper brave induction
• Brave induction
• Inductive logic programming
• Nonmonotonic logic programming

-

Introduction The problem of concept-learning [ 8 ] is to construct a general description of a class of objects given a set of examples and non-examples using background knowledge. There are many di erent logical frameworks for concept-learning, including explanatory induction [ 5 ] or learning from entailment [ 3 ] which is considered as a normal setting in inductive logic programming (ILP) [ 9 ], learning from satisability (LFS) [ 3 ], and learning from interpretations (LFI) [ 3 ]. Besides, Sakama and Inoue [ 14 ] introduced a novel logic framework for concept-learning called brave induction, which allows more hypotheses than explanatory induction and fewer hypotheses than LFS. They showed that brave induction has potential applications for problem solving in systems biology, requirement engineering, and multiagent negotiation.

Example 1. There are 1 teacher and 30 students in a class, of which 20 are European, 7 are Asian, and 3 are American. The situation is represented by background knowledge B and the observation O:

O : euro(1); : : : ; euro(20); asia(21); : : : ; asia(27); usa(28); : : : ; usa(30); where each number represents a teacher or an individual student. Here are some hypotheses:

H1 : euro(X) _ asia(X) _ usa(X)

student(X);

H2 : euro(X) _ asia(X) _ usa(X) _ teacher(X);

H3 : euro(X) _ asia(X) _ usa(X) _ teacher(X)

student(X): All of them are allowed by brave induction, while H1 appears a good hypothesis.

Shapiro [ 15 ] discussed logical foundations of inductive learning and de ned model inference problems. The intuition behind the de nition is that, the \world" is governed by some model M of the language and the inductive learning process is to gather information and correct hypotheses in order to converge to theories that could capture the model M .

If a hypothesis captures more models, then it has more \uncertainties" to capture the \world" model. Motivated from the above intuition, we would prefer hypotheses allowed by brave induction with fewer \uncertainties" to capture the \world" model. In speci c, we introduce an optimization of brave induction called proper brave induction, which allows a hypothesis that is allowed by brave induction and there does not exist another such hypothesis whose set of minimal models or answer sets is a proper subset of its. In Example 1, H1 is allowed by proper brave induction while H2 and H3 are not. In the paper, we provide formal de nitions of proper brave induction for clausal theories and nonmonotonic logic programs, then investigate corresponding properties and develop an optimization procedure. At last, we analyze computational complexity of decision problems for proper brave induction in propositional case. 2

Preliminaries In this paper, we assume a function-free rst-order language L with nite sets of constant symbols and predicate symbols, and a countable set of variables. A term is either a variable or a constant. A ground term is a constant. An atom is an expression p(t1; : : : ; tn), where p is a predicate symbol with arity n 1 and t1; : : : ; tn are terms. A literal is an atom or the negation of an atom. A formula is a propositional combination of atoms. A ground atom (resp. ground formula) is an atom (resp. formula) that contains no variables.

The Herbrand universe of L is the set of constants and the Herbrand base of L

is the set of ground atoms. A ground instance of an expression (atom, formula, etc.) is obtained by uniformly instantiating the variables in it with ground terms in the Herbrand universe.

An interpretation I is de ned as a subset of the Herbrand base of L. I satis es

a ground formula F , if I entails F in the sense of classical logic. Moreover, I satis es a (non-ground) formula F , written I j= F , if I satis es every ground instance of F . I satis es a set T of formulas, written I j= T , if I satis es every formula in T . Given sets T1 and T2 of formulas, T1 entails T2, written T1 j= T2, if every interpretation I satis es T1 implies I satis es T2.

In the following, we recall the basic notions about clausal theories with the minimal model semantics, answer set programming [ 1 ], and brave induction [ 14 ]. 2.1

Clausal Theories and the Minimal Model Semantics A clausal theory is a nite set of clauses of the form: where n m 0 and A1; : : : ; An are atoms. If m 1, it is a Horn clause; if m = n, it is a positive clause; if A1; : : : ; An are ground atoms, it is a ground clause. A Horn clausal theory is a nite set of Horn clauses and a ground clausal theory is a nite set of ground clauses.

An interpretation I satis es a ground clause of form (1) if fAm+1; : : : ; Ang

I implies fA1; : : : ; Amg \ I 6= ;. A clause with variables is considered as a shorthand for the set of its ground instantiations. In speci c, an interpretation I satis es a (non-ground) clause if I satis es every ground instance of it. An interpretation I is a model of a clausal theory T if I satis es every clause in T . A model I of a clausal theory T is minimal if there does not exist another model I0 of T such that I0 is a proper subset of I. We use MM (T ) to denote the set of minimal models of a clausal theory T . A clausal theory T is consistent if MM (T ) 6= ;; otherwise, T is inconsistent. Answer set programming (ASP) is one of the most popular rule-based nonmonotonic formalisms [ 1 ]. An ASP program (or simply a program, DLP) is a nite set of (disjunctive) rules of the form: where n m k 0, n 1 and A1; : : : ; An are atoms. If k 1, it is a normal rule; if m = n, it is a positive rule. A normal logic program (NLP) is a nite set of normal rules and a positive program is a nite set of positive rules.

We will also write rule r of form (2) as head(r) body(r); where head(r) is A1 _ _ Ak, body(r) = body+(r) ^ body (r), body+(r) is

Ak+1 ^ ^ Am, and body (r) is :Am+1 ^ ^ :An. With a slight abuse of

notion, we identify head(r), body+(r), body (r) with their corresponding sets of atoms. We can omit if body(r) is empty.

An interpretation S satis es a ground rule r if body+(r) S and body (r) \

S = ; implies head(r) \ S 6= ;. Similar to clausal theories, a program with variables is considered as a shorthand for the set of its ground instantiations. In speci c, an interpretation S satis es a (non-ground) rule if S satis es every ground instance of it. An interpretation S is a model a program P if S satis es every rule in P , in this case, P is satis able. A model S of a program P is minimal if there does not exist another model S0 of P such that S0 S. We also use MM (P ) to denote the set of minimal models of a program P .

Given an ASP program P and an interpretation S, the Gelfond-Lifschitz reduct of P on S, written P S , is obtained from P by deleting: { each rule that has a formula not p in its body with p 2 S, { all formulas of the form not p in the bodies of the remaining rules. Then P S is a positive program. An interpretation S is an answer set of P if

S 2 MM (P S ). In the following, we use AS(P ) to denote the set of answer sets

of a program P . P is consistent if there exists an answer set of P ; otherwise, P is inconsistent. P AS-entails a formula F (resp. a set T of formulas), written P j=AS F (resp. P j=AS T ), if for every S 2 AS(P ), S j= F (resp. S j= T ).

Notice that, given a clausal theory T , a positive program P can be obtained from T by replacing each clause of form (1) with the positive rule of the form: and MM (T ) = AS(P ). In the following, we identify a clausal theory T with the corresponding positive program P and a minimal model of T with the corresponding answer set of P . A typical induction task is to construct hypotheses to explain an observation using background knowledge. In speci c, one is given a triple hLb; Lo; Lhi, where Lb is the language of background knowledge, Lo is the language of observations, and Lh is the language of hypotheses. Here we identify a language with the set of sentences allowed in the language and require that Lb; Lo; Lh are subsets of sentences of L. Given an observation O in Lo and background knowledge B in Lb, a formalization of concept-learning is to de ne a cover-relation from O and B to a hypothesis H in Lh.

Sakama and Inoue [ 14 ] proposed a framework of concept-learning called brave induction based on the triple hLCT ; LCT ; LCT i, where LCT denotes the set of clausal theories in L, and extended the notion to the triple hLASP ; LGA; LASP i1, where LASP denotes the set of ASP programs and LGA denotes the set of ground atoms in L. Di erent from existing frameworks, brave induction allows more hypotheses than explanatory induction and fewer hypotheses than LFS. It has been shown that brave induction has potential applications for problem solving in many domains. We recall the basic notions of brave induction here. De nition 1 (Brave induction). Let B be background knowledge and O an observation. A hypothesis H covers O under B in brave induction if 1 In [ 14 ], classical negation is allowed in ASP programs and the language of observations is the set of ground literals. However, from [ 1 ], an ASP program with classical negation can be equivalently translated to one without classical negation. Without loss of generality, we only consider ASP programs without classical negation here. { B [ H has a minimal model satisfying O, given the triple hLCT ; LCT ; LCT i; { B[H has an answer set S such that O S, given the triple hLASP ; LGA; LASP i. In this case, H is called a solution of brave induction.

Besides brave induction, there are other frameworks for concept-learning, including explanatory induction [ 5 ], LFS [ 3 ], and cautious induction [ 14 ]. De nition 2. Let B be background knowledge and O an observation. { A hypothesis H covers O under B in explanatory induction if

B [ H is consistent and B [ H j= O, given the triple hLCT ; LCT ; LCT i. { A hypothesis H covers O under B in LFS if

B [ H has a model satisfying O, given the triple hLCT ; LCT ; LCT i.

{ A hypothesis H covers O under B in cautious induction if

B [ H is consistent and every minimal model of B [ H satis es O, given the triple hLCT ; LCT ; LCT i;

B [ H is consistent and O S for every answer set S of B [ H, given the triple hLASP ; LGA; LASP i.

H is called a solution of explanatory induction, LFS, or cautious induction.

Following propositions summarize the relations between these frameworks. Proposition 1 (Proposition 2.1 and 6.1 in [ 14 ]). Given the triple hLCT ; LCT ; LCT i, let B be background knowledge and O an observation.

{ If H is a solution of explanatory induction, then H is a solution of cautious induction. The converse implication holds when O is a set of positive clauses. { If H is a solution of cautious induction, then H is a solution of brave induction. The converse implication holds when B [ H is a Horn clausal theory. { If H is a solution of brave induction, then H is a solution of LFS. Proposition 2 (Proposition 3.4 in [ 14 ]). Given the triple hLASP ; LGA; LASP i, let B be background knowledge and O an observation.

{ If H is a solution of cautious induction, then H is a solution of brave induction. The converse implication holds when B [ H is a positive NLP.

[ 14 ] provided computational complexity results of brave induction.

Proposition 3 (Theorem 4.1 and 4.3 in [ 14 ]). Let B be background knowledge and O an observation, the following complexity results hold: { Deciding whether O has a solution of brave or cautious induction under B is NP-complete, given the triple hLCT ; LCT ; LCT i or hLASP ; LGA; LASP i. { Deciding whether a given hypothesis is a solution of brave induction is 2P complete, given the triple hLCT ; LCT ; LCT i or hLASP ; LGA; LASP i. { Deciding whether a given hypothesis is a solution of cautious induction is coNP-complete, given the triple hLCT ; LCT ; LCT i. { Deciding whether a given hypothesis is a solution of cautious induction is 2P -complete, given the triple hLASP ; LGA; LASP i.

Motivations An inductive learning problem often assumes that the \world" is governed by some model M of the language and the learning process is to gather information and correct hypotheses in order to converge to theories that could capture the model M . In this section, we address the problem of brave induction from the perspective of the assumption, which motivates our optimization of brave induction proposed in the next section.

Following Shapiro's [ 15 ] de nition of model inference problems, we de ne problems of explanatory induction, LFS, brave induction, and cautious induction. Given a triple hLb; Lo; Lhi and an interpretation M as the model of the \world", we use LoM to denote the set of observational sentences satis ed by M .

De nition 3. Given a triple hLb; Lo; Lhi, an interpretation M of L, and back

ground knowledge B Lb satis ed by M , { the explanatory induction problem is to nd a hypothesis T Lh such that

M satis es T and T [ B j= LoM ; { the LFS problem is to nd a hypothesis T Lh such that M satis es T and there exists a model S of T [ B with S j= LoM ; { the brave induction problem is to nd a hypothesis T Lh such that M satis es T and there exists an answer set S of T [ B with S j= LoM ; { the cautious induction problem is to nd a hypothesis T Lh such that M satis es T , T [ B is consistent, and T [ B j=AS LoM .

In this case, T is respectively called an observation complete axiomatization of the explanatory induction, LFS, brave induction, or cautious induction problem.

Notice that, if the set of all ground literals in L, denoted by LGL, is a subset

of Lo, then the condition \M satis es T " has been implied and can be omitted in the de nition.

We can extend the de nition of brave and cautious induction given the triple hLASP ; LGL; LASP i.

De nition 4. Given the triple hLASP ; LGL; LASP i, let B be background knowl

edge and O an observation.

{ A hypothesis H covers O under B in brave induction if B [ H has an answer set satisfying O. { A hypothesis H covers O under B in cautious induction if B [H is consistent and every answer set of B [ H satis es O.

Recall that, the language L is function-free and contains nite sets of con

stants and predicates, then both LGL and interpretations are nite. Proposition 4. Let M be an interpretation of L, background knowledge B satis ed by M , and an observation O = fl j l 2 LGL \ Lo and M j= lg where Lo is the language of observation.

{ Given the triple hLCT ; LCT ; LCT i, a hypothesis H is an observation complete axiomatization of the explanatory induction, LFS, brave induction, or cautious induction problem if and only if H is a solution of explanatory induction, LFS, brave induction, or cautious induction respectively. { Given the triple hLASP ; LGA; LASP i, a hypothesis H is an observation complete axiomatization of the brave induction or cautious induction problem implies H is a solution of brave or cautious induction respectively, but not vice versa in general. { Given the triple hLASP ; LGL; LASP i, a hypothesis H is an observation complete axiomatization of the brave induction or cautious induction problem if and only if H is a solution of brave or cautious induction respectively. Example 2. Consider Example 1, the \world" model M implies that the sets of

European, Asian, and American are pairwise disjoint. Given the triple hLASP ; LGA; LASP i

and the observation O [ B, the hypothesis feuro(X); asia(X); usa(X)g is a solution of brave and cautious induction, but it is not an observation complete axiomatization of the brave or cautious induction problem.

If LGL Lo and LGL Lh, then the set fl j l 2 LGL and M j= lg is an observation complete axiomatization of explanatory induction, LFS, brave induction, and cautious induction problems. However, the set is not a good solution for many concept-learning problems. Normally, Lh has a set of restrictions, i.e., language bias [ 9 ], which speci es the space of acceptable hypotheses. For example, some set of constants may not be allowed to appear in Lh. To simplify the discussion, we consider the set of clausal theories with no appearance of any constants, denoted by LCT V , and the set of ASP programs without any constants, denoted by LASP V , as examples of restricted language of hypotheses.

Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, solutions of ex

planatory induction, LFS, brave induction, and cautious induction are de ned the same for the triple hLCT ; LCT ; LCT i or hLASP ; LGL; LASP i respectively.

Example 3. Consider Example 1, given the triple hLCT ; LCT ; LCT V i, we could

not nd out a hypothesis that covers O under B in explanatory induction and cautious induction. On the other hand, hypotheses H1, H2, H3, and

H4 : euro(X) _ student(X); H5 : :asia(X) _ :usa(X)

are solutions of LFS. H1, H2, and H3 are solutions of brave induction.

Although the hypothesis space of brave induction is smaller than the space of LFS, candidate solutions of brave induction also need to be optimized. For instance, we would prefer H1 to H2 and H3, as AS(B [ H1) AS(B [ H2) and

AS(B [ H1) AS(B [ H3). The intuition is that, a solution of brave induc

tion is intended to capture the \world" model with background knowledge, and solutions with fewer \uncertainties" are preferred. Following the intuition, we specify our optimization of brave induction in the next section.

Proper Brave Induction Motivated from previous discussions, we introduce two frameworks of induction. De nition 5 (Proper brave and cautious induction). Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, let B be background knowledge and O an observation.

{ A hypothesis H covers O under B in proper brave induction if H covers O under B in brave induction, and there does not exist another such hypothesis H0 such that AS(H0 [ B) AS(H [ B). { A hypothesis H covers O under B in proper cautious induction if H covers O under B in cautious induction, and there does not exist another such hypothesis H0 such that AS(H0 [ B) AS(H [ B).

H is called a solution of proper brave or cautious induction respectively . Example 4. Consider Example 3, H1, H2 and H3 are solutions of brave induction and only H1 is a solution of proper brave induction.

Relations to brave and cautious induction are as follows.

Proposition 5. Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, let

B be background knowledge and O an observation.

{ If H is a solution of proper cautious induction, then H is a solution of proper brave induction. { If H is a solution of proper cautious induction, then H is a solution of cautious induction. { If H is a solution of proper brave induction, then H is a solution of brave induction.

When B [H has only one answer set, the converse implication holds respectively.

Proof. H is a solution of proper cautious induction, then H is a solution of brave induction. If there exists another solution H0 of brave induction such that AS(H0) AS(H), then H0 is also a solution of cautious induction, which con icts to the precondition that H is a solution of proper cautious induction.

Proper brave (resp. cautious) induction has a solution if and only if brave (resp. cautious) induction has a solution. The conditions for the existence of solutions for triples hLCT ; LCT ; LCT i and hLASP ; LGA; LASP i have been discussed in [ 14 ]. We extend the results here.

Proposition 6 (Necessary conditions for the existence of solutions). Let B be background knowledge and O an observation.

{ Given the triple hLCT ; LCT ; LCT V i, proper brave induction (resp. brave induction, proper cautious induction, cautious induction) has a solution, only if B [ O is consistent. { Given the triple hLASP ; LGL; LASP V i, proper brave induction (resp. brave induction, proper cautious induction, cautious induction) has a solution, only if B [ O is satis able.

Proof. (1) If proper brave induction has a solution H, then B [ H has a minimal

model satisfying O, thus B [ O is consistent. (2) If proper brave induction has a solution H, then B [ H has an answer set satisfying O, thus B [ O is satisable. The proofs for brave induction, proper cautious induction, and cautious induction are similar.

Given the triple hLCT ; LCT ; LCT V i, B [ O is consistent is not a su cient

condition for the existence of solutions. For example, given B = ; and O = fp(a); :p(b)g, MM (B [ O) 6= ;. However, proper brave induction (resp. brave induction, proper cautious induction, cautious induction) does not have a solution.

Given the triple hLASP ; LGL; LASP V i, B [ O is consistent is not a necessary con

dition for the existence of solutions. For example, given B = fp(a) not p(a)g and O = fq(a)g, AS(B [ O) = ;. However, H = fp(X); q(X)g is a solution of proper brave induction.

Corollary 1 (Necessary condition of solutions). Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, let B be background knowledge and O an observation. H is a solution of proper brave induction (resp. brave induction, proper cautious induction, cautious induction), only if B [ H [ O is consistent.

Now we provide some properties of proper brave and cautious induction.

Given two clausal theories T1 and T2, we denote T1 _ T2 to be a clausal theory

that is logically equivalent to the formula VC2T1 C _ VC2T2 C.

Proposition 7. Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, both

H1 and H2 are solutions of proper brave or cautious induction does not imply that H1 [ H2 is a solution of proper brave or cautious induction. Example 5. Let B = fq(a) _ r(a); :q(a) _ :r(a)g and O = fp(a)g. Both H1 = fq(X); p(X) _ :q(X)g and H2 = fr(X); p(X) _ :r(X)g cover O under B in proper brave and cautious induction, but H1 [ H2 does not.

Proposition 8. Given the triple hLCT ; LCT ; LCT V i, both H1 and H2 are solu

tions of proper brave or cautious induction does not imply that H1 _ H2 is a solution of proper brave or cautious induction.

Note that, the result is di erent from Proposition 2.5 in [ 14 ] for brave and cautious induction. Though H1 _H2 is a solution of brave induction, it is possible that MM (H1) MM (H1 _ H2). Example 5 is such an example.

Proposition 9. Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, H

covers both O1 and O2 under B in proper cautious induction implies that H covers O1 [ O2 under B in proper cautious induction. But this is not the case for proper brave induction.

Example 6. Let B = fp(X) _ q(X)g, O1 = fp(a)g, and O2 = fq(a)g. Then H = ; covers both O1 and O2 under B in proper brave induction, but H does not cover O1 [ O2 under B.

Proposition 10. Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, H

covers O under both B1 and B2 in proper brave or cautious induction does not imply that H covers O under B1 [ B2 in proper brave or cautious induction. Example 7. Let B1 = fp(a)g, B2 = f:f (x) p(x)g, O = ff (a)g. H = ff (X)g covers O under both B1 and B2 in proper brave and cautious induction, but H does not cover O under B1 [ B2.

Sakama and Inoue [ 14 ] provided algorithms to compute solutions of brave induction for triples hLCT ; LCT ; LCT i and hLASP ; LGA; LASP i. From previous discussions, the idea of proper brave induction can be used to optimize the solutions of brave induction. One such optimization procedure is as follows: 1. for each rule r in the hypothesis H and each atom A 2 head(r), let r0 = head(r) n fAg body(r) and H0 = (H n frg) [ fr0g;

2. if H0 is still a solution of brave induction and AS(H0 [ B) AS(H [ B),

then replace r by r0.

In Example 1, H1 can be obtained from H3 by the optimization procedure.

Proposition 11. Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, let

B be background knowledge, O an observation, H a solution of brave induction, and H0 a hypothesis obtained from H by the above optimization procedure. AS(H0 [ B) AS(H [ B).

Proof. Note that, in the optimization procedure, in each step H0 is required to satisfy the condition that AS(H0 [ B) AS(H [ B). Then after nite steps, AS(H0 [ B) AS(H [ B).

Notice that, the condition AS(H0 [ B) AS(H [ B) in the optimization

procedure is necessary for the validity of Proposition 11.

Example 8. Let B = fp(a) q(a)g, O = fp(ag), H = fp(x) _ q(x)g, and H0 = fq(x)g. Both H and H0 cover O under B. However, AS(H [B) = ffp(a)gg, AS(H0 [ B) = ffp(a); q(a)gg, and AS(H0 [ B) 6 AS(H [ B).

There are some syntactic conditions for guaranteeing the condition AS(H0 [

B) AS(H [ B) in the optimization procedure. For instance, if there does

not exist another rule r 2 H0 [ B such that A 2 head(r ), then AS(H0 [

B) AS(H [ B) in the procedure. Moreover, we can improve the optimization procedure for the triple hLASP ; LGL; LASP V i.

An improved optimization procedure for the triple hLASP ; LGL; LASP V i is as

follows: 1. for each rule r in the hypothesis H and each atom A 2 head(r), let r0 = head(r) n fAg body(r) [ fnot Ag and H0 = (H n frg) [ fr0g; 2. if H0 is still a solution of brave induction, then replace r by r0.

Proposition 12. Given the triple hLASP ; LGL; LASP V i, let B be background knowl

edge, O an observation, H a solution of brave induction, and H0 a hypothesis obtained from H by the above optimization procedure. AS(H0 [ B) AS(H [ B).

Proof. S is an answer set of H0 [ B implies that S is a model of H [ B. If S is

not an answer set of H [ B, then there exists a model S0 of (H [ B)S such that S0 S.

Let a be a ground atom corresponding to the atom A in the procedure and r be the grounding rule corresponding to the rule r0 and a. If a 2 S, then fr S g = ; and S0 satis es r S . If a 2= S, then a 2= S0 and S0 satis es r S . So S0 is still a model of (H0 [ B)S , which con icts to the condition that S is an answer of H0 [ B. 5

Computational Complexity In this section, we consider computational complexity of proper brave induction.

The classes PK, kP, kP of the Polynomial Hierarchy [11] are de ned as follows:

0P = 0P = 0P = P and for all k 1;

P kP = P k 1 ;

P kP = NP k 1 ; kP = co- kP:

The class DkP is de ned as the class of problems that consist of the conjunction

of two independent problems from kP and kP. In particular, NP = 1P, co-NP = 1P, and DP = D1P. For all k 1,

P k

DkP

P k+1

P k+1

PSPACE:

First, we provide some computational complexity results about clausal theories and ASP programs. Notice that, we view a program with variables as a shorthand of its ground instantiations. We only consider ground clausal theories and ground ASP programs in this section.

Lemma 1. Let H1 and H2 be (ground) clausal theories or DLPs. { Deciding whether AS(H1) AS(H2) is 2P-complete. { Deciding whether AS(H1) = AS(H2) is 2P-complete.

{ Deciding whether AS(H1) AS(H2) is D2P-complete.

Proof. (1) The complement of the problem is in 2P, as we can guess a set S

such that S 2 AS(H1) and S 2= AS(H2) and the problem of deciding whether

S 2 AS(H1) is co-NP-complete [4]. The hardness can be proved by reducing the

problem of deciding whether AS(H1) = ; to whether AS(H1) AS(fp not pg). Note that, deciding whether AS(H1) = ; is 2P-complete [ 4 ].

(2) can be proved in the same manner.

(3) The problem is equivalent to deciding whether AS(H1) AS(H2) and AS(H1) 6= AS(H2), so it is in D2P. The hardness can be proved by reducing the problem of deciding whether the conjunction 9X8Y E ^ 8X09Y 0E0 is satis able to whether AS(H1) AS(H2), where H2 has an answer set i 9X8Y E is satis able and H1 has an answer set i 8X09Y 0E0 is satis able.

Similar to the proof for Lemma 1, we have the following lemma. Lemma 2. Let H1 and H2 be (ground) NLPs.

{ Deciding whether AS(H1) AS(H2) is co-NP-complete. { Deciding whether AS(H1) = AS(H2) is co-NP-complete. { Deciding whether AS(H1) AS(H2) is DP-complete.

Now we provide computational complexity results of proper brave induction. We use LNLP and LNLP V to denote the set of NLPs and the set of NLPs without any constants.

Theorem 1. The following computational complexity results hold: { Given the triple hLNLP ; LGL; LNLP V i, deciding whether a given hypothesis is a solution of brave induction is NP-complete; deciding the existence of solutions in brave induction or proper brave induction is in 2P and NP-hard; deciding whether a given hypothesis is a solution of proper brave induction is in 2P and co-NP-hard. { Given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i, deciding whether a given hypothesis is a solution of brave induction is

2P-complete;

deciding the existence of solutions in brave induction or proper brave induction is in 3P and 2P-hard; deciding whether a given hypothesis is a solution of proper brave induction is in 3P and 2P-hard.

Proof. (1) The problem is equivalent to checking whether a set O of ground literals is satis ed by some answer set of an NLP H [ B, which is known to be NP-complete.

(2) The problem is in 2P, as we can guess a hypothesis H such that H is a solution of brave induction, which can be veri ed in polynomial time by an NP oracle. The NP-hardness can be proved by reducing the problem of deciding whether a ground NLP P has an answer set to whether there exists a hypothesis covers an observation O under background knowledge B, where B is obtained from P by replacing each occurrence of a ground atom A in P by an atom fA(cA) and adding rules fA(c0A) and fA(c0A0 ) for each ground atom A in P , and O = ff (c)g such that both f and c do not appear in B. It is easy to verify that, there exists a hypothesis (i.e., ff (X)g) covers O under B iff P has an answer set. Note that, deciding whether a ground NLP has an answer set is NP-complete.

(3) The complement of the problem is in 2P, as we can guess another solution

H0 of brave induction such that AS(H0 [ B) AS(H [ B), which can be veri ed

in polynomial time by an NP oracle. The co-NP-hardness can be proved from the fact that H covers an observation O under background knowledge B in brave induction iff H0 does not cover O under B [ B0 in proper brave induction, where

H0 is obtained from H by adding not f (X) in body(r) of each r 2 H and adding

f 0(X) not f (X) and f (X) not f 0(X) with new symbols f and f 0, and B0 = fA f (X) j A 2 Og [ f A; f (X) j :A 2 Og.

(4) can be proved in the same manner of the proof for Proposition 3. (5) and (6) can be proved in the same manner for (2) and (3) respectively.

From Proposition 3, given the triple hLCT ; LCT ; LCT i or hLASP ; LGA; LASP i,

deciding the existence of solutions in brave induction is NP-complete. However, the problem is 2P-hard given the triple hLCT ; LCT ; LCT V i or hLASP ; LGL; LASP V i. The reason is that, the hypothesis space is restricted in the latter case and

B [ O is satis able would no longer be the su cient condition for the existence

of solutions in brave induction. 6

Related Work In previous sections, we provided an optimization of brave induction called proper brave induction and compared it with brave induction in Proposition 5. From the discussion in [ 14 ], a solution of explanatory induction is always a solution of brave induction and a solution of brave induction is a solution of LFS. Then a solution of proper brave induction is always a solution of LFS. Similar to brave induction, proper brave induction is neither stronger nor weaker than LFI [ 3 ] or con rmatory induction [ 6 ]. Notice that, the idea of proper brave induction can also be extended to these logic frameworks of induction.

On the other hand, there has been much work on induction in nonmonotonic logic programs. Otero [ 10 ] and Sakama [ 13 ] extended the de nition of ILP to the stable model semantics and introduced frameworks for learning positive/negative examples in NLPs. Ray [ 12 ] developed a nonmonotonic ILP system, called XHAIL, which combines abduction and induction for constructing hypotheses. ASPAL [ 2 ], another nonmonotonic ILP system, uses ASP as a solver to compute a solution to a standard ILP task. Later, Law, Russo, and Broda [ 7 ] presented a new paradigm for ILP that allows the learning of ASP programs. Note that, the optimization based on fewer stable models or answer sets can also be applied to these nonmonotonic ILP systems. 7

Conclusion Motivated from Shapiro's de nition of model inference problems, we provide an optimization of Sakama and Inoue's brave induction, called proper brave induction, for causal theories and ASP programs. A hypothesis is a solution of proper brave induction, if it is a solution of brave induction and there does not exist another solution whose set of answer sets is a proper subset of its. We investigate formal properties of proper brave induction and develop an optimization procedure. At last, we analyze computational complexity of decision problems for proper brave induction in propositional case. We expect that the idea of the optimization will be extended to other logical frameworks for concept-learning. Acknowledgments. We thank reviewers for their helpful comments. The work was supported by NSFC under grant 61573386 and 61175057, NSFC for the Youth under grant 61403359, as well as the USTC Key Direction Project and the USTC 985 Project.

References

1. Baral , C. : Knowledge representation, reasoning and declarative problem solving . Cambridge university press ( 2003 )

2. Corapi , D. , Russo , A. , Lupu , E.: Inductive logic programming in answer set programming . In: Proceedings of the 22nd International Conference on Inductive Logic Programming (ILP-12) . pp. 91 { 97 ( 2012 )

3. De Raedt , L. : Logical settings for concept-learning . Arti cial Intelligence 95 ( 1 ), 187 { 201 ( 1997 )

4. Eiter , T. , Gottlob , G.: On the computational cost of disjunctive logic programming: Propositional case . Annals of Mathematics and Arti cial Intelligence 15 ( 3-4 ), 289 { 323 ( 1995 )

5. Flach , P.A. : Rationality postulates for induction . In: Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge . pp. 267 { 281 ( 1996 )

6. Lachiche , N.: Abduction and induction from a non-monotonic reasoning perspective . In: Abduction and Induction: Essays on their Relation and Integration , pp. 107 { 116 . Kluwer ( 2000 )

7. Law , M. , Russo , A. , Broda , K. : Inductive learning of answer set programs . In: Proceedings of the 14th European Conference on Logics in Arti cial Intelligence (JELIA-14) . pp. 311 { 325 ( 2014 )

8. Mitchell, T.M.: Generalization as search . Arti cial intelligence 18 ( 2 ), 203 { 226 ( 1982 )

9. Muggleton , S. , De Raedt , L. : Inductive logic programming: Theory and methods . The Journal of Logic Programming 19 , 629 { 679 ( 1994 )

10. Otero , R.P. : Induction of stable models . In: Proceedings of the 11th International Conference on Inductive Logic Programming (ILP-01) . pp. 193 { 205 ( 2001 )

11. Papadimitriou , C.H. : Computational complexity . John Wiley and Sons Ltd. ( 2003 )

12. Ray , O. : Nonmonotonic abductive inductive learning . Journal of Applied Logic 7 ( 3 ), 329 { 340 ( 2009 )

13. Sakama , C. : Induction from answer sets in nonmonotonic logic programs . ACM Transactions on Computational Logic (TOCL) 6 ( 2 ), 203 { 231 ( 2005 )

14. Sakama , C. , Inoue , K. : Brave induction: a logical framework for learning from incomplete information . Machine Learning 76(1) , 3 { 35 ( 2009 )

15. Shapiro , E.Y. : Inductive inference of theories from facts . Yale University, Department of Computer Science ( 1981 )