MICAI 2006: Advances in Artificial Intelligence

The paper follows the path that AI has taken since its beginnings until the brink of the third millennium. New areas, such as Agents, have sprout; other subjects (Learning) have diminished. Areas have separated (Vision, Image Processing) and became independent, self-standing. Some areas have acquired formality and rigor (Vision). Important problems (Spelling, Chess) have been solved. Other problems (Disambiguation) are almost solved or about to be solved. Many challenges (Natural language translation) still remain. A few parts of the near future are sketched through predictions: important problems about to be solved, and the relation of specific AI areas with other areas of Computer Science.

We explore the properties of subgraphs (called Markovian subgraphs) of a decomposable graph under some conditions. For a decomposable graph

$\mathcal{G}$

and a collection

γ

of its Markovian subgraphs, we show that the set

$\chi(\mathcal{G})$

of the intersections of all the neighboring cliques of

$\mathcal{G}$

contains

. We also show that

$\chi(\mathcal{G})=\cup_{g\in\gamma}\chi(g)$

holds for a certain type of

$\mathcal{G}$

which we call a maximal Markovian supergraph of

γ

. This graph-theoretic result is instrumental for combining knowledge structures that are given in undirected graphs.

A simple representation framework for ontological knowledge with dynamic and deontic characteristics is presented. It represents structural relationships (

is

-

a

,

part

/

whole

), dynamic relationships (actions such as

register

,

pay

, etc.), and conditional relationships (

if

-

then

-

else

). As a case study, we apply our representation language to the task of requirements elicitation in software engineering. We show how our pre-conceptual schemas can be obtained from controlled natural language discourse and how these diagrams can be then converted into standard UML diagrams. Thus our representation framework is shown to be a useful intermediate step for obtaining UML diagrams from natural language discourse.

This paper presents a formal model of the knowledge representation scheme KRFP based on the Fuzzy Petri Net (FPN) theory. The model is represented as an 11-tuple consisting of the components of the FPN and two functions that give semantic interpretations to the scheme. For the scheme a fuzzy recognition-inference procedure, based on the dynamical properties of the FPN and the inverse –KRFP scheme, is described in detail. An illustrative example of the fuzzy recognition algorithm for the knowledge base, designed by the KRFP, is given.

This paper addresses an extended order-sorted logic that can deal with structured sort symbols consisting of multiple ordinary words like noun phrases, and proposes inference rules for the resolution process semantically interpreting the sort symbols word by word. Each word in a sort symbol can represent a general concept or a particular object, which is a variable or a constant having the word itself as the sort symbol. It may be a proper noun or variable. This paper also describes an application scheme of the proposed inference rules and an algorithm for judging the subsort relation between complex sort symbols.

In this paper we introduce preference rules which allow us to specify preferences as an ordering among the possible solutions of a problem. Our approach allow us to express preferences for general theories. The formalism used to develop our work is Answer Set Programming. Two distinct semantics for preference logic programs are proposed. Finally, some properties that help us to understand these semantics are also presented.

This paper presents an object-oriented framework based on the E-R computational creativity model. It proposes a generic architecture for solving problems that require a certain amount of creativity. The design is based on advanced Software Engineering concepts for object-oriented Framework Design. With the use of the proposed framework, the knowledge of the E-R computational model can be easily extended. This model is important since it tries to diagram the human creativity process when a human activity is done. The framework is described together with two applications under development which implement the framework.

This article presents the implementation of first-order interval type-1 non-singleton type-2 TSK fuzzy logic system (FLS). Using input-output data pairs during the forward pass of the training process, the interval type-1 non-singleton type-2 TSK FLS output is calculated and the consequent parameters are estimated by back-propagation (BP) method. In the backward pass, the error propagates backward, and the antecedent parameters are estimated also by back-propagation. The proposed interval type-1 non-singleton type-2 TSK FLS system was used to construct a fuzzy model capable of approximating the behaviour of the steel strip temperature as it is being rolled in an industrial Hot Strip Mill (HSM) and used to predict the transfer bar surface temperature at finishing Scale Breaker (SB) entry zone, being able to compensate for uncertain measurements that first-order interval singleton type-2 TSK FLS can not do.

This paper addresses state estimation of discrete event systems (

DES

) using a fuzzy reasoning approach; a method for approximating the current state of

DES

with uncertainty in the duration of activities is presented. The proposed method is based on a

DES

specification given as a fuzzy timed Petri net in which fuzzy sets are associated to places; a technique for the recursive computing of imprecise markings is given, then the conversion to discrete marking is presented.

In this paper we investigate real-time adaptive extensions of our fuzzy logic based approach for providing biologically based motivations to be used in evolutionary mobile robot learning. The main idea is to introduce active battery level sensors and recharge zones to improve robot behavior for reaching survivability in environment exploration. In order to achieve this goal, we propose an improvement of our previously defined model, as well as a hybrid controller for a mobile robot, combining behavior-based and mission-oriented control mechanism. This method is implemented and tested in action sequence based environment exploration tasks in a Khepera mobile robot simulator. We investigate our technique with several sets of configuration parameters and scenarios. The experiments show a significant improvement in robot responsiveness regarding survivability and environment exploration.

When sensor networks are deployed in hostile environments, an adversary may compromise some sensor nodes and use them to inject false sensing reports. False reports can lead to not only false alarms but also the depletion of limited energy resource in battery powered networks. The interleaved hop-by-hop authentication scheme detects such false reports through interleaved authentication. In this scheme, the choice of a security threshold value is important since it trades off security and overhead. In this paper, we propose a fuzzy logic-based adaptive threshold determining method for the interleaved authentication scheme. The fuzzy rule-based system is exploited to determine a security threshold value by considering the number of cluster nodes, the number of compromised nodes, and the energy level of nodes. The proposed method can conserve energy, while it provides sufficient resilience.

No single software development estimation technique is best for all situations. A careful comparison of the results of several approaches is most likely to produce realistic estimates. On the other hand, unless engineers have the capabilities provided by personal training, they cannot properly support their teams or consistently and reliably produce quality products. In this paper, an investigation aimed to compare a personal Fuzzy Logic System (FLS) with linear regression is presented. The evaluation criteria are based upon ANOVA of MRE and MER, as well as MMRE, MMER and pred(25). One hundred five programs were developed by thirty programmers. From these programs, a FLS is generated for estimating the effort of twenty programs developed by seven programmers. The adequacy checking as well as a validation of the FLS are made. Results show that a FLS can be used as an alternative for estimating the development effort at personal level.

Nowadays the dynamic behavior of a computer network system can be modeled from the perspective of a control system. One strategy to be follow is the real-time modeling of magnetic levitation system. After this representation, next stage is how a control approach can be affected and modified. In that respect, this paper proposes a control reconfiguration strategy from the definition of an Intelligent Fuzzy System computer network reconfiguration. Several stages are including, how computer network takes place, as well as how control techniques are modified using Takagi-Sugeno Fuzzy Control.

The application of fuzzy control to large-scale complex systems is not a trivial task. For such systems the number of the fuzzy IF-THEN rules exponentially explodes. If we have

l

possible linguistic properties for each of

n

variables, with which we will have

l

n

possible combinations of input values. Large-scale systems require special approaches for modeling and control. In our work the sensory fusion method is studied in an attempt to reduce the size of the inference engine for large-scale systems. This method reduces the number of rules considerably. But, in order to do so, the adequate parameters should be estimated, which, in the traditional way, depends on the experience and knowledge of a skilled operator. In this work, we are proposing a method to automatically estimate the corresponding parameters for the sensory fusion rule base reduction method to be applied to fuzzy control complex systems. In our approach, the parameters of the sensory fusion method are found through the use of genetic algorithms. The implementation process, the simulation experiments, as well as some results are described in the paper.

This paper deals with a fault detection system design for uncertain nonlinear systems modeled as T-S fuzzy systems with the integral quadratic constraints. In order to generate a residual signal, we used a left coprime factorization of the T-S fuzzy system. Using a multi-objective filter, the fault occurrence can be detected effectively. A simulation study with nuclear steam generator level control system shows that the suggested method can be applied to detect the fault in actual applications.

Expert knowledge in most of application domains is uncertain, incomplete and perception-based. For processing such expert knowledge an expert system should be able to represent and manipulate perception-based evaluations of uncertainties of facts and rules, to support multiple-valuedness of variables, and to make conclusions with unknown values of variables. This paper describes an uncertainty model based on two algebras of conjunctive and disjunctive multi-sets used by the inference engine for processing perception-based evaluations of uncertainties. The discussion is illustrated by examples of the expert system, called SMART-Agua, which is aimed to diagnose and give solution to water production problems in petroleum wells.

This paper presents a new version of an existing hybrid model for the development of knowledge-based systems, where case-based reasoning is used as a problem solver. Numeric predictive attributes are modeled in terms of fuzzy sets to define neurons in an associative Artificial Neural Network (ANN). After the Fuzzy-ANN is trained, its weights and the membership degrees in the training examples are used to automatically generate a local distance function and an attribute weighting scheme. Using this distance function and following the Nearest Neighbor rule, a new hybrid Connectionist Fuzzy Case-Based Reasoning model is defined. Experimental results show that the model proposed allows to develop knowledge-based systems with a higher accuracy than when using the original model. The model takes the advantages of the approaches used, providing a more natural framework to include expert knowledge by using linguistic terms.

