Overriding subsuming rules

This paper is concerned with intelligent agents that are able to perform nonmonotonic reasoning, not only with, but also about general rules with exceptions. More precisely, the focus is on enriching a knowledge base Γ with a general rule that is subsumed by other rules already there. Such a problem is important because evolving knowledge needs not follow logic as it is well-known from e.g. the belief revision paradigm. However, belief revision is mainly concerned with the case that the extra information logically conflicts with Γ. Otherwise, the extra knowledge is simply doomed to extend Γ with no change altogether. The problem here is different and may require a change in Γ even though no inconsistency arises. The idea is that when a rule is to be added, it might need to override any rule that subsumes it: preemption must take place. A formalism dedicated to reasoning with and about rules with exceptions is introduced. An approach to dealing with preemption over such rules is then developed. Interestingly, it leads us to introduce several implicants concepts for rules that are possibly defeasible.     

Extracting compact and information lossless sets of fuzzy association rules

Applying classical association rule extraction framework on fuzzy datasets leads to an unmanageably highly sized association rule sets. Moreover, the discretization operation leads to information loss and constitutes a hamper towards an efficient exploitation of the mined knowledge. To overcome such a drawback, this paper proposes the extraction and the exploitation of compact and informative generic basis of fuzzy association rules. The presented approach relies on the extension, within the fuzzy context, of the notion of closure and Galois connection, that we introduce in this paper. In order to select without loss of information a generic subset of all fuzzy association rules, we define three fuzzy generic basis from which remaining (redundant) FARs are generated. This generic basis constitutes a compact nucleus of fuzzy association rules, from which it is possible to informatively derive all the remaining rules. In order to ensure a sound and complete derivation process, we introduce an axiomatic system allowing the complete derivation of all the redundant rules. The results obtained from experiments carried out on benchmark datasets are very encouraging. They highlight a very important reduction of the number of the extracted fuzzy association rules without information loss.     

Rough set approach to multiple criteria classification with imprecise evaluations and assignments

Dominance-based Rough Set Approach (DRSA) has been introduced to deal with multiple criteria classification (also called multiple criteria sorting, or ordinal classification with monotonicity constraints), where assignments of objects may be inconsistent with respect to dominance principle. In this paper, we consider an extension of DRSA to the context of imprecise evaluations of objects on condition criteria and imprecise assignments of objects to decision classes. The imprecisions are given in the form of intervals of possible values. In order to solve the problem, we reformulate the dominance principle and introduce second-order rough approximations. The presented methodology preserves well-known properties of rough approximations, such as rough inclusion, complementarity, identity of boundaries and precisiation. Moreover, the meaning of the precisiation property is extended to the considered case. The paper presents also a way to reduce decision tables and to induce decision rules from rough approximations.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

Bounds on the value of information in uncertain decision problems

The cost of obtaining good information regarding the various probability distributions needed for the solution of most stochastic decision problems is considerable. It is important to consider questions such as: (1) what minimal amounts of information are sufficient to determine optimal decision rules; (2) what is the value of obtaining knowledge of the actual realization of the random vectors; and (3) what is the value of obtaining some partial information regarding the actual realization of the random vectors. This paper is primarily concerned with questions two and three when the decision maker has an a priori knowledge of the joint distribution function of the random variables. Some remarks are made regarding results along the lines of question one. Mention is made of assumptions sufficient so that knowledge of means, or of means, variances, co-variances and n-moments are sufficient for the calculation of optimal decision rules. The analysis of the second question leads to the development of bounds on the value of perfect information. For multiperiod problems it is important to consider when the perfect information is available. Jensen's inequality is the key tool of the analysis. The calculation of the bounds requires the solution of nonlinear programs and the numerical evaluation of certain functions. Generally speaking, tighter bounds may be obtained only at the expense of additional information and computational complexity. Hence, one may wish to compute some simple bounds to decide upon the advisability of obtaining more information. For the analysis of the value of partial information it is convenient to introduce the notion of a signal. Each signal represents the receipt of certain information, and these signals are drawn from a given probability distribution. When a signal is received, it alters the decision maker's perception of the probability distributions inherent in his decision problem. The choice between different information structures must then take into account these probability distributions as well as the decision maker's preference function. A hierarchy of bounds may be determined for partial information evaluation utilizing the tools of the multiperiod perfect information case. However, the calculation of these bounds is generally considerably more dicult than the calculation of similar boulids in the perfect information case. Most of the analysis is directed towards problems in which the decision maker has a linear utility function over profits, costs or some other numerical variable. However, some of the bounds generalize to the case when the utility function is strictly increasing and concave.     

The scorix: A popular representation of votes revisited

