Search

We propose an optimization scheme that achieves fast yet accurate computation of superpixels from an image. Our optimization is designed to improve the efficiency and robustness for the minimization of a composite energy functional in the expectation-minimization (EM) framework where we restrict the update of an estimate to avoid redundant computations. We consider a superpixel energy formulation that consists of L2-norm for the spatial regularity and L1-norm for the data fidelity in the demonstration of the robustness of the proposed algorithm. The quantitative and qualitative evaluations indicate that our superpixel algorithm outperforms SLIC and SEEDS algorithms. It is also demonstrated that our algorithm guarantees the convergence with less computational cost by up to 89% on average compared to the SLIC algorithm while preserving the accuracy. Our optimization scheme can be easily extended to other applications in which the alternating minimization is applicable in the EM framework. © 2016 SPIE and IS&T [DOI: 10.1117/1.JEI.25.5.053035] [ABSTRACT FROM AUTHOR]

We consider the problem of approximating and learning disjunctions (or equivalently, conjunctions) on symmetric distributions over {0,1}n. Symmetric distributions are distributions whose PDF is invariant under any permutation of the variables. We prove that for every symmetric distribution D, there exists a set of nO(log(1/ϵ)) functions S, such that for every disjunction c, there is function p, expressible as a linear combination of functions in S, such that p ϵ-approximates c in l1 distance on D or Ex∼D[∣c(x) - p(x)∣] ≤ ϵ. This implies an agnostic learning algorithm for disjunctions on symmetric distributions that runs in time nO(log(1/ϵ)). The best known previous bound is nO(log(1/ϵ4) and follows from approximation of the more general class of halfspaces (Wimmer, 2010). We also show that there exists a symmetric distribution D, such that the minimum degree of a polynomial that 1/3-approximates the disjunction of all n variables in l1 distance on D is Ω(√n). Therefore the learning result above cannot be achieved via l1-regression with a polynomial basis used in most other agnostic learning algorithms. Our technique also gives a simple proof that for any product distribution D and every disjunction c, there exists a polynomial p of degree O(log (1/ϵ)) such that p ϵ-approximates c in l1 distance on D. This was first proved by Blais et al. (2008) via a more involved argument. [ABSTRACT FROM AUTHOR]

Consider a face-down card lying on the table such that we do not know whether its suit color is black or red. Then, how do we make identical copies of the card while keeping its color secret? A partial solution has been devised: using a number of additional black and red cards, Niemi and Renvall proposed an excellent protocol which can copy a face-down card while allowing only a small probability of revealing its color. In contrast, this paper shows the nonexistence of a perfect solution, namely, the impossibility of copying a face-down card with perfect secrecy. To prove such an impossibility result, we construct a rigorous mathematical model of card-based cryptographic protocols; giving this general computational model is the main result of this paper. [ABSTRACT FROM AUTHOR]

Abstract: Partial-monitoring games constitute a mathematical framework for sequential decision making problems with imperfect feedback: the learner repeatedly chooses an action, the opponent responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action and the outcome. The goal of the learner is to minimize his total cumulative loss. We make progress toward the classification of these games based on their minimax expected regret. Namely, we classify almost all games with two outcomes and a finite number of actions: we show that their minimax expected regret is either zero, , , or , and we give a simple and efficiently computable classification of these four classes of games. Our hope is that the result can serve as a stepping stone toward classifying all finite partial-monitoring games. [Copyright &y& Elsevier]

Abstract: Known algorithms for learning PDFA can only be shown to run in time polynomial in the so-called distinguishability of the target machine, besides the number of states and the usual accuracy and confidence parameters. We show that the dependence on is necessary in the worst case for every algorithm whose structure resembles existing ones. As a technical tool, a new variant of Statistical Queries termed -queries is defined. We show how to simulate -queries using classical Statistical Queries and show that known PAC algorithms for learning PDFA are in fact statistical query algorithms. Our results include a lower bound: every algorithm to learn PDFA with queries using a reasonable tolerance must make queries for every . Finally, an adaptive algorithm that PAC-learns w.r.t. another measure of complexity is described. This yields better efficiency in many cases, while retaining the same inevitable worst-case behavior. Our algorithm requires fewer input parameters than previously existing ones, and has a better sample bound. [Copyright &y& Elsevier]

The rapid growth of smart grid systems demands efficient management of smart grid services. Smart grids are expected to enable the delivery and management of electricity in a more reliable, efficient, economical, and secured manner. Thus, the development of effective power management solutions for smart grids to meet these challenges is an important area of research in recent times. In this article, we propose using learning automata (LA), a computational learning utility, for efficient power management in smart grids (LAPM). The proposed system, LAPM, helps in identifying the electricity required for various distribution substations and controls the usage of power by various devices (i.e., preventing unauthorized use of power). The use of LA enables performing a dynamic analysis of power usage and providing decision making for its effective usage. The system is evaluated on a real-life-resembling environment, with respect to parameters such as power utilization and customer satisfaction. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, an intelligent prognostic for battery health based on sample entropy (SampEn) feature of discharge voltage is proposed. SampEn can provide computational means for assessing the predictability of a time series and also can quantity the regularity of a data sequence. Therefore, when it is applied to discharge voltage battery data, it could serve an indicator for battery health. In this work, the intelligent ability is introduced by utilizing machine learning methods namely support vector machine (SVM) and relevance vector machine (RVM). SampEn and estimated state of charge (SOH) are employed as data input and target vector of learning algorithms, respectively. The results show that the proposed method is plausible due to the good performance of SVM and RVM in SOH prediction. In our study, RVM outperforms SVM based battery health prognostics. [Copyright &y& Elsevier]

Hierarchical text classification (HTC) approaches have recently attracted a lot of interest on the part of researchers in human language technology and machine learning, since they have been shown to bring about equal, if not better, classification accuracy with respect to their 'flat' counterparts while allowing exponential time savings at both learning and classification time. A typical component of HTC methods is a 'local' policy for selecting negative examples: Given a category c, its negative training examples are by default identified with the training examples that are negative for c and positive for the categories which are siblings of c in the hierarchy. However, this policy has always been taken for granted and never been subjected to careful scrutiny since first proposed 15 years ago. This article proposes a thorough experimental comparison between this policy and three other policies for the selection of negative examples in HTC contexts, one of which (BEST LOCAL (k)) is being proposed for the first time in this article. We compare these policies on the hierarchical versions of three supervised learning algorithms (boosting, support vector machines, and naïve Bayes) by performing experiments on two standard TC datasets, REUTERS-21578 and RCV1-V2. [ABSTRACT FROM AUTHOR]

It is widely accepted in machine learning that it is easier to learn several smaller decomposed concepts than a single large one. Typically, such decomposition of concepts is achieved in highly constrained environments, or aided by human experts. In this article, we investigate concept learning by example decomposition in a general probably approximately correct setting for Boolean learning. We develop sample complexity bounds for the different steps involved in the process. We formally show that if the cost of example partitioning is kept low then it is highly advantageous to learn by example decomposition. [ABSTRACT FROM AUTHOR]

Abstract: A challenge in building pervasive and smart spaces is to learn and recognize human activities of daily living (ADLs). In this paper, we address this problem and argue that in dealing with ADLs, it is beneficial to exploit both their typical duration patterns and inherent hierarchical structures. We exploit efficient duration modeling using the novel Coxian distribution to form the Coxian hidden semi-Markov model (CxHSMM) and apply it to the problem of learning and recognizing ADLs with complex temporal dependencies. The Coxian duration model has several advantages over existing duration parameterization using multinomial or exponential family distributions, including its denseness in the space of nonnegative distributions, low number of parameters, computational efficiency and the existence of closed-form estimation solutions. Further we combine both hierarchical and duration extensions of the hidden Markov model (HMM) to form the novel switching hidden semi-Markov model (SHSMM), and empirically compare its performance with existing models. The model can learn what an occupant normally does during the day from unsegmented training data and then perform online activity classification, segmentation and abnormality detection. Experimental results show that Coxian modeling outperforms a range of baseline models for the task of activity segmentation. We also achieve a recognition accuracy competitive to the current state-of-the-art multinomial duration model, while gaining a significant reduction in computation. Furthermore, cross-validation model selection on the number of phases K in the Coxian indicates that only a small K is required to achieve the optimal performance. Finally, our models are further tested in a more challenging setting in which the tracking is often lost and the activities considerably overlap. With a small amount of labels supplied during training in a partially supervised learning mode, our models are again able to deliver reliable performance, again with a small number of phases, making our proposed framework an attractive choice for activity modeling. [Copyright &y& Elsevier]

Abstract: Iterative learning (-learning) is a Gold-style learning model in which each of a learner’s output conjectures may depend only upon the learner’s current conjecture and the current input element. Two extensions of the -learning model are considered, each of which involves parallelism. The first is to run, in parallel, distinct instantiations of a single learner on each input element. The second is to run, in parallel, individual learners incorporating the first extension, and to allow the learners to communicate their results. In most contexts, parallelism is only a means of improving efficiency. However, as shown herein, learners incorporating the first extension are more powerful than -learners, and, collective learners resulting from the second extension increase in learning power as increases. Attention is paid to how one would actually implement a learner incorporating each extension. Parallelism is the underlying mechanism employed. [Copyright &y& Elsevier]

In this paper we introduce and evaluate a novel machine learning based approach to reduce the complexity of Intra macroblock (MB) coding. The proposed approach is based on the hypothesis that MB coding mode decisions in H.264/AVC video have a correlation with the intensities of adjacent MBs and sub-MBs. This paper also discusses and analyzes different approaches of using machine learning in Intra prediction. We discuss, amongst other features, slices, Intra prediction scheme for H.264 and data mining. We use data mining algorithms to develop decision trees for H.264 coding mode decisions. The proposed approach reduces the H.264/AVC MB mode computation process into a decision tree lookup with very low complexity. The proposed algorithm is implemented in reference software by modifying the source code and is compared with the JM reference software for H.264/AVC. [ABSTRACT FROM AUTHOR]

Abstract: We propose a new method that treats visible human behaviour at the level of navigational strategies. By inferring intentions in terms of known goals, it is possible to explain the behaviour of people moving around within the field of view of a video camera. The approach presented here incorporates models of navigation from within psychology which are both simple and conceptually plausible, whilst providing good results in an event-detection application. The output is in the form of statements involving goals, such as “Agent 25 went to exit 8 via sub-goals 34 and 21” for a given navigational strategy, an image representing the path through the scene, and an overall score for each trajectory. The central algorithm generates all plausible paths through the scene to known goal sites and then compares each path to the agent''s actual trajectory thus finding the most likely explanation for their behaviour. Two navigational strategies are examined, shortest path and simplest path. Experimental results are presented for an outdoor car-park and an indoor foyer scene, and our method is found to produce psychologically plausible explanations in the majority of cases. We propose a novel approach to determining the effectiveness of event detection systems, and evaluate the method presented here against this new ground truth. This evaluation method uses human observers to judge the behaviour shown in various video clips, then uses these judgements in correlation with those of the software. We compare the method with a standard machine learning approach based on nearest neighbour. Finally we consider the application of such a system in a binary event-detection or behaviour filtering system. [Copyright &y& Elsevier]

In the present work, an attempt has been made to use different artificial neural network (ANN) architectures to achieve more accurate prediction of drill wear. Large numbers of drilling operations, using mild steel as the work-piece and high speed steel (HSS) as the drill, have been performed and drill flank wear has been measured intermittently. Experimental results show a strong dependency of direct and indirect process parameters with drill wear. Experimentally obtained data have been used to train different ANN architectures using different combinations of important process parameters as input and measured flank wear as the output of the network. Relative performances of different ANN based drill wear prediction schemes in regard to prediction of drill wear have been compared. From the present work it has been observed that inclusions of more sensor signals as input to the network results a better-trained network, which can predict wear more accurately. It has also been observed from the present work that standard back propagation neural network (BPNN) predicts wear more accurately compared to fuzzy back propagation network (FBPN) and self-organizing method (SOM), through BPNN is slow in convergence. [ABSTRACT FROM AUTHOR]

This paper investigates a variation to Adlassnig's fuzzy relation based model for medical diagnosis. The proposed model is an attempt to closely replicate a physician's perceptions of symptom-disease associations and his approximate-reasoning for diagnosis. For proof of principle, the algorithm is evaluated in two sample studies. First case study relates to selected cardiovascular diseases, wherein the required parameters are estimated by interviewing physicians, and an evaluation is performed on a dataset of 79 cases. In the second study, the algorithm is implemented using an alternative semiautomatic approach for a more complex problem of diagnosing common infectious diseases, wherein the parameters are derived from a dataset of 92 case records; for evaluation, jack-knife is performed along with a comparison with Independence Bayes, considered here as the reference standard. The proposed algorithm was found to be as accurate as Independence Bayes for diagnosing common infectious diseases from the small dataset. This result may indicate the utility of proposed algorithm to optimally model the diagnostic process for small datasets; especially, due to its computational simplicity. Further studies on a variety of datasets are needed to establish such a utility. [ABSTRACT FROM AUTHOR]

The ocean color inverse problem consists of determining the concentrations of optically active constituents, such as chlorophyll, suspended particulate matter and colored dissolved organic matter, from remotely sensed multispectral measurements of the reflected sunlight back-scattered by the water body. In this paper, we approach this regression problem by using an evolutionary multi-objective algorithm, namely the (2+2) Modified Pareto Archived Evolutionary Strategy ((2+2)M-PAES), to optimize Takagi-Sugeno type (TS-type) fuzzy rule-based systems (FRBSs). Accuracy and complexity are the two competitive objectives to be simultaneously optimized. TS-type FRBSs are implemented as an artificial neural network; by training the neural network, the parameters of the fuzzy model are adjusted. In this way, the evolutionary optimization coarsely identifies the structure of the TS-type FRBSs, while the corresponding neural networks finely tune their parameters. As a result, a set of TS-type FRBSs with different trade-offs between accuracy and complexity is provided at the end of the optimization process. We show the effectiveness of our approach by comparing our results with those obtained on the ocean color inverse problem by other techniques recently proposed in the literature. [ABSTRACT FROM AUTHOR]

Fuzzy vault cryptography relies on the error-correcting capabilities of the underlying error-correction code (typically, Reed-Solomon). Therefore, any application of such a system can tolerate only a limited number of errors associated with the true data points. For fingerprint vault systems, poor alignment can cause valid extracted minutiae (true data points) to be regarded as errors because they are outside the matching threshold. Attempting to overcome this problem by increasing the matching threshold may result in additional matching of false (chaff) points in the vault, depending on the density of points in the vault. A simulation study was conducted in order to determine acceptable parameters and thresholds for a fingerprint vault cryptographic system to function successfully. Simulation results show that the variation of repeatable minutiae points must be below the matching threshold of the system for acceptable performance and therefore improving the quality of fingerprint alignment is critical to a successful implementation of the method. An experimental study was also conducted to confirm that if fingerprint alignment is not carefully considered, the fuzzy vault system for fingerprints is prone to failure. [ABSTRACT FROM AUTHOR]

A process of trial and error plays an important role in not only the human learning but also the machine learning. Such a process is called exploration in the reinforcement learning which has originated from experimental studies on learning in psychology. A uniform pseudorandom number generator appears to be suitable for exploration. However, it is known that a chaotic source also provides a random-like sequence as like as a stochastic source. By applying this random-like feature of a deterministic chaotic generator for exploration in a nonstationary shortcut maze problem, we have observed that a deterministic chaotic generator provides a better performance than a stochastic random exploration generator when used for exploration based on a logistic map. In this study, in order to confirm this difference in the performances of the two generators, we examine another nonstationary task – target capturing. The simulation result of this task agrees with the result of our previous study. From the view of multi-agent system, it is an inhomogeneous or heterogeneous system composed of some kinds of agents in many cases. In such situations, the exploration of them is not uniform. Chaotic exploration may suit well this heterogeneity in such a multi-agent system. [ABSTRACT FROM AUTHOR]

The application of machine learning to intrusion detection has been researched for several decades, however, with varying degrees of success. This paper focuses on two common techniques: Multi Layer Perceptrons (MLPs) and Decision Trees (DTs). Previous research on these techniques has produced contradictory results concerning their ability to detect particular classes of intrusion. Some of these contradictions are argued to be a result of properties of the data set used for empirical study, the KDD Cup '99 data set, which poses several challenges to learning algorithms. One particular challenge is considered here, learning from imbalanced data, which is an intrinsic problem to intrusion detection. Empirical results show that both the DT and MLP trained with back propagation obtain very poor classification rates of the minor classes, particularly U2R (User to Root) intrusions; the MLP often being unable to detect this class. An evolutionary neural network is employed, in which several evaluation functions are examined. Two general fitness measures are used, which lead to similar behaviour to training an MLP with back propagation. However, when employing evaluation functions that calculate the fitness proportionally to the instances of each class, thereby avoiding a bias towards the major class(es) in the data set, significantly improved true positive rates are obtained whilst maintaining a low false positive rate. [ABSTRACT FROM AUTHOR]

In this brief, a new neural network model called generalized adaptive resonance theory (GART) is introduced. GART is a hybrid model that comprises a modified Gaussian adaptive resonance theory (MGA) and the generalized regression neural network (GRNN). It is an enhanced version of the GRNN, which preserves the online learning properties of adaptive resonance theory (ART). A series of empirical studies to assess the effectiveness of GART in classification, regression, and time series prediction tasks is conducted. The results demonstrate that GART is able to produce good performances as compared with those of other methods, including the online sequential extreme learning machine (OSELM) and sequential learning radial basis function (RBF) neural network models. [ABSTRACT FROM AUTHOR]

Abstract-The recent years have witnessed a surge of interest in semisupervised learning. Numerous methods have been proposed for learning from partially labeled data. In this brief, a novel semisupervised learning approach based on an electrostatic field model is proposed. We treat the labeled data points as point charges, therefore the remaining unlabeled data points are placed in the electrostatic fields generated by these charges. The labels of these unlabeled data points can be regarded as the electric potentials of the electrostatic field at their corresponding places. Moreover, we also develop an efficient way to extend our method for out-of-sample data and analyze theoretically the relationship between our method and the traditional graph-based methods. Finally, the experimental results on both toy and real-world data sets are provided to show the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Manifold learning has been demonstrated as an effective way to represent intrinsic geometrical structure of samples. In this paper, a new manifold learning approach, named Local Coordinates Alignment (LCA), is developed based on the alignment technique. LCA first obtains local coordinates as representations of local neighborhood by preserving proximity relations on a patch, which is Euclidean. Then, these extracted local coordinates are aligned to yield the global embeddings. To solve the out of sample problem, linearization of LCA (LLCA) is proposed. In addition, in order to solve the non-Euclidean problem in real world data when building the locality, kernel techniques are utilized to represent similarity of the pairwise points on a local patch. Empirical studies on both synthetic data and face image sets show effectiveness of the developed approaches. [ABSTRACT FROM AUTHOR]

Closed sets have been proven successful in the context of compacted data representation for association rule learning. However, their use is mainly descriptive, dealing only with unlabeled data. This paper shows that when considering labeled data, closed sets can be adapted for classification and discrimination purposes by conveniently contrasting covering properties on positive and negative examples. We formally prove that these sets characterize the space of relevant combinations of features for discriminating the target class. In practice, identifying relevant/irrelevant combinations of features through closed sets is useful in many applications: to compact emerging patterns of typical descriptive mining applications, to reduce the number of essential rules in classification, and to efficiently learn subgroup descriptions, as demonstrated in real-life subgroup discovery experiments on a high dimensional microarray data set. [ABSTRACT FROM AUTHOR]

Abstract: We give a new algorithm for learning intersections of halfspaces with a margin, i.e. under the assumption that no example lies too close to any separating hyperplane. Our algorithm combines random projection techniques for dimensionality reduction, polynomial threshold function constructions, and kernel methods. The algorithm is fast and simple. It learns a broader class of functions and achieves an exponential runtime improvement compared with previous work on learning intersections of halfspaces with a margin. [Copyright &y& Elsevier]

We consider a variant of Gold’s learning paradigm where a learner receives as input different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed different languages, can produce grammars covering all input languages, but cannot produce grammars covering input languages for any . We also consider a variant of this task, where each of the output grammars may not cover more than input languages. Our main results indicate that the major factor affecting classification capabilities is the difference between the number of input languages and the number of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters (the number of input languages), (number of output grammars), and (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters of certain types. [Copyright &y& Elsevier]

Documents formatted in eXtensible Markup Language (XML) are available in collections of various document types. In this paper, we present an approach for the summarisation of XML documents. The novelty of this approach lies in that it is based on features not only from the content of documents, but also from their logical structure. We follow a machine learning, sentence extraction-based summarisation technique. To find which features are more effective for producing summaries, this approach views sentence extraction as an ordering task. We evaluated our summarisation model using the INEX and SUMMAC datasets. The results demonstrate that the inclusion of features from the logical structure of documents increases the effectiveness of the summariser, and that the learnable system is also effective and well-suited to the task of summarisation in the context of XML documents. Our approach is generic, and is therefore applicable, apart from entire documents, to elements of varying granularity within the XML tree. We view these results as a step towards the intelligent summarisation of XML documents. [ABSTRACT FROM AUTHOR]

In this paper, we explore the possibility that machine learning approaches to natural- language processing being developed in engineering-oriented computational linguistics may be able to provide specific scientific insights into the nature of human language. We argue that, in principle, machine learning results could inform basic debates about language, in one area at least, and that in practice, existing results may offer initial tentative support for this prospect. Further, results from computational learning theory can inform arguments carried on within linguistic theory as well. [ABSTRACT FROM AUTHOR]

Abstract: Multi-label learning originated from the investigation of text categorization problem, where each document may belong to several predefined topics simultaneously. In multi-label learning, the training set is composed of instances each associated with a set of labels, and the task is to predict the label sets of unseen instances through analyzing training instances with known label sets. In this paper, a multi-label lazy learning approach named ML-KNN is presented, which is derived from the traditional K-nearest neighbor (KNN) algorithm. In detail, for each unseen instance, its K nearest neighbors in the training set are firstly identified. After that, based on statistical information gained from the label sets of these neighboring instances, i.e. the number of neighboring instances belonging to each possible class, maximum a posteriori (MAP) principle is utilized to determine the label set for the unseen instance. Experiments on three different real-world multi-label learning problems, i.e. Yeast gene functional analysis, natural scene classification and automatic web page categorization, show that ML-KNN achieves superior performance to some well-established multi-label learning algorithms. [Copyright &y& Elsevier]

From computational learning theory, sample size in machine learning problems indeed affects the learning performance. Since only few samples can be obtained in the early stages of a system and fewer exemplars usually lead to a low learning accuracy, this research compares different machine learning methods through their classification accuracies to improve small-data-set learning. Techniques used in this paper include the mega-trend diffusion technique, a backpropagation neural network, a support vector machine, and decision trees to explore the machine learning issue with two real medical data sets concerning cancer. The result of the experiment shows that the mega-trend diffusion technique and backpropagation approaches are effective methods of small-data-set learning. [ABSTRACT FROM AUTHOR]

The increasing volumes of unsolicited bulk e-mail (also known as spam) are bringing more annoyance for most Internet users. Using a classifier based on a specific machine-learning technique to automatically filter out spam e-mail has drawn many researchers’ attention. This paper is a comparative study the performance of three commonly used machine learning methods in spam filtering. On the other hand, we try to integrate two spam filtering methods to obtain better performance. A set of systematic experiments has been conducted with these methods which are applied to different parts of an e-mail. Experiments show that using the header only can achieve satisfactory performance, and the idea of integrating disparate methods is a promising way to fight spam. [Copyright &y& Elsevier]

The initial state of a design under verification has a major impact on the ability of stimuli generators to successfully generate the requested stimuli. For complexity reasons, most stimuli generators use sequential solutions without planning ahead. Therefore, in many cases, they fail to produce a consistent stimuli due to an inadequate selection of the initial state. We propose a new method, based on machine learning techniques, to improve generation success by learning the relationship between the initial state vector and generation success. We applied the proposed method in two different settings, with the objective of improving generation success and coverage in processor and system level generation. In both settings, the proposed method significantly reduced generation failures and enabled faster coverage. [ABSTRACT FROM AUTHOR]

In this paper we describe an application of Q 2 learning, a recently developed approach to machine learning in numerical domains (Šuc et al., 20032004) to the automated modelling of a complex, industrially relevant mechanical system – a four wheel suspension and steering system of a car. In this experiment, first a qualitative model of this dynamic system was induced from data, and then this model was reified into a quantitative model. The induced qualitative models enable explanation of relations among the variables in the system and, when reified into quantitative models, enable accurate numerical prediction. Furthermore, the qualitative guidance of the quantitative modelling process leads to predictions that are significantly more accurate than those obtained by state-of-the-art numerical learning methods. [ABSTRACT FROM AUTHOR]

Imbalanced learning is a challenged task in machine learning. In this context, the data associated with one class are far fewer than those associated with the other class. Traditional machine learning methods seeking classification accuracy over a full range of instances are not suitable to deal with this problem, since they tend to classify all the data into a majority class, usually the less important class. In this correspondence, the authors describe a new approach named the biased minimax probability machine (BMPM) to deal with the problem of imbalanced learning. This BMPM model is demonstrated to provide an elegant and systematic way for imbalanced learning. More specifically, by controlling the accuracy of the majority class under all possible choices of class-conditional densities with a given mean and covariance matrix, this model can quantitatively and systematically incorporate a bias for the minority class. By establishing an explicit connection between the classification accuracy and the bias, this approach distinguishes itself from the many current imbalanced-learning methods; these methods often impose a certain bias on the minority data by adapting intermediate factors via the trial-and-error procedure. The authors detail the theoretical foundation, prove its solvability, propose an efficient optimization algorithm, and perform a series of experiments to evaluate the novel model. The comparison with other competitive methods demonstrates the effectiveness of this new model. [ABSTRACT FROM AUTHOR]

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any ≤1k≤n) over the original n Boolean features in the input space. This motivates the question of whether maximum margin algorithms such as Support Vector Machines can learn Disjunctive Normal Form expressions in the Probably Approximately Correct (PAC) learning model by using this kernel. We study this question, as well as a variant in which structural risk minimization (SRM) is performed where the class hierarchy is taken over the length of conjunctions. We show that maximum margin algorithms using the Boolean kernels do not PAC learn t(n)- term DNF for any t(n) = ω(1), even when used with such a SRM scheme. We also consider PAC learning under the uniform distribution and show that if the kernel uses conjunctions of length ϖ(√n) then the maximum margin hypothesis will fail on the uniform distribution as well. Our results concretely illustrate that margin based algorithms may overfit when learning simple target functions with natural kernels. [ABSTRACT FROM AUTHOR]

The CPR (“cumulative proportional reinforcement”) learning rule stipulates that an agent chooses a move with a probability proportional to the cumulative payoff she obtained in the past with that move. Previously considered for strategies in normal form games (Laslier, Topol and Walliser, Games and Econ. Behav., 2001), the CPR rule is here adapted for actions in perfect information extensive form games. The paper shows that the action-based CPR process converges with probability one to the (unique) subgame perfect equilibrium. [ABSTRACT FROM AUTHOR]

In my bookHow the Mind Works, I defended the theory that the human mind is a naturally selected system of organs of computation. Jerry Fodor claims that‘the mind doesn’t work that way’(in a book with that title) because(1) Turing Machines cannot duplicate humans’ ability to perform abduction(inference to the best explanation);(2) though a massively modular system could succeed at abduction, such a system is implausible on other grounds; and(3) evolution adds nothing to our understanding of the mind. In this review I show that these arguments are flawed. First, my claim that the mind is a computational system is different from the claim Fodor attacks(that the mind has the architecture of a Turing Machine); therefore the practical limitations of Turing Machines are irrelevant. Second, Fodor identifies abduction with the cumulative accomplishments of the scientific community over millennia. This is very different from the accomplishments of human common sense, so the supposed gap between human cognition and computational models may be illusory. Third, my claim about biological specialization, as seen in organ systems, is distinct from Fodor's own notion of encapsulated modules, so the limitations of the latter are irrelevant. Fourth, Fodor's arguments dismissing of the relevance of evolution to psychology are unsound. [ABSTRACT FROM AUTHOR]

Support vector machines (SVMs) construct decision functions that are linear combinations of kernel evaluations on the training set. The samples with non-vanishing coefficients are called support vectors. In this work we establish lower (asymptotical) bounds on the number of support vectors. On our way we prove several results which are of great importance for the understanding of SVMs. In particular, we describe to which "limit" SVM decision functions tend, discuss the corresponding notion of convergence and provide some results on the stability of SVMs using subdifferential calculus in the associated reproducing kernel Hilbert space. [ABSTRACT FROM AUTHOR]

Neural networks do not readily provide an explanation of the knowledge stored in their weights as part of their information processing. Until recently, neural networks were considered to be black boxes, with the knowledge stored in their weights not readily accessible. Since then, research has resulted in a number of algorithms for extracting knowledge in symbolic form from trained neural networks. This article addresses the extraction of knowledge in symbolic form from recurrent neural networks trained to behave like deterministic finite-state automata (DFAs). To date, methods used to extract knowledge from such networks have relied on the hypothesis that networks' states tend to cluster and that clusters of network states correspond to DFA states. The computational complexity of such a cluster analysis has led to heuristics that either limit the number of clusters that may form during training or limit the exploration of the space of hidden recurrent state neurons. These limitations, while necessary, may lead to decreased fidelity, in which the extracted knowledge may not model the true behavior of a trained network, perhaps not even for the training set. The method proposed here uses a polynomial time, symbolic learning algorithm to infer DFAs solely from the observation of a trained network's input-output behavior. Thus, this method has the potential to increase the fidelity of the extracted knowledge. [ABSTRACT FROM AUTHOR]

We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P=NP, there is no polynomial time approximation scheme for finding a member in the class that approximately maximizes the agreement with a given training sample. In particular our results apply to the classes of monomials, axis-aligned hyper-rectangles, closed balls and monotone monomials. For each of these classes, we prove the NP-hardness of approximating maximal agreement to within some fixed constant (independent of the sample size and of the dimensionality of the sample space). For the class of half-spaces, we prove that, for any ϵ>0, it is NP-hard to approximately maximize agreements to within a factor of (418/415−ϵ), improving on the best previously known constant for this problem, and using a simpler proof. An interesting feature of our proofs is that, for each of the classes we discuss, we find patterns of training examples that, while being hard for approximating agreement within that concept class, allow efficient agreement maximization within other concept classes. These results bring up a new aspect of the model selection problem—they imply that the choice of hypothesis class for agnostic learning from among those considered in this paper can drastically effect the computational complexity of the learning process. [Copyright &y& Elsevier]

Subspace clustering is very useful in many fields, such as computer vision and machine learning. However, most of the clustering methods cannot deal with out-of-sample data directly. For each new sample, these methods need to relearn the representations of all (new and original) data for clustering. This is unrealistic in many practical applications. A new online clustering method to cluster out-of sample data in terms of the meaningful energy scores of data is proposed. By interpreting low-rank representation (LRR) as a dynamical system, a computation method for energy scores of data has been developed. The scores can be calculated by integration, independent of the LRR learning procedure. Then, a linear classifier is used to cluster out-of-sample data using their energy scores. Experimental results demonstrate the effectiveness and efficiency of the method. [ABSTRACT FROM AUTHOR]