Belief propagation (BP) algorithm has been becoming increasingly a popular method for probabilistic inference on general graphical models. When networks have loops, it may not converge and, even if converges, beliefs, i.e., the result of the algorithm, may not be equal to exact marginal probabilities. When networks have loops, the algorithm is called Loopy BP (LBP). Tatikonda and Jordan applied Gibbs measures theory to LBP algorithm and derived a sufficient convergence condition. In this paper, we utilize Gibbs measure theory to investigate the discrepancy between a marginal probability and the corresponding belief. Consequently, in particular, we obtain an error bound if the algorithm converges under a certain condition. It is a general result for the accuracy of the algorithm. We also perform numerical experiments to see the effectiveness of the result.

In this paper, we pursue application of Gibbs measure theory to LBP in two ways. First, we show this theory can be applied directly to LBP for factor graphs, where one can use higher-order potentials. Consequently, we show beliefs are just marginal probabilities for a certain Gibbs measure on a computation tree. We also give a convergence criterion using this tree. Second, to see the usefulness of this approach, we apply a well-known general condition and a special one, which are developed in Gibbs measure theory, to LBP. We compare these two criteria and another criterion derived by the best present result. Consequently, we show that the special condition is better than the others and also show the general condition is better than the best present result when the influence of one-body potentials is sufficiently large. These results surely encourage the use of Gibbs measure theory in this area.

We analyse how a learner modelling engine that uses belief functions for evidence and belief representation, called

xLM

, reacts to different input information about the learner in terms of changes in the state of its beliefs and the decisions that it derives from them. The paper covers

xLM

induction of evidence with different strengths from the qualitative and quantitative properties of the input, the amount of indirect evidence derived from direct evidence, and differences in beliefs and decisions that result from interpreting different sequences of events simulating learners evolving in different directions. The results here presented substantiate our vision of

xLM

is a proof of existence for a generic and potentially comprehensive learner modelling subsystem that explicitly represents uncertainty, conflict and ignorance in beliefs. These are key properties of learner modelling engines in the bizarre world of open Web-based learning environments that rely on the content+metadata paradigm.

Modern control systems and other monitoring systems require the acquisition of values of most of the parameters involved in the process. Examples of processes are industrial procedures or medical treatments or financial forecasts. However, sometimes some parameters are inaccessible through the use of traditional instrumentation. One example is the blades temperature in a gas turbine during operation. Other parameters require costly instrumentation difficult to install, operate and calibrate. For example, the contaminant emissions of power plant chimney. One solution of this problem is the use of analytical estimation of the parameter using complex differential equations. However, these models sometimes are very difficult to obtain and to maintain according the changes in the processes. Other solution is to borrow an instrument and measure a data set with the value of the difficult variable and its related variables at all the operation range. Then, use an automatic learning algorithm that allows inferring the difficult measure, given the related variables. This paper presents the use of Bayesian networks that represents the probabilistic relations of all the variables in a process, in the design of a virtual sensor. Experiments are presented with the temperature sensors of a gas turbine.

Markov decision processes (MDPs) have developed as a standard for representing uncertainty in decision-theoretic planning. However, MDPs require an explicit representation of the state space and the probabilistic transition model which, in continuous or hybrid continuous-discrete domains, are not always easy to define. Even when this representation is available, the size of the state space and the number of state variables to consider in the transition function may be such that the resulting MDP cannot be solved using traditional techniques. In this paper a reward-based abstraction for solving hybrid MDPs is presented. In the proposed method, we gather information about the rewards and the dynamics of the system by exploring the environment. This information is used to build a decision tree (C4.5) representing a small set of abstract states with equivalent rewards, and then is used to learn a probabilistic transition function using a Bayesian networks learning algorithm (K2). The system output is a problem specification ready for its solution with traditional dynamic programming algorithms. We have tested our abstract MDP model approximation in real-world problem domains. We present the results in terms of the models learned and their solutions for different configurations showing that our approach produces fast solutions with satisfying policies.

Learning and making decisions in a complex uncertain multiagent environment like RoboCup Soccer Simulation 3D is a non-trivial task. In this paper, a probabilistic approach to handle such uncertainty in RoboCup 3D is proposed, specifically a Naive Bayes classifier. Although its conditional independence assumption is not always accomplished, it has proved to be successful in a whole range of applications. Typically, the Naive Bayes model assumes discrete attributes, but in RoboCup 3D the attributes are continuous. In literature, Naive Bayes has been adapted to handle continuous attributes mainly using Gaussian distributions or discretizing the domain, both of which present certain disadvantages. In the former, the probability density of attributes is not always well-fitted by a normal distribution. In the latter, there can be loss of information. Instead of discretizing, the use of a Fuzzy Naive Bayes classifier is proposed in which attributes do not take a single value, but a set of values with a certain membership degree. Gaussian and Fuzzy Naive Bayes classifiers are implemented for the pass evaluation skill of 3D agents. The classifiers are trained with different number of training examples and different number of attributes. Each generated classifier is tested in a scenario with three teammates and four opponents. Additionally, Gaussian and Fuzzy approaches are compared versus a random pass selector. Finally, it is shown that the Fuzzy Naive Bayes approach offers very promising results in the RoboCup 3D domain.

This paper presents the preliminary results of the Student Model based on beliefs of Self-Efficacy aiming to improve the effectiveness of Intelligent Tutoring Systems. The Self-efficacy construct means the student’s belief on his own capacity of performing a task. This belief affects his behavior, motivation, affectivity and the choices he makes. We design an e-Learning System, called InteliWeb, this environment is composed by the Self-Efficacy Mediator Agent and offers instruction material on Biological sciences. We use fuzzy theory for dealing with uncertainty in the assessment of the students and the incomplete knowledge about his Self-Efficacy.

A bifurcation occurs in a dynamic system when the structure of the system itself and therefore also its qualitative behavior change as a result of changes in one of the system’s parameters. In most cases, an infinitesimal change in one of the parameters make the dynamic system exhibit dramatic changes. In this paper, we present a framework (QRBD) for performing qualitative analysis of dynamic systems exhibiting bifurcations. QRBD performs a simulation of the system with bifurcations, in the presence of perturbations, producing accounts for all events in the system, given a qualitative description of the changes it undergoes. In such a sequence of events, we include catastrophic changes due to perturbations and bifurcations, and hysteresis. QRBD currently works with first-order systems with only one varying parameter. We propose the qualitative representations and algorithm that enable us to reason about the changes a dynamic system undergoes when exhibiting bifurcations, in the presence of perturbations.

In this paper, to conquer the scalability issue of evolvable hardware (EHW), we introduce a novel system-decomposition-strategy which realizes training set partition in the intrinsic evolution of a non-truth table based 32 characters classification system. The new method is expected to improve the convergence speed of the proposed evolvable system by compressing fitness value evaluation period which is often the most time-consuming part in an evolutionary algorithm (EA) run and reducing computational complexity of EA. By evolving target characters classification system in a complete FPGA-based experiment platform, this research investigates the influence of introducing partitioning training set technique to non-truth table based circuit evolution. The experimental results conclude that it is possible to evolve characters classification systems larger and faster than those evolved earlier, by employing our proposed scheme.

We propose a new perspective for solving systems of nonlinear equations by viewing them as a multiobjective optimization problem where every equation represents an objective function whose goal is to minimize the difference between the right- and left-hand side of the corresponding equation of the system. An evolutionary computation technique is suggested to solve the problem obtained by transforming the system into a multiobjective optimization problem. Results obtained are compared with some of the well-established techniques used for solving nonlinear equation systems.

This paper presents a new multi-objective evolutionary algorithm which consists of a hybrid between a particle swarm optimization (PSO) approach and scatter search. The main idea of the approach is to combine the high convergence rate of the particle swarm optimization algorithm with a local search approach based on scatter search. We propose a new leader selection scheme for PSO, which aims to accelerate convergence. Upon applying PSO, scatter search acts as a local search scheme, improving the spread of the nondominated solutions found so far. Thus, the hybrid constitutes an efficient multi-objective evolutionary algorithm, which can produce reasonably good approximations of the Pareto fronts of multi-objective problems of high dimensionality, while only performing 4,000 fitness function evaluations. Our proposed approach is validated using ten standard test functions commonly adopted in the specialized literature. Our results are compared with respect to a multi-objective evolutionary algorithm that is representative of the state-of-the-art in the area: the NSGA-II.

This work addresses an important problem in Feedforward Neural Networks (FNN) training, i.e. finding the pseudo-global minimum of the cost function, assuring good generalization properties to the trained architecture. Firstly, pseudo-global optimization is achieved by employing a combined parametric updating algorithm which is supported by the transformation of network parameters into interval numbers. It solves the network weight initialization problem, performing an exhaustive search for minimums by means of Interval Arithmetic (IA). Then, the global minimum is obtained once the search has been limited to the region of convergence (ROC). IA allows representing variables and parameters as compact-closed sets, then, a training procedure using interval weights can be done. The methodology developed is exemplified by an approximation of a known non-linear function in last section.

