Hypothetical reasoning is an important framework for knowledge-based systems, however, its inference time grows exponentially with respect to problem size. In this paper, we present an understandable efficient method called slide-down and lift-up (SL) method which uses a linear programming technique for determining an initial search point and a non-linear programming technique for efficiently finding a near-optimal 0–1 solution. To escape from trapping into local optima, we have developed a new local handler, which systematically fixes a variable to a locally consistent value. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.
By handling incomplete hypothesis knowledge which possibly contradicts with other knowledge, hypothetical reasoning tries to find a set of element hypotheses which is sufficient for proving (or explaining) a given goal (or a given observation) [13]. Because of its theoretical basis and its practical usefulness, hypothetical reasoning is an important framework for knowledge-based systems, particularly for systems based on declarative knowledge. However, since hypothetical reasoning is a form of non-monotonic reasoning and thus an NP-complete or NP-hard problem, its inference time grows exponentially with respect to problem size. In practice, slow inference speed often becomes the most crucial problem.
There already exist several investigations trying to overcome this problem. For example, see [8], [9], [10], [11] and [12] for authors' work. Besides symbolic inference methods which have been exploited mostly in AI field, search methods working in continuous-value space have recently shown promising results in achieving efficient inference for hypothetical reasoning as well as for SAT problems and constraint satisfaction problem (CSP). This approach is closely related to mathematical programming, particularly with 0–1 integer programming. When we consider a cost-based propositional hypothetical-reasoning problem, it can be transformed into an equivalent 0–1 integer programming problem with a set of inequality constraints. Although its computational complexity still remains NP-hard, it allows us to exploit a new efficient search method in continuous-value space. One key point here is an effective use of the efficient simplex method for linear programming, which is formed by relaxing the 0–1 constraint in 0–1 integer programming. Also, non-linear programming formation provides us another possibility. These approaches may be beneficial particularly for developing efficient approximate solution methods, for example, in cost-based hypothetical reasoning [2].
The pivot-and-complement method [1] is a good approximate solution method for 0–1 integer programming. Ishizuka and Okamoto [9] used this method to realize an efficient computation of a near-optimal solution for cost-based hypothetical reasoning. Ohsawa and Ishizuka [12] have transformed the behavior of the pivot-and-complement method into a visible behavior on a knowledge network, improved its efficiency by using the knowledge structure of a given problem, and consequently developed networked bubble propagation (NBP) method. NBP method can empirically achieve a polynomial-time inference of N1.4 where N is the number of possible element hypotheses, to produce a good quality near-optimal solution in cost-based hypothetical reasoning.
The key point of these methods is the determination of an initial search point by using simplex method and efficient local searches around this point in continuous space for eventually finding a near-optimal 0–1 solution. However, in order to avoid trapping into locally optimal points, a sophisticated control of the local search is required; as a result, the inference mechanisms have become complicated and for humans they are difficult to understand.
On the other hand, Gu [5] and [6] exploited an efficient method to solve SAT problems by transforming them into unconstrained non-linear programming; the SAT problem is related to propositional hypothetical reasoning. There are several methods for unconstrained non-linear programming, i.e. the steepest descent method, Newton's method, quasi-Newton method, and conjugate direction method. The mechanisms of these local search methods are easy to understand as they basically proceed by descending a valley of a function. However, since these methods simply try to find a single solution depending upon an initial search point, they cannot be used for finding a (near) optimal solution for the following reason: if they are trapped into local optima, they have to restart from a new initial point that is to be selected randomly.
In order to find a near-optimal solution using the simple non-linear programming technique, we combine a linear programming, namely simplex method, to determine the initial search point of the non-linear programming. The search, however, often falls into local optima and an effective method escaping from these local optima is required. In this paper, we present an effective method named variable fixing method for this problem. Variable fixing corrects a local inconsistency at each locally optimal point and allows to restart the search. Unlike conventional random restart schemes, this method permits to direct the search systematically using the knowledge structure of a given problem.
As sliding-down operations toward a valley of a non-linear function and lifting-up operations are repeated alternately, we call this method slide-down and lift-up (SL) method. By illustrating its behavior visually, we show that its mechanism is easily understandable and also achieves good inference efficiency that is close to the efficiency of the NBP method.
In this paper, we will treat hypothetical reasoning problems that are represented in propositional Horn clauses; we will also allow for (in)consistency constraints among hypotheses.
We have presented the SL method for cost-based hypothetical reasoning, which can find a near-optimal solution in polynomial-time in cost-based hypothetical reasoning. It uses both linear and non-linear programming techniques. Moreover, it incorporates a local handler to escape from trapping into locally optimal points. The notable feature of this method is its simple and understandable search behavior as visually illustrated here, though at present its speed performance is slightly lower than that of the NBP method [12]. The mechanism of the SL method may also be useful to develop systematic polynomial-time methods for finding near-optimal solutions in other problems such as the constraint optimization problem.