In earlier work, some of the present authors have advocated that the search for monotonicity of the votrix, a well-known representation of votes, leads to natural ranking rules. In order to exploit hitherto unconsidered information, we introduced a new representation of votes, the votex, and the search for monotonicity was extended to this representation. Previously, we have focused on representations of votes based on pairwise information and we have left aside another well-known representation of votes based on positional information: the scorix. In this paper, we propose to exploit the monotonicity of the scorix and introduce a new family of ranking rules based on the search for this new type of monotonicity. It is shown that, in case the scorix is monotone, all existing scoring ranking rules give the same ranking as output.     

数据库中布尔型及广义模糊加权关联规则的挖掘

引入布尔型加权关联规则和广义模糊加权关联规则的概念,并分别给出挖掘这些规则的计算方法．     

Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks

In this paper, we introduce a new clustering problem in underwater sensor networks, namely minimum average routing path clustering problem (MARPCP). To deal with the high complexity of MARPCP, we relax it to a special case of minimum weight dominating set problem (MWDSP). We show an existing algorithm for MWDSP can produce an approximate solution for MARPCP. Also, we design a constant factor approximation algorithm for MARPCP, which is much faster than the first method.     

Global investing risk: a case study of knowledge assessment via rough sets

This paper presents an application of knowledge discovery via rough sets to a real life case study of global investing risk in 52 countries using 27 indicator variables. The aim is explanation of the classification of the countries according to financial risks assessed by Wall Street Journal international experts and knowledge discovery from data via decision rule mining, rather than prediction; i.e. to capture the explicit or implicit knowledge or policy of international financial experts, rather than to predict the actual classifications. Suggestions are made about the most significant attributes for each risk class and country, as well as the minimal set of decision rules needed. Our results compared favorably with those from discriminant analysis and several variations of preference disaggregation MCDA procedures. The same approach could be adapted to other problems with missing data in data mining, knowledge extraction, and different multi-criteria decision problems, like sorting, choice and ranking.     

Specifying Rewrite Strategies for Interactive Exercises

Strategies specify how a wide range of exercises can be solved incrementally, such as bringing a logic proposition to disjunctive normal form, reducing a matrix, or calculating with fractions. In this paper we introduce a language for specifying strategies for solving exercises. This language makes it easier to automatically calculate feedback, for example when a user makes an erroneous step in a calculation. We can automatically generate worked-out examples, track the progress of a student by inspecting submitted intermediate answers, and report back suggestions in case the student deviates from the strategy. Thus it becomes less labor-intensive and less ad-hoc to specify new exercise domains and exercises within that domain. A strategy describes valid sequences of rewrite rules, which turns tracking intermediate steps into a parsing problem. This is a promising view at interactive exercises because it allows us to take advantage of many years of experience in parsing sentences of context-free languages, and transfer this knowledge and technology to the domain of stepwise solving exercises. In this paper we work out the similarities between parsing and solving exercises incrementally, we discuss generating feedback on strategies, and the implementation of a strategy recognizer.     

Some robust objectives of FCM for data analyzing

There are many data clustering techniques available to extract meaningful information from real world data, but the obtained clustering results of the available techniques, running time for the performance of clustering techniques in clustering real world data are highly important. This work is strongly felt that fuzzy clustering technique is suitable one to find meaningful information and appropriate groups into real world datasets. In fuzzy clustering the objective function controls the groups or clusters and computation parts of clustering. Hence researchers in fuzzy clustering algorithm aim is to minimize the objective function that usually has number of computation parts, like calculation of cluster prototypes, degree of membership for objects, computation part for updating and stopping algorithms. This paper introduces some new effective fuzzy objective functions with effective fuzzy parameters that can help to minimize the running time and to obtain strong meaningful information or clusters into the real world datasets. Further this paper tries to introduce new way for predicting membership, centres by minimizing the proposed new fuzzy objective functions. And experimental results of proposed algorithms are given to illustrate the effectiveness of proposed methods.     

A perspective on artificial intelligence: Learning to learn

The classical approach to the acquisition of knowledge in artificial intelligence has been to program the intelligence into the machine in the form of specific rules for the application of the knowledge: expert systems. Unfortunately, the amount of time and resources required to program an expert system with sufficient knowledge for non-trivial problem-solving is prohibitively large. An alternative approach is to allow the machine tolearn the rules based upon trial-and-error interaction with the environment, much as humans do. This will require endowing the machine with a sophisticated set of sensors for the perception of the external world, the ability to generate trial actions based upon this perceived information, and a dynamic evaluation policy to allow it to measure the effectiveness of its trial actions and modify its repertoire accordingly. The principles underlying this paradigm, known ascollective learning systems theory, have already been applied to sophisticated gaming problems, demonstrating robust learning and dynamic adaptivity.The fundamental building block of a collective learning system is thelearning cell, which may be embedded in a massively parallel, hierarchical data communications network. Such a network comprising 100 million learning cells will approach the intelligence capacity of the human cortex. In the not-too-distant future, it may be possible to build a race of robotic slaves to perform a wide variety of tasks in our culture. This goal, while irresistibly attractive, is most certainly fraught with severe social, political, moral, and economic difficulties.This paper was given as an invited talk on the 12th Symposium on Operations Research, University of Passau, September 1987.     