A gradient-based algorithm for ensemble weights modification is presented and applied on the regression tasks. Simulation results show that this method can produce an estimator ensemble with better generalization than those of bagging and single neural network. The method can not only have a similar function to GASEN of selecting many subnets from all trained networks, but also be of better performance than GASEN, bagging and best individual of regressive estimators.

Since the convergence of neural networks depends on learning rates, the learning rates of training algorithm for neural networks are very important factors. Therefore, we propose the Adaptive Learning Rates(ALRs) of Extended Kalman Filter(EKF) based training algorithm for wavelet neural networks(WNNs). The ALRs of the EFK based training algorithm produce the convergence of the WNN. Also we derive the convergence analysis of the learning process from the discrete Lyapunov stability theorem. Several simulation results show that the EKF based WNN with ALRs adapt to abrupt change and high nonlinearity with satisfactory performance.

In this study, we propose a multistage neural network metalearning technique for financial time series predication. First of all, an interval sampling technique is used to generate different training subsets. Based on the different training subsets, the different neural network models with different training subsets are then trained to formulate different base models. Subsequently, to improve the efficiency of metalearning, the principal component analysis (PCA) technique is used as a pruning tool to generate an optimal set of base models. Finally, a neural-network-based metamodel can be produced by learning from the selected base models. For illustration, the proposed metalearning technique is applied to foreign exchange rate predication.

The topology of a neural network has a significant importance on the network’s performance. Although this is well known, finding optimal configurations is still an open problem. This paper proposes a solution to this problem for Radial Basis Function (RBF) networks and General Regression Neural Network (GRNN) which is a kind of radial basis networks. In such networks, placement of centers has significant effect on the performance of network. The centers and widths of the hidden layer neuron basis functions are coded in a chromosome and these two critical parameters are determined by the optimization using genetic algorithms. Thyroid, iris and escherichia coli bacteria datasets are used to test the algorithm proposed in this study. The most important advantage of this algorithm is getting succesful results by using only a small part of a benchmark. Some numerical solution results indicate the applicability of the proposed approach.

Most models of Bidirectional Associative Memories intend to achieve that all trained patterns correspond to stable states; however, this has not been possible. Also, none of the former models has been able to recall all the trained patterns. A new model which appeared recently, called Alpha-Beta Bidirectional Associative Memory (BAM), recalls 100% of the trained patterns, without error. Also, the model is non iterative and has no stability problems. In this work the analysis of time and space complexity of the Alpha-Beta BAM is presented.

Hebbian hetero-associative learning is inherently asymmetric. Storing a forward association from pattern

A

to pattern

B

enables the recalling of pattern

B

given pattern

A

. This, in general, does not allow the recalling of pattern

A

given pattern

B

. The forward association between

A

and

B

will tend to be stronger than the backward association between

B

and

A

. In this paper it is described how the dynamical associative model proposed in [10] can be extended to create a bi-directional associative memory where forward association between

A

and

B

is equal to backward association between

B

and

A

. This implies that storing a forward association, from pattern

A

to pattern

B

, would enable the recalling of pattern

B

given pattern

A

and the recalling of pattern

A

given pattern

B

. We give some formal results that support the functioning of the proposal, and provide some examples were the proposal finds application.

This article analyzes the performance of Ant Colony Optimization algorithms on the resolution of Crew Pairing Problem, one of the most critical processes in airline management operations. Furthermore, we explore the hybridization of Ant algorithms with Constraint Programming techniques. We show that, for the instances tested from Beasley’s OR-Library, the use of this kind of hybrid algorithms obtains good results compared to the best performing metaheuristics in the literature.

This paper introduces a refined evaluation function, called Φ, for the Minimum Linear Arrangement problem (MinLA). Compared with the classical evaluation function (

LA

), Φ integrates additional information contained in an arrangement to distinguish arrangements with the same

LA

value. The main characteristics of Φ are analyzed and its practical usefulness is assessed within both a Steepest Descent (SD) algorithm and a Memetic Algorithm (MA). Experiments show that the use of Φ allows to boost the performance of SD and MA, leading to the improvement on some previous best known solutions.

Many problems in AI can be stated as search problems and most of them are very complex to solve. One alternative for these problems are local search methods that have been widely used for tackling difficult optimization problems for which we do not know algorithms which can solve every instance to optimality in a reasonable amount of time. One of the most popular methods is what is known as iterated local search (ILS), which samples the set of local optima searching for a better solution. This algorithm’s behavior is achieved by some mechanisms like perturbation which is a key aspect to consider, since it allows the algorithm to reach a new solution from the set of local optima by escaping from the previous local optimum basis of attraction. In order to design a good perturbation method we need to analyze the local optima structure such that ILS leads to a good biased sampling. In this paper, the local optima structure of the Quadratic Assignment Problem, an NP-hard optimization problem, is used to determine the required perturbation size in the ILS algorithm. The analysis is focused on verifying if the set of local optima has the “Big Valley (BV)” structure, and on how close local optima are in relation to problem size. Experimental results show that a small perturbation seems appropriate for instances having the BV structure, and for instances having a low distance among local optima, even if they do not have a clear BV structure. Finally, as the local optima structure moves away from BV a larger perturbation is needed.

A supply chain distribution network design model is developed in this paper. The goal of the model is to select the optimum numbers, locations and capacity levels of plants and warehouses to deliver the products to the retailers at the least cost while satisfying the desired service level. Maximal covering approach is employed in statement of the service level. Different from the previous researches in this area, coverage functions which differ among the retailers according to their service standard requests are defined for the retailers. Additionally, to provide a more realistic model structure, decision maker’s imprecise aspiration levels for the goals, and demand uncertainties are incorporated into the model through fuzzy modeling approach. Realistic computational experiments are provided to confirm the viability of the model.

In this paper, we simultaneously address the route selection and rate allocation problem in multirate multicast networks. We propose the evolutionary computation algorithm based on a genetic algorithm for this problem and elaborate upon many of the elements in order to improve solution quality and computational efficiency in applying the proposed methods to the problem. These include: the genetic representation, evaluation function, genetic operators and procedure. Additionally, a new method using an artificial intelligent search technique, called the coevolutionary algorithm, is proposed to achieve better solutions. The results of extensive computational simulations show that the proposed algorithms provide high quality solutions and outperform existing approach.

We solve a single-robot

m

-machine cyclic scheduling problem arising in flexible manufacturing systems served by computer-controlled robots. The problem is to find the minimum cycle time for the so-called 2-cyclic (or “2-degree”) schedules, in which exactly two parts enter and two parts leave the production line during each cycle. An earlier known polynomial time algorithm for this problem was applicable only to the Euclidean case, where the transportation times must satisfy the “triangle inequality”. In this paper we study a general non-Euclidean case. Applying a geometrical approach, we construct a polynomial time algorithm of complexity O(

m

5

log

m

).

This paper presents a new algorithm that obtains an approximation of the Critical Path in schedules generated using the disjunctive graph model that represents the Job Shop Scheduling Problem (JSSP). This algorithm selects a set of operations in the JSSP, where on the average ninety nine percent of the total operations that belong to the set are part of the critical path. A comparison is made of cost and performance between the proposed algorithm, CPA (Critical Path Approximation), and the classic algorithm, CPM (Critical Path Method). With the obtained results, it is demonstrated that the proposed algorithm is very efficient and effective at generating neighborhoods in the simulated annealing algorithm for the JSSP.

Quay cranes are the most important equipment in port container terminals, because they are directly related to the wharf productivity. This study proposes a heuristic search algorithm, called greedy randomized adaptive search procedure (GRASP), for constructing a schedule of quay cranes in a way of minimizing the makespan and considering interference among yard cranes. The performance of the heuristic algorithm was tested by a numerical experiment.

The Job Shop Scheduling Problem with Sequence Dependent Setup Times (

SDJSS

) is an extension of the Job Shop Scheduling Problem (

JSS

) that has interested to researchers during the last years. In this paper we confront the

SDJSS

problem by means of a memetic algorithm. We study two schedule generation schemas that are extensions of the well known

G

&

T

algorithm for the

JSS

. We report results from an experimental study showing that the proposed approaches produce similar results and that both of them are more efficient than other genetic algorithm proposed in the literature.

Lot output time prediction is a critical task to a wafer fab (fabrication plant). Traditional studies are focused on prediction accuracy and efficiency. Another performance measure that is as important but has been ignored in traditional studies is the achievability of an output time forecast, which is defined as the possibility that the fabrication on a wafer lot can be finished in time before the output time forecast. Theoretically, if a probability distribution can be obtained for the output time forecast, then the achievability can be evaluated with the cumulative probability of the probability distribution before the given date. However, there are many managerial actions that are more influential to the achievability. For this reason, a fuzzy set approach is proposed for evaluating the achievability of the output time forecast. The fuzzy set approach is composed of two parts: a fuzzy back propagation network (FBPN) and a set of fuzzy inference rules (FIRs). An example is used to demonstrate the applicability of the proposed methodology.

The Bayesian Information Criterion (BIC) and the Minimum Description Length Principle (MDL) have been widely proposed as good metrics for model selection. Such scores basically include two terms: one for accuracy and the other for complexity. Their philosophy is to find a model that rightly balances these terms. However, it is surprising that both metrics do often not work very well in practice for they overfit the data. In this paper, we present an analysis of the BIC and MDL scores using the framework of Bayesian networks that supports such a claim. To this end, we carry out different tests that include the recovery of gold-standard network structures as well as the construction and evaluation of Bayesian network classifiers. Finally, based on these results, we discuss the disadvantages of both metrics and propose some future work to examine these limitations more deeply.

The method of Grey prediction and Markov Chain prediction could be used for the prediction in time order. Their combination could be extensively applied in forecasting. In this paper, we studied the precisions of Grey-Markov forecasting model based on the original data of the silkworm cocoon yield in China from 1950 to 1999. The precisions of Grey-Markov forecasting model from 2000 to 2003 are 95.56%, 95.17% and 94.40% respectively, which are higher than GM (1,1), and next to the Exponential Smoothing method and linear regression. The paper provided a scientific basis for the planned development of sericulture in China.

Condition monitoring and classification of machinery health state is of great practical significance in manufacturing industry, because it provides updated information regarding machine status on-line, thus avoiding the production loss and minimizing the chances of catastrophic machine failures. This is a pattern recognition problem and a condition monitoring system based on a hybrid of neural network and hidden Markov model (HMM) is proposed in this paper. Neural network realizes dimensionality reduction for Lipschitz exponent functions obtained from vibration data as input features and hidden Markov model is used for condition classification. The machinery condition can be identified by selecting the corresponding HMM which maximizes the probability of a given observation sequence. In the end, the proposed method is validated using gearbox vibration data.

Feature selection has become a relevant and challenging problem for the area of knowledge discovery in database. An effective feature selection strategy can significantly reduce the data mining processing time, improve the predicted accuracy, and help to understand the induced models, as they tend to be smaller and make more sense to the user. In this paper, an effective research around the utilization of the Perceptron paradigm as a method for feature selection is carried out. The idea is training a Perceptron and then utilizing the interconnection weights as indicators of which attributes could be the most relevant. We assume that an interconnection weight close to zero indicates that the associated attribute to this weight can be eliminated because it does not contribute with relevant information in the construction of the class separator hyper-plane. The experiments were realized with 4 real and 11 synthetic databases. The results show that the proposed algorithm is a good trade-off among performance (generalization accuracy), efficiency (processing time) and feature reduction. Specifically, we apply the algorithm to a Mexican Electrical Billing database with satisfactory accuracy, efficiency and feature reduction results.

The performance of learning tasks is very sensitive to the characteristics of training data. There are several ways to increase the effect of learning performance including standardization, normalization, signal enhancement, linear or non-linear space embedding methods, etc. Among those methods, determining the relevant and informative features is one of the key steps in the data analysis process that helps to improve the performance, reduce the generation of data, and understand the characteristics of data. Researchers have developed the various methods to extract the set of relevant features but no one method prevails. Random Forest, which is an ensemble classifier based on the set of tree classifiers, turns out good classification performance. Taking advantage of Random Forest and using wrapper approach first introduced by Kohavi

et al

, we propose a new algorithm to find the optimal subset of features. The Random Forest is used to obtain the feature ranking values. And these values are applied to decide which features are eliminated in the each iteration of the algorithm. We conducted experiments with two public datasets: colon cancer and leukemia cancer. The experimental results of the real world data showed that the proposed method results in a higher prediction rate than a baseline method for certain data sets and also shows comparable and sometimes better performance than the feature selection methods widely used.

Selecting a set of features which is optimal for a given task is a problem which plays an important role in a wide variety of contexts including pattern recognition, adaptive control, and machine learning. Recently, exploiting fractal dimension to reduce the features of dataset is a novel method. FDR (Fractal Dimensionality Reduction), proposed by Traina in 2000, is the most famous fractal dimension based feature selection algorithm. However, it is intractable in the high dimensional data space for multiple scanning the dataset and incapable of eliminating two or more features simultaneously. In this paper we combine GA with the Z-ordering based FDR for addressing this problem and present a new algorithm GAZBFDR(Genetic Algorithm and Z-ordering Based FDR). The algorithm proposed can directly select the fixed number features from the feature space and utilize the fractal dimension variation to evaluate the selected features within the comparative lower space. The experimental results show that GAZBFDR algorithm achieves better performance in the high dimensional dataset.

Popular nonlinear dimensionality reduction algorithms, e.g., SIE and Isomap suffer a difficulty in common: global neighborhood parameters often fail in tackling data sets with high variation in local manifold. To improve the availability of nonlinear dimensionality reduction algorithms in the field of machine learning, an adaptive neighbors selection scheme based on locally principal direction reconstruction is proposed in this paper. Our method involves two main computation steps. First, it selects an appropriate neighbors set for each data points such that all neighbors in a neighbors set form a d-dimensional linear subspace approximately and computes locally principal directions for each neighbors set respectively. Secondly, it fits each neighbor by means of locally principal directions of corresponding neighbors set and deletes the neighbors whose fitting error exceeds a predefined threshold. The simulation shows that our proposal could deal with data set with high variation in local manifold effectively. Moreover, comparing with other adaptive neighbors selection strategy, our method could circumvent false connectivity induced by noise or high local curvature.

At first, support vector machines (SVMs) were applied to solve binary classification problems. They can also be extended to solve multicategory problems by the combination of binary SVM classifiers. In this paper, we propose a new fuzzy model that includes the advantages of several previously published methods solving their drawbacks. For each datum, a class is rejected using information provided by every decision function related to it. Our proposal yields membership degrees in the unit interval and in some cases, it improves the performance of the former methods in the unclassified regions.

Support vector machine (SVM) has been successfully applied to solve a large number of classification problems. Despite its good theoretic foundations and good capability of generalization, it is a big challenging task for the large data sets due to the training complexity, high memory requirements and slow convergence. In this paper, we present a new method,

SVM classification based on fuzzy clustering

. Before applying SVM we use fuzzy clustering, in this stage the optimal number of clusters are not needed in order to have less computational cost. We only need to partition the training data set briefly. The SVM classification is realized with the center of the groups. Then the de-clustering and SVM classification via reduced data are used. The proposed approach is scalable to large data sets with high classification accuracy and fast convergence speed. Empirical studies show that the proposed approach achieves good performance for large data sets.

The problem of determining optimal decision model is a difficult combinatorial task in the fields of pattern classification, machine learning, and especially bioinformatics. Recently, support vector machine (SVM) has shown a better performance than conventional learning methods in many applications. This paper proposes a weighted kernel function for support vector machine and its learning method with a fast convergence and a good classification performance. We defined the weighted kernel function as the weighted sum of a set of different types of basis kernel functions such as neural, radial, and polynomial kernels, which are trained by a learning method based on genetic algorithm. The weights of basis kernel functions in proposed kernel are determined in learning phase and used as the parameters in the decision model in classification phase. The experiments on several clinical datasets such as colon cancer, leukemia cancer, and lung cancer datasets indicate that our weighted kernel function results in higher and more stable classification performance than other kernel functions. Our method also has comparable and sometimes better classification performance than other classification methods for certain applications.

Ensemble learning schemes have shown impressive increases in prediction accuracy over single model schemes. We introduce a new decision forest learning scheme, whose base learners are Minimum Message Length (MML) oblique decision trees. Unlike other tree inference algorithms, MML oblique decision tree learning does not over-grow the inferred trees. The resultant trees thus tend to be shallow and do not require pruning. MML decision trees are known to be resistant to over-fitting and excellent at probabilistic predictions. A novel weighted averaging scheme is also proposed which takes advantage of high probabilistic prediction accuracy produced by MML oblique decision trees. The experimental results show that the new weighted averaging offers solid improvement over other averaging schemes, such as majority vote. Our MML decision forests scheme also returns favourable results compared to other ensemble learning algorithms on data sets with binary classes.

It is known that in decision trees the reliability of lower branches is worse than the upper branches due to data fragmentation problem. As a result, unnecessary tests of attributes may be done, because decision trees may require tests that are not best for some part of the data objects. To supplement the weak point of decision trees of data fragmentation, using reliable short rules with decision tree is suggested, where the short rules come from limited application of association rule finding algorithms. Experiment shows the method can not only generate more reliable decisions but also save test costs by using the short rules.

This paper presents a method based on chemometrics analysis to select the optimal wavebands for variety discrimination of Chinese cabbage seed by using a Visible/Near-infrared spectroscopy (Vis/NIRS) system. A total of 120 seed samples were investigated using a field spectroradiometer. Chemometrics was used to build the relationship between the absorbance spectra and varieties. Principle component analysis (PCA) was not suitable for variety discrimination as the principle components (PCs) plot of three primary principle components could only intuitively distinguish the varieties well. Partial Least Squares Regression (PLS) was executed to select 6 optimal wavebands as 730nm, 420nm, 675nm, 620nm, 604nm and 609nm based on loading values. Two chemometrics, multiple linear regression (MLR) and stepwise discrimination analysis (SDA) were used to establish the recognition models. MLR model is not suitable in this study because of its unsatisfied predictive ability. The SDA model was proposed by the advantage of variable selection. The final results based on SDA model showed an excellent performance with high discrimination rate of 99.167%. It is also proved that optimal wavebands are suitable for variety discrimination.