A partition-based global optimization algorithm

This paper is devoted to the study of partition-based deterministic algorithms for global optimization of Lipschitz-continuous functions without requiring knowledge of the Lipschitz constant. First we introduce a general scheme of a partition-based algorithm. Then, we focus on the selection strategy in such a way to exploit the information on the objective function. We propose two strategies. The first one is based on the knowledge of the global optimum value of the objective function. In this case the selection strategy is able to guarantee convergence of every infinite sequence of trial points to global minimum points. The second one does not require any a priori knowledge on the objective function and tries to exploit information on the objective function gathered during progress of the algorithm. In this case, from a theoretical point of view, we can guarantee the so-called every-where dense convergence of the algorithm.     

Logical testing for rule-base management

We present a procedure to logically reduce simple implications that comprise the rule-base of an expert system. Our method uses topological sorting on a digraph representation that detects logical inconsistency and circular reasoning in linear-time. Then, the sort order provides an efficient method to detect and eliminate forced values and redundant rules. We consider additional diagnostic aids for the rule-base manager, notably how to range the number of propositions that could be true and how to consolodate the rule-base. We than show how the simple case may be extended to logically test a general rule-base with a decomposition principle.     

Effects of regulatory delays and uncertainty on pricing decisions

In this paper we introduce a simple decision rule that a single product firm may use for filing for a price change to offset variations of the marginal cost. We consider a regulatory body whose response to the price change request involves a time delay with an exponential distribution. Two possibilities regarding the response of the regulatory body are considered. In one case it is assumed to be a binary approval process in which the rate adjustment is either approved in its entirety or rejected. In the second case we consider a partial approval process with a more general distribution. Decision rules for each case are developed. Finally we derive a multi-stage decision rule in which filing decisions are continuously updated based on temporal variations of the cost function. The multi-stage pricing decision model assumes that marginal cost escalation satisfies a Markovian jump process.This work was completed while the authors were with Bell Laboratories, USA.     

On existence and stability in the theory of swelling porous elastic soils

The aim of this paper is to introduce a new functional in thestudy of swelling porous elastic soils saturated by a fluid.This new functional is a useful tool; it allows us to provethe existence of solutions in the case of a compressible fluid.We also prove the stability of solutions and the exponentialdecay in the case of an incompressible fluid. We study as wellthe continuous dependence with respect to the initial time.     

Sparse Convex Clustering

Convex clustering, a convex relaxation of k-means clustering and hierarchical clustering, has drawn recent attentions since it nicely addresses the instability issue of traditional nonconvex clustering methods. Although its computational and statistical properties have been recently studied, the performance of convex clustering has not yet been investigated in the high-dimensional clustering scenario, where the data contains a large number of features and many of them carry no information about the clustering structure. In this article, we demonstrate that the performance of convex clustering could be distorted when the uninformative features are included in the clustering. To overcome it, we introduce a new clustering method, referred to as Sparse Convex Clustering, to simultaneously cluster observations and conduct feature selection. The key idea is to formulate convex clustering in a form of regularization, with an adaptive group-lasso penalty term on cluster centers. To optimally balance the trade-off between the cluster fitting and sparsity, a tuning criterion based on clustering stability is developed. Theoretically, we obtain a finite sample error bound for our estimator and further establish its variable selection consistency. The effectiveness of the proposed method is examined through a variety of numerical experiments and a real data application. Supplementary material for this article is available online.     

Modeling Discrete Event Systems With Faults Using a Rules-based Modeling Formalism

Obtaining accurate models of systems which are prone to failures and breakdowns is a difficult task. In this paper we present a methodology which makes the task of modeling failure prone discrete event systems (DESs) considerably less cumbersome, less error prone, and more user-friendly. The task of obtaining commonly used automata models for DESs is non-trivial for most practical systems, owing to the fact that the number of states in the commonly used automata models is exponential in the number of signals and faults. In contrast a model of a discrete event system, in the rules based modeling formalism proposed by the co-authors of this paper, is of size polynomial in the number of signals and faults. In order to model failures, we augment the signals set of the rules based formalism to include binary valued fault signals, the values representing either a non-faulty or a faulty state of a certain failure type. Addition of new fault signals requires introduction of new rules for the added fault signal events, and also modification of the existing rules for non-fault events. The rules based modeling formalism is further extended to model real-time systems, and we apply it to model delay-faults of the system as well. The model of a failure prone DES in the rules based can automatically be converted into an equivalent (timed)-automaton model for a failure analysis in the automaton model framework.     

On Multi-threaded Metrical Task Systems

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities.In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information.