This paper focuses on the study of a new method for detecting masqueraders in computer systems. The main feature of such masqueraders is that they have knowledge about the behavior profile of legitimate users. The dataset provided by Schonlau

et al.

[1], called SEA, has been modified for including synthetic sessions created by masqueraders using the behavior profile of the users intended to impersonate. It is proposed an hybrid method for detection of masqueraders based on the compression of the users sessions and Hidden Markov Models. The performance of the proposed method is evaluated using ROC curves and compared against other known methods. As shown by our experimental results, the proposed detection mechanism is the best of the methods here considered.

In this paper, we present a lightweight detection and visualization methodology for Denial of Service (DoS) attacks. First, we propose a new approach based on Random Forest (RF) to detect DoS attacks. The classification accuracy of RF is comparable to that of Support Vector Machines (SVM). RF is also able to produce the importance value of individual feature. We adopt RF to select intrinsic important features for detecting DoS attacks in a lightweight way. And then, with selected features, we plot both DoS attacks and normal traffics in 2 dimensional space using Multi-Dimensional Scaling (MDS). The visualization results show that simple MDS can help one to visualize DoS attacks without any expert domain knowledge. The experimental results on the KDD 1999 intrusion detection dataset validate the possibility of our approach.

Seeds based semi-supervised clustering algorithms often utilize a seeds set consisting of a small amount of labeled data to initialize cluster centroids, hence improve the performance of clustering over whole data set. Researches indicate that both the scale and quality of seeds set greatly restrict the performance of semi-supervised clustering. A novel semi-supervised clustering algorithm named DE-Tri-training semi-supervised K means is proposed. In new algorithm, prior to initializing cluster centroids, the training process of a semi-supervised classification approach named Tri-training is used to label the unlabeled data and add them into initial seeds to enlarge the scale. Meanwhile, to improve the quality of enlarged seeds set, a Nearest Neighbor Rule based data editing technique named Depuration is introduced into the Tri-training process to eliminate and correct the noise and mislabeled data among the enlarged seeds. Experiments show that novel algorithm can effectively improve the initialization of cluster centroids and enhance clustering performance.

The implicit knowledge in the databases can be extracted of automatic form. One of the several approaches considered for this problem is the construction of graphical models that represent the relations between the variables and regularities in the data. In this work the problem is addressed by means of an algorithm of search and scoring. These kind of algorithms use a heuristic mechanism search and a function of score to guide themselves towards the best possible solution.

The algorithm, which is implemented in the semifunctional language Lisp, is a searching mechanism of the structure of a bayesian network (BN) based on concurrent processes.

Each process is assigned to a node of the BN and effects one of three possible operations between its node and some of the rest: to put, to take away or to invert an edge. The structure is constructed using the metric MDL (made up of three terms), whose calculation is made of distributed way, in this form the search is guided by selecting those operations between the nodes that minimize the MDL of the network.

In this work are presented some results of the algorithm in terms of comparison of the structure of the obtained network with respect to its gold network.

This paper presents a method of collaborative design optimization based on knowledge discovery. Firstly, a knowledge discovery approach based on simulation data is presented. Rules are extracted by knowledge discovery algorithm, and each rule is divided into several intervals. Secondly, a collaborative optimization model is established. In the model, the consistency intervals are derived from intervals of knowledge discovery. The model is resolved by genetic arithmetic. Finally, The method is demonstrated by a parameter design problem of piston-connecting mechanism of automotive engine. The proposed method can improve the robustness of collaborative design optimization.

In telecommunication networks, alarms are usually useful for identifying faults, and therefore solving them. However, for large systems the number of alarms produced is so large that the current management systems are overloaded. One way of overcoming this problem is to filter and reduce the number of alarms before the faults can be located. In this paper, we describe a new approach for fault recognition and classification in telecommunication networks. We study and evaluate its performance using real-world data collected from 3G telecommunication networks.

This paper introduces MineSP, a relational-like operator to mine sequential patterns from databases. It also shows how an inductive query can be translated into a traditional query tree augmented with MineSP nodes. This query tree is then optimized, choosing the mining algorithm that best suits the constraints specified by the user and the execution environment conditions. The SPMiner prototype system supporting our approach is also presented.

Beijing has deployed Intelligent Transportation System (ITS) monitoring devices along selected major roads in the core urban area in order to help relieve traffic congestion and improve traffic conditions. The huge amount of traffic data from ITS originally collected for the control of traffic signals can be a useful source to assist in transportation designing, planning, managing, and research by identifying major traffic patterns from the ITS data. The importance of data visualization as one of the useful data mining methods for reflecting the potential patterns of large sets of data has long been recognized in many disciplines. This paper will discuss several comprehensible and appropriate data visualization techniques, including line chart, bi-directional bar chart, rose diagram, and data image, as exploratory data analysis tools to explore traffic volume data intuitively and to discover the implicit and valuable traffic patterns. These methods could be applied at the same time to gain better and more comprehensive insights of traffic patterns and data relationships hidden in the massive data set. The visual exploratory analysis results could help transportation managers, engineers, and planners make more efficient and effective decisions on the design of traffic operation strategies and future transportation planning scientifically.

Robot Soccer is a challenging research domain for Artificial Intelligence, which was proposed in order to provide a long-term problem in which researchers can investigate the construction of systems involving multiple agents working together in a dynamic, uncertain and probabilistic environment, to achieve a specific goal. This work focuses on the design and implementation of a fast and robust computer vision system for a team of small size robot soccer players. The proposed system combines artificial intelligence and computer vision techniques to locate the mobile robots and the ball, based on global vision images. To increase system performance, this work proposes a new approach to interpret the space created by a well-known computer vision technique called Hough Transform, as well as a fast object recognition method based on constraint satisfaction techniques. The system was implemented entirely in software using an off-the-shelf frame grabber. Experiments using real time image capture allows to conclude that the implemented system are efficient and robust to noises and lighting variation, being capable of locating all objects in each frame, computing their position and orientation in less than 20 milliseconds.

In mobile robotics, the inference of the 3D layout of large-scale indoor environments is a critical problem for achieving exploration and navigation tasks. This article presents a framework for building a 3D model of an indoor environment from partial data using a mobile robot. The modeling of a large-scale environment involves the acquisition of a huge amount of range data to extract the geometry of the scene. This task is physically demanding and time consuming for many real systems. Our approach overcomes this problem by allowing a robot to rapidly collect a set of intensity images and a small amount of range information. The method integrates and analyzes the statistical relationships between the visual data and the limited available depth on terms of small patches and is capable of recovering complete dense range maps. Experiments on real-world data are given to illustrate the suitability of our approach.

In this paper, an effective method is proposed for automatic facial expression recognition from static images. First, a modified Active Appearance Model (AAM) is used to locate facial feature points automatically. Then, based on this, facial feature vector is formed. Finally, SVM classifier with a sample selection method is adopted for expression classification. Experimental results on the JAFFE database demonstrate an average recognition rate of 69.9% for novel expressers, showing that the proposed method is promising.

In this paper, a new feature extraction called principal component net analysis (PCNA) is developed for face recognition. It looks a face image upon as two orthogonal modes: row channel and column channel and extracts Principal Components (PCs) for each channel. Because it does not need to transform an image into a vector beforehand, much more spacial discrimination information is reserved than traditional PCA, ICA etc. At the same time, because the two channels have different physical meaning, its extracted PCs can be understood easier than 2DPCA. Series of experiments were performed to test its performance on three main face image databases: JAFFE, ORL and FERET. The recognition rate of PCNA was the highest (PCNA, PCA and 2DPCA) in all experiments.

In this paper, we propose an

Advanced Soft Remote Control System

so as to endow the users with the ability to control various home appliances instead of individual remote controller for each appliance and to command naturally at various places without being conscious of the view direction of the cameras. Through the developed system, the user first selects the device that he/her wants to control by pointing it with his/her hand. Then, the user can command operation of the desired functions via 10 predefined basic hand motion commands. By the experiment, we can get 97.1% recognition rate during offline test and 96.5% recognition rate during online test. The developed system complements some inconveniences of conventional remote controllers specially by giving additional freedom to persons with movement deficits and people without disabilities.

In this paper, we propose an interacting multiple model (IMM) method using intelligent tracking filter with fuzzy gain to reduce tracking error for maneuvering target. In the proposed filter, the unknown acceleration input for each sub-model is determined by mismatches between the modelled target dynamics and the actual target dynamics. After an acceleration input is detected, the state estimate for each sub-model is modified. To modify the accurate estimation, we propose the fuzzy gain based on the relation between the filter residual and its variation. To optimize each fuzzy system, we utilize the genetic algorithm (GA). Finally, the tracking performance of the proposed method is compared with those of the input estimation(IE) method and AIMM method through computer simulations.

This paper describes a complete FPGA implemented intrinsic evolvable system which is employed as a novel approach to automatic design of spatial image filters for two given types of noise. The genotype-phenotype representation of the proposed evolvable system is inspired by the Cartesian Genetic Programming and the function level evolution. The innovative feature of the proposed system is that the whole evolvable system which consists of evolutionary algorithm unit, fitness value calculation unit and reconfigurable function elements array is realized in a same FPGA. A commercial and current FPGA card: Celoxica RC1000 PCI board with a Xilinx Virtex xcv2000E FPGA is employed as our hardware platform. The main motive of our research is to design a general, simple and fast virtual reconfigurable hardware platform with powerful computation ability to achieve intrinsic evolution. The experiment results show that a spatial image filter can be evolved in less than 71 seconds.

We present an algorithm for automatic selection of features that best segment an image in texture homogeneous regions. The set of “best extractors” are automatically selected among the Gabor filters, Co-occurrence matrix, Law’s energies and intensity response. Noise-features elimination is performed by taking into account the magnitude and the granularity of each feature image, i.e. the compute image when a specific feature extractor is applied. Redundant features are merged by means of probabilistic rules that measure the similarity between a pair of image feature. Then, cascade applications of general purpose image segmentation algorithms (K-Means, Graph-Cut and EC-GMMF) are used for computing the final segmented image. Additionally, we propose an evolutive gradient descent scheme for training the method parameters for a benchmark image set. We demonstrate by experimental comparisons, with stat of the art methods, a superior performance of our technique.

This paper presents a hybrid segmentation algorithm, which provides a synthetic image description in terms of regions. This method has been used to segment images of outdoor scenes. We have applied our segmentation algorithm to color images and images encoding 3D information. 5 different color spaces were tested. The segmentation results obtained with each color space are compared.

This paper presents a novel method that uses incremental self-organizing map (ISOM) network and wavelet transform together for the segmentation of magnetic resonance (MR), computer tomography (CT) and ultrasound (US) images. In order to show the validity of the proposed scheme, ISOM has been compared with Kohonen’s SOM. Two-dimensional continuous wavelet transform (2D-CWT) is used to form the feature vectors of medical images. According to the selected two feature extraction methods, features are formed by the intensity of the pixel of interest or mean value of intensities at one neighborhood of the pixel at each sub-band. The first feature extraction method is used for MR and CT head images. The second method is used for US prostate image.

Iris recognition is a method used to identify people based on the analysis of the eye iris. A typical iris recognition system is composed of four phases: (1) image acquisition and preprocessing, (2) iris localization and extraction, (3) iris features characterization, and (4) comparison and matching. A novel contribution in the step of characterization of iris features is introduced by using a Hammersley’s sampling algorithm and accumulated histograms. Histograms are computed with data coming from sampled sub-images of iris. The optimal number and dimensions of samples is obtained by the simulated annealing algorithm. For the last step, couples of accumulated histograms iris samples are compared and a decision of acceptance is taken based on an experimental threshold. We tested our ideas with UBIRIS database; for clean eye iris databases we got excellent results.

We tackle the problem of retrieving images from a database. In particular we are concerned with the problem of retrieving images of airplanes belonging to one of the following six categories: 1) commercial planes on land, 2) commercial planes in the air, 3) war planes on land, 4) war planes in the air, 5) small aircrafts on land, and 6) small aircrafts in the air. During training, a wavelet-based description of each image is first obtained using Daubechies 4-wavelet transformation. The resulting coefficients are then used to train a neural network. During classification, test images are presented to the trained system. The coefficients are obtained from the Daubechies transform from histograms of a decomposition of the image into square sub-images of each channel of the original image. 120 images were used for training and 240 for independent testing. An 88% correct identification rate was obtained.

From the engineering aspect, the research on Kansei information is a field aimed at processing and understanding how human intelligence processes subjective information or ambiguous sensibility and how such information can be executed by a computer. Our study presents a method of image processing aimed at accurate image retrieval based on human Kansei. We created the Kansei-Vocabulary Scale by associating Kansei of high-level information with shapes among low-level features of an image and constructed the object retrieval system using Kansei-Vocabulary Scale. In the experimental process, we put forward an adaptive method of measuring similarity that is appropriate for Kansei-based image retrieval. We call it “adaptive-Tangent Space Representation (adaptive-TSR)”. The method is based on the improvement of the TSR in 2-dimensional space for Kansei-based retrieval. We then it define an adaptive similarity algorithm and apply to the Kansei-based image retrieval. As a result, we could get more promising results than the existing method in terms of human Kansei.

We consider statistical properties of prepositions—the most numerous and important functional words in European languages. Usually, they syntactically link verbs and nouns to nouns. It is shown that their rank distributions in Russian differ radically from those of content words, being much more compact. The Zipf law distribution commonly used for content words fails for them, and thus approximations flatter at first ranks and steeper at higher ranks are applicable. For these purposes, the Mandelbrot family and an expo-logarithmic family of distributions are tested, and an insignificant difference between the two least-square approximations is revealed. It is proved that the first dozen of ranks cover more than 80% of all preposition occurrences in the DB of Russian collocations of Verb-Preposition-Noun and Noun-Preposition-Noun types, thus hardly leaving room for the rest two hundreds of available Russian prepositions.

When training hidden-Markov-model-based part-of-speech (PoS) taggers involved in machine translation systems in an unsupervised manner the use of target-language information has proven to give better results than the standard Baum-Welch algorithm. The target-language-driven training algorithm proceeds by translating every possible PoS tag sequence resulting from the disambiguation of the words in each source-language text segment into the target language, and using a target-language model to estimate the likelihood of the translation of each possible disambiguation. The main disadvantage of this method is that the number of translations to perform grows exponentially with segment length, translation being the most time-consuming task. In this paper, we present a method that uses

a priori

knowledge obtained in an unsupervised manner to prune unlikely disambiguations in each text segment, so that the number of translations to be performed during training is reduced. The experimental results show that this new pruning method drastically reduces the amount of translations done during training (and, consequently, the time complexity of the algorithm) without degrading the tagging accuracy achieved.

Based on recent evaluation of word sense disambiguation (WSD) systems [10], disambiguation methods have reached a standstill. In [10] we showed that it is possible to predict the best system for target word using word features and that using this ’optimal ensembling method’ more accurate WSD ensembles can be built (3-5% over Senseval state of the art systems with the same amount of possible potential remaining). In the interest of developing if more accurate ensembles, w e here define the strong regions for three popular and effective classifiers used for WSD task (Naive Bayes – NB, Support Vector Machine – SVM, Decision Rules – D) using word features (word grain, amount of positive and negative training examples, dominant sense ratio). We also discuss the effect of remaining factors (feature-based).

Word sense disambiguation (WSD) is an important intermediate stage for many natural language processing applications. The senses of an ambiguous word are the classification of usages for that word. WSD is basically a mapping function from a context to a set of applicable senses depending on various parameters. Resource selection, determination of senses for ambiguous words, decision of effective features, algorithms, and evaluation criteria are the major issues in a WSD system. This paper deals with the feature selection strategies for word sense disambiguation task in Turkish language. There are many different features that can contribute to the meaning of a word. These features can vary according to the metaphorical usages, POS of the word, pragmatics, etc. The observations indicated that detecting the critical features can contribute much than the learning methodologies.

In this paper, an approach to semantic disambiguation based on machine learning and semantic classes for Spanish is presented. A critical issue in a corpus-based approach for Word Sense Disambiguation (WSD) is the lack of wide-coverage resources to automatically learn the linguistic information. In particular, all-words sense annotated corpora such as SemCor do not have enough examples for many senses when used in a machine learning method. Using semantic classes instead of senses allows to collect a larger number of examples for each class while polysemy is reduced, improving the accuracy of semantic disambiguation. Cast3LB, a SemCor-like corpus, manually annotated with Spanish WordNet 1.5 senses, has been used in this paper to perform semantic disambiguation based on several sets of classes: lexicographer files of WordNet, WordNet Domains, and SUMO ontology.

This paper presents a machine-learning approach for the recognition of textual entailment. For our approach we model lexical and semantic features. We study the effect of stacking and voting joint classifier combination techniques which boost the final performance of the system. In an exhaustive experimental evaluation, the performance of the developed approach is measured. The obtained results demonstrate that an ensemble of classifiers achieves higher accuracy than an individual classifier and comparable results to already existing textual entailment systems.

The variability of semantic expression is a special characteristic of natural language. This variability is challenging for many natural language processing applications that try to infer the same meaning from different text variants. In order to treat this problem a generic task has been proposed: Textual Entailment Recognition. In this paper, we present a new Textual Entailment approach based on Latent Semantic Indexing (LSI) and the cosine measure. This proposed approach extracts semantic knowledge from different corpora and resources. Our main purpose is to study how the acquired information can be combined with an already developed and tested Machine Learning Entailment system (MLEnt). The experiments show that the combination of MLEnt, LSI and cosine measure improves the results of the initial approach.

This paper describes a machine learning approach to the identification of temporal clauses by disambiguating the subordinating conjunctions used to introduce them. Temporal clauses are regularly marked by subordinators, many of which are ambiguous, being able to introduce clauses of different semantic roles. The paper also describes our work on generating an annotated corpus of sentences embedding clauses introduced by ambiguous subordinators that might have temporal value. Each such clause is annotated as temporal or non-temporal by testing whether it answers the questions

when

,

how often

or

how long

with respect to the action of its superordinate clause. Using this corpus, we then train and evaluate personalised classifiers for each ambiguous subordinator, in order to set apart temporal usages. Several classifiers are evaluated, and the best performing ones achieve an average accuracy of 89.23% across the set of ambiguous connectives.

This paper deals with a domain-independent natural language interface to databases (NLIDB) for the Spanish language. This NLIDB had been previously tested for the Northwind and Pubs domains and had attained good performance (86% success rate). However, domain independence complicates the task of achieving high translation success, and to this end the ATIS (Air Travel Information System) database, which has been used by several natural language interfaces, was selected to conduct a new evaluation. The purpose of this evaluation was to asses the efficiency of the interface after the reconfiguration for another domain and to detect the problems that affect translation success. For the tests a corpus of queries was gathered and the results obtained showed that the interface can easily be reconfigured and that attained a 50% success rate. When the found problems concerning query translation were analyzed, wording deficiencies of some user queries and several errors in the synonym dictionary were discovered. After correcting these problems a second test was conducted, in which the interface attained a 61.4% success rate. These experiments showed that user training is necessary as well as a dialogue system that permits to clarify a query when it is deficiently formulated.

An efficient use of the web will imply the ability to find not only documents but also specific pieces of information according to user’s query. Right now, this last possibility is not tackled by current information extraction or question answering systems, since it requires both a deeper semantic understanding of queries and contents along with deductive capabilities. In this paper, the authors propose the use of Interlinguas as a plausible approach to search and extract specific pieces of information from a document, given the semantic nature of Interlinguas and their support for deduction. More concretely, the authors describe the UNL Interlinguas from the representational point of view and illustrate its deductive capabilities by means of an example.

The arm of this work is to provide a formal model and an effective way for information retrieving from a big related data set. Based upon fuzzy logic operation, a fuzzy mathematical model of 0-1 mixture programming is addressed. Meanwhile, a density function indicating the overall possessive status of the effective mined out data is introduced. Then, a soft computing (SC) approach which is a genetic algorithm (GA) embedded fuzzy deduction is presented. During the SC process, fuzzy logic decision is taken into the uses of determining the genes’ length, calculating fitness function and choosing feasible solution. Stimulated experiments and comparison tests show that the methods can match the user’s most desired information from magnanimity data exactly and efficiently. The approaches can be extended in practical application in solving general web mining problem.

In this paper we address the problem of matching musical renditions of the same piece of music also known as

performances

. We use an entropy based Audio-Fingerprint delivering a framed, small footprint AFP which reduces the problem to a string matching problem. The Entropy AFP has very low resolution (750 ms per symbol), making it suitable for flexible string matching.

We show experimental results using dynamic time warping (DTW), Levenshtein or

edit

distance and the Longest Common Subsequence (LCS) distance. We are able to correctly (100%) identify different renditions of masterpieces as well as pop music in less than a second per comparison.

The three approaches are 100% effective, but LCS and Levenshtein can be computed online, making them suitable for monitoring applications (unlike DTW), and since they are distances a metric index could be use to speed up the recognition process.

Topical web crawling technology is important for domain-specific resource discovery. Topical crawlers yield good recall as well as good precision by restricting themselves to a specific domain from web pages. There is an intuition that the text surrounding a link or the link-context on the HMTL page is a good summary of the target page. Motivated by that, This paper investigates some alternative methods and advocates that the link-context derived from reference page’s HTML tag tree can provide a wealth of illumination for steering crawler to stay on domain-specific topic. In order that crawler can acquire enough illumination from link-context, we initially look for some referring pages by traversing backward from seed URLs, and then build initial term-based feature set by parsing the link-contexts extracted from those reference web pages. Used to measure the similarity between the crawled pages’ link-context, the feature set can be adaptively trained by some link-contexts to relevant pages during crawling. This paper also presents some important metrics and an evaluation function for ranking URLs about pages relevance. A comprehensive experiment has been conducted, the result shows obviously that this approach outperforms Best-First and Breath-First algorithm both in harvest rate and efficiency.

We describe a music recommender model that uses intermediate agents to evaluate music composition according to their own rules respectively, and make recommendations to user. After user scoring recommended items, agents can adapt their selection rules to fit user tastes, even when user preferences undergo a rapid change. Depending on the number of users, the model can also be applied to such tasks as critiquing large numbers of music, image, or written compositions in a competitive contest with other judges. Several experiments are reported to test the model’s ability to adapt to rapidly changing conditions yet still make appropriate decisions and recommendations.

In this work, a data-driven approach for extracting answers from web-snippets is presented. Answers are identified by matching contextual distributional patterns of the expected answer type(EAT) and answer candidates. These distributional patterns are directly learnt from previously annotated tuples {

question, sentence, answer

}, and the learning mechanism is based on the principles language acquisition. Results shows that this linguistic motivated data-driven approach is encouraging.

Nowadays, there is an increasing interest in research on QA over restricted domains. Concretely, in this paper we will show the process of question analysis in a medical QA system. This system is able to obtain answers to different natural language questions according to a question taxonomy. In this system we combine the use of NLP techniques and biomedical resources. The main NLP technique is the use of logic forms and the pattern matching technique in this question analysis performance.

Automatic categorization has been shown to be an accurate alternative to manual categorization in which documents are processed and automatically assigned to pre-defined categories. The accuracy of different methods for categorization has been studied largely, but their efficiency has seldom been mentioned. Aiming to maintain effectiveness while improving efficiency, we proposed a fast algorithm for text categorization and a compressed document vector representation method based on a novel class space model. The experiments proved our methods have better efficiency and tolerable effectiveness.

How to improve the accuracy of categorization is a big challenge in text categorization. This paper proposes a high performance prototype system for Chinese text categorization, which mainly includes feature extraction subsystem, feature selection subsystem, and reliability evaluation subsystem for classification results. The proposed prototype system employs a two-step classifying strategy. First, the features that are effective for all testing texts are used to classify texts. Then, the reliability evaluation subsystem evaluates the classification results directly according to the outputs of the classifier, and divides them into two parts: texts classified reliable or not. Only for the texts classified unreliable at the first step, go to the second step. Second, a classifier uses the features that are more subtle and powerful for those texts classified unreliable to classify the texts. The proposed prototype system is successfully implemented in a case that exploits a Naive Bayesian classifier as the classifier in the first and second steps. Experiments show that the proposed prototype system achieves a high performance.

This article aims at presenting a methodological approach for classifying educational conference papers by employing a Bayesian Network (BN). A total of 400 conference papers were collected and categorized into 4 major topics (

Intelligent Tutoring System

, C

ognition

,

e-Learning

, and

Teacher Education

). In this study, we have implemented a 80-20 split of collected papers. 80% of the papers were meant for keywords extraction and BN parameter learning whereas the other 20% were aimed for predictive accuracy performance. A feature selection algorithm was applied to automatically extract keywords for each topic. The extracted keywords were then used for constructing BN. The prior probabilities were subsequently learned using the Expectation Maximization (EM) algorithm. The network has gone through a series of validation by human experts and experimental evaluation to analyze its predictive accuracy. The result has demonstrated that the proposed BN has outperformed Naïve Bayesian Classifier, and BN learned from the training data.

This paper presents an application of an ontology based system for automated text analysis using a sample of a drilling report to demonstrate how the methodology works. The methodology used here consists basically of organizing the knowledge related to the drilling process by elaborating the ontology of some typical problems. The whole process was carried out with the assistance of a drilling expert, and by also using software to collect the knowledge from the texts. Finally, a sample of drilling reports was used to test the system, evaluating its performance on automated text classification.

This paper proposes a topic selection method for web documents using ontology hierarchy. The idea of this approach is to utilize the ontology structure in order to determine a topic in a web document. In this paper, we propose an approach for improving the performance of document clustering as we select the topic efficiently based on domain ontology. We preprocess the web documents for keywords extraction using

Term Frequency

formula and we build domain ontology as we branch off the partial hierarchy from WordNet using an automatic domain ontology building tool in preprocessing step. And we select a topic for the web documents based on domain ontology structure. Finally we realized that our approach contributes the efficient document clustering.

This paper presents an approach for the automatic speech re-cognition using syllabic units. Its segmentation is based on using the Short-Term Total Energy Function (STTEF) and the Energy Function of the High Frequency (ERO parameter) higher than 3,5 KHz of the speech signal. Training for the classification of the syllables is based on ten related Spanish language rules for syllable splitting. Recognition is based on a Continuous Density Hidden Markov Models and the bigram model language. The approach was tested using two voice corpus of natural speech, one constructed for researching in our laboratory (experimental) and the other one, the corpus Latino40 commonly used in speech researches. The use of ERO and MFCCs parameter increases speech recognition by 5.5% when compared with recognition using STTEF in discontinuous speech and improved more than 2% in continuous speech with three states. When the number of states is incremented to five, the recognition rate is improved proportionally to 98% for the discontinuous speech and to 81% for the continuous one.

We have been building a text-independent speaker recognition system in noisy conditions. In this paper, we propose a novel feature using hybrid PCA/LDA. The feature is created from the convectional MFCC(mel-frequency cepstral coefficients) by transforming them using a matrix. The matrix consists of some components from the PCA and LDA transformation matrices. We tested the new feature using Aurora project Database 2 which is intended for the evaluation of algorithms for front-end feature extraction algorithms in background noise. The proposed method outperformed in all noise types and noise levels. It reduced the relative recognition error by 63.6% than using the baseline feature when the SNR is 15dB.

One of the speaker authentication problems consists on identifying a person only by means of his/her voice. To obtain the best authentication results, it is very important to select the most relevant features from the speech samples, this because we think that not all of the characteristics are relevant for the authentication process and also that many of these data might be redundant. This work presents the design and implementation of a Genetic-Neural algorithm for feature selection used on a speaker authentication task. We extract acoustic features such as Mel Frequency Cepstral Coefficients, on a database composed by 150 recorded voice samples, and a genetic feature selection system combined with a time delay feed-forward neural network trained by scaled conjugate gradient back propagation, to classify/authenticate the speaker. We also show that after the hybrid system finds the best solution, it almost never looses it, even when the search space changes. The design and implementation process, the performed experiments, as well as some results are shown.

This research shows the improvement obtained by including the principal component analysis as part of the feature production in the generation of a speech key. The main architecture includes an automatic segmentation of speech and a classifier. The first one, by using a forced alignment configuration, computes a set of primary features, obtains a phonetic acoustic model, and finds the beginnings and ends of the phones in each utterance. The primary features are then transformed according to both the phone model parameters and the phones segments per utterance. Before feeding these processed features to the classifier, the principal component analysis algorithm is applied to the data and a new set of secondary features is built. Then a support vector machine classifier generates an hyperplane that is capable to produce a phone key. Finally, by performing a phone spotting technique, the key is hardened. In this research the results for 10, 20 and 30 users are given using the YOHO database. 90% accuracy.

In this paper, we introduce a real-time temporal probabilistic knowledge logic, called

RATPK

, which can express not only real-time temporal and probabilistic epistemic properties but also cooperation properties. It is showed that temporal modalities such as “always in an interval”, “until in an interval”, and knowledge modalities such as “knowledge in an interval”, “common knowledge in an interval” and “probabilistic common knowledge” can be expressed in such a logic. The model checking algorithm is given and a case is studied.

This paper extends the scope of the model of regulation of social exchanges based on the concept of a supervisor of social equilibrium. We allow the supervisor to interact with personality-based agents that control the supervisor access to their internal states, behaving either as transparent agents (agents that allow full external access to their internal states) or as non-transparent agents (agents that restrict such external access). The agents may have different personality traits, which induce different attitudes towards both the regulation mechanism and the possible profits of social exchanges. Also, these personality traits influence the agents’ evaluation of their current status. To be able to reason about the social exchanges among personality-based non-transparent agents, the equilibrium supervisor models the system as a Hidden Markov Model.

This paper is a proof of concept report for a bottom-up approach to a conceptual and engineering framework to enable Intelligent Organizations using MAS Technology. We discuss our experience of implementing different types of server agents and a rudimentary

organization engine

for two industrial-scale information systems now in operation. These server agents govern knowledge repositories and user interactions according to workflow scripts that are interpreted by the organization engine. These results show how we have implemented the bottom layer of the proposed framework architecture. They also allow us to discuss how we intend to extend the current organization engine to deal with institutional aspects of an organization other than workflows.

The paper proposes a modeling methodology allowing the specification of multi mobile agent systems using nLNS, a multi level Petri net based formalism. The prey-predator problem is addressed and a modular and hierarchical model for this case study is developed. An overview of a nLNS simulator is presented through the prey predator problem.

In this paper we introduce a technique for runtime fault detection and localization in component-oriented software systems. Our approach allows for the definition of arbitrary properties at the component level. By monitoring the software system at runtime we can detect violations of these properties and, most notably, also locate possible causes for specific property violation(s). Relying on the model-based diagnosis paradigm, our fault localization technique is able to deal with intermittent fault symptoms and it allows for measurement selection. Finally, we discuss results obtained from our most recent case studies.

We present a method for sensor-based exploration of unknown environments by mobile robots. This method proceeds by building a data structure called SRT (Sensor-based Random Tree). The SRT represents a roadmap of the explored area with an associated safe region, and estimates the free space as perceived by the robot during the exploration. The original work proposed in [1] presents two techniques: SRT-Ball and SRT-Star. In this paper, we propose an alternative strategy called SRT-Radial that deals with non-holonomic constraints using two alternative planners named SRT_Extensive and SRT_Goal. We present experimental results to show the performance of the SRT-Radial and both planners.

The development of an effective central model of action selection has already been reviewed in previous work. The central model has been set to resolve a foraging task with the use of heterogeneous behavioral modules. In contrast to collecting/depositing modules that have been hand-coded, modules related to exploring follow an evolutionary approach. However, in this paper we focus on the use of genetic algorithms for evolving the weights related to calculating the urgency for a behavior to be selected. Therefore, we aim to reduce the number of decisions made by a human designer when developing the neural substratum of a central selection mechanism.

Growing Functional Modules (GFM) is a recently introduced paradigm conceived to automatically generate an adaptive controller which consists of an architecture based on interconnected growing modules. When running, the controller is able to build its own representation of the environment through acting and sensing. Due to this deep-rooted interaction with the environment, robotics is, by excellence, the field of application. This paper describes a hardware architecture designed to satisfy the requirements of the GFM controller and presents the implementation of a simple mushroom shaped robot.

This paper proposes a novel fast protein structure alignment algorithm and its application. Because it is known that the functions of protein are derived from its structure, the method of measuring the structural similarities between two proteins can be used to infer their functional closeness. In this paper, we propose a 3D chain code representation for fast measuring the local geometric similarity of protein and introduce a backtracking algorithm for joining a similar local substructure efficiently. A 3D chain code, which is a sequence of the directional vectors between the atoms in a protein, represents a local similarity of protein. After constructing a pair of similar substructures by referencing local similarity, we perform the protein alignment by joining the similar substructure pair through a backtracking algorithm. This method has particular advantages over all previous approaches; our 3D chain code representation is more intuitive and our experiments prove that the backtracking algorithm is faster than dynamic programming in general case. We have designed and implemented a protein structure alignment system based on our protein visualization software (MoleView). These experiments show rapid alignment with precise results.

The main goal of this paper is to design an electromyogram (EMG) pattern classifier which is robust to muscular fatigue effects for human-machine interaction. When a user operates some machines such as a PC or a powered wheelchair using EMG-based interface, muscular fatigue is generated by sustained duration time of muscle contraction. Therefore, recognition rates are degraded by the muscular fatigue. In this paper, an important observation is addressed: the variations of feature values due to muscular fatigue effects are consistent for sustained duration time. From this observation, a robust pattern classifier was designed through the adaptation process of hyperboxes of Fuzzy Min-Max Neural Network. As a result, significantly improved performance is confirmed.

Breast cancer is one of the main causes of death in women and early diagnosis is an important means to reduce the mortality rate. The presence of microcalcification clusters are primary indicators of early stages of malignant types of breast cancer and its detection is important to prevent the disease. This paper proposes a procedure for the classification of microcalcification clusters in mammograms using sequential difference of gaussian filters (DoG) and three evolutionary artificial neural networks (EANNs) compared against a feedforward artificial neural network (ANN) trained with backpropagation. We found that the use of genetic algorithms (GAs) for finding the optimal weight set for an ANN, finding an adequate initial weight set before starting a backpropagation training algorithm and designing its architecture and tuning its parameters, results mainly in improvements in overall accuracy, sensitivity and specificity of an ANN, compared with other networks trained with simple backpropagation.

Ultrasound images are characterized by high level of speckle noise causing undefined contours and difficulties during the segmentation process. This paper presents a novel method to detect heart cavities in ultrasound images. The method is based on a Self Organizing Map and the use of the variance of images. Successful application of our approach to detect heart cavities on real images is presented.

This study aims to develop an effective measurement instrument and analysis method of gait stability, particularly focused on the motion of lower spine and pelvis during gait. Silicon micromechanical inertial instruments have been developed and body-attitude (pitch and roll) angles were estimated via closed-loop strapdown estimation filters, which results in improved accuracy of estimated attitude. Also, it is shown that the spectral analysis utilizing the Fast Fourier Transform (FFT) provides an efficient analysis method, which provides quantitative diagnoses for the gait stability. The results of experiments on various subjects suggest that the proposed system provides a simplified but an efficient tool for the evaluation of both gait stabilities and rehabilitation treatments effects.