Learning intersection-closed classes with signatures

Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature.     

A tight bound on concept learning

A tight bound on the generalization performance of concept learning is shown by a novel approach. Unlike existing theories, the new approach uses no assumption on large sample size as in Bayesian approach and does not consider the uniform learnability as in the VC dimension analysis. We analyze the generalization performance of some particular learning algorithm that is not necessarily well behaved, in the hope that once learning curves or sample complexity of this algorithm is obtained, it is applicable to real learning situations. The result is expressed in a dimension called Boolean interpolation dimension, and is tight in the sense that it meets the lower bound requirement of Baum and Haussler (1989). The Boolean interpolation dimension is not greater than the number of modifiable system parameters, and definable for almost all the real-world networks such as backpropagation networks and linear threshold multilayer networks. It is shown that the generalization error follows from a beta distribution of parameters m, the number of training examples, and d, the Boolean interpolation dimension. This implies that for large d, the learning results tend to the average-case result, known as the self-averaging property of the learning. The bound is shown to be applicable to the practical learning algorithms that can be modeled by the Gibbs algorithm with a uniform prior. The result is also extended to the case of inconsistent learning.     

On stochastic approximation algorithms for classes of PAC learning problems.

The classical stochastic approximation methods are shown to yield algorithms to solve several formulations of the PAC learning problem defined on the domain [0,1](d). Under some smoothness conditions on the probability measure functions, simple algorithms to solve some PAC learning problems are proposed based on networks of nonpolynomial units (e.g. artificial neural networks). Conditions on the sizes of the samples required to ensure the error bounds are derived using martingale inequalities.     

An improved lower bound on query complexity for quantum PAC learning

In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d, the lower bound is for ? accuracy and 1−δ confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is .     

A new complexity bound for the least-squares problem

For a least-squares problem of m degree polynomial regression with n measured values (n ≥ m + 1), the traditional methods need O(n²m) arithmetic operations. We prove that the arithmetic complexity of this problem does not exceed O(nlog²₂m).     

A new lower bound for curriculum-based course timetabling

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones).     

A new concept of invariance for saturated systems

In this paper, the notions of SNS-invariance and SNS-domain of attraction are introduced. The SNS-domain of attraction serves as an estimation of the domain of attraction of a saturated system. It is shown that, in the case of single input saturated systems, any contractive set is contained in the SNS-domain of attraction. Another important characteristic of the SNS-domain of attraction is that it contains any estimation obtained by means of a linear difference inclusion of the saturated system. A simple algorithm that converges to the SNS-domain of attraction is presented. An illustrative example is given.     

A new approach for constructing the concept map

In recent years, e-learning system has become more and more popular and many adaptive learning environments have been proposed to offer learners customized courses in accordance with their aptitudes and learning results. For achieving the adaptive learning, a predefined concept map of a course is often used to provide adaptive learning guidance for learners. However, it is difficult and time consuming to create the concept map of a course. Thus, how to automatically create a concept map of a course becomes an interesting issue. In this paper, we propose a Two-Phase Concept Map Construction (TP-CMC) approach to automatically construct the concept map by learners’ historical testing records. Phase 1 is used to preprocess the testing records; i.e., transform the numeric grade data, refine the testing records, and mine the association rules from input data. Phase 2 is used to transform the mined association rules into prerequisite relationships among learning concepts for creating the concept map. Therefore, in Phase 1, we apply Fuzzy Set Theory to transform the numeric testing records of learners into symbolic data, apply Education Theory to further refine it, and apply Data Mining approach to find its grade fuzzy association rules. Then, in Phase 2, based upon our observation in real learning situation, we use multiple rule types to further analyze the mined rules and then propose a heuristic algorithm to automatically construct the concept map. Finally, the Redundancy and Circularity of the concept map constructed are also discussed. Moreover, we also develop a prototype system of TP-CMC and then use the real testing records of students in junior high school to evaluate the results. The experimental results show that our proposed approach is workable.     

A new algebraic structure for formal concept analysis

Formal concept analysis (FCA) originally proposed by Wille [39], is an important theory for data analysis and knowledge discovery. Concept lattice is the core of the mathematical theory of formal concept analysis. To address the requirements of real word applications, concept lattice has been extended to many other forms from the theoretical point of view and possible applications. In this paper, with the aim of deriving the mathematical properties of formal concepts from the point of algebra, we propose a new algebra system for the formal context. Under the frame of the proposed system, some interesting properties of formal concepts are explored, which could be applied to explore concept hierarchy and ontology merging.     

A new upper bound for the skewed structured singular value

The structured singular value (s.s.v)μ enables the study of robust stability and performance of a controller in the presence of real parametric uncertainties and complex uncertainties corresponding to neglected dynamics. In spite of the NP-hard characteristic of the problem, it is now possible to compute an interval for the s.s.v. μ using polynomial-time algorithms. The skewed s.s.v. ν was introduced by Fan and Tits in the context of robust performance analysis. The primary aim of this paper is to propose a new mixed ν upper bound, which is applicable to problems with a special, but practically important, structure. We then illustrate through a realistic missile example that certain problems naturally require the ν tool rather than the μ tool. Copyright © 1999 John Wiley & Sons, Ltd.     

A new concept in chair design

. What is to be expected from the office chair of the future? One thing is certain: office seating is taking on increasingly dynamic dimensions. Office work today is based on a multitude of activities requiring frequent changes in position, and added to this are flexible organizational forms—technically complex office systems are often used by a number of people. Thus, the working chair has become a prime target for an ergonomic approach in the office environment.     

A new method for mining regression classes in large data sets

Extracting patterns and models of interest from large databases is attracting much attention in a variety of disciplines. Knowledge discovery in databases (KDD) and data mining (DM) are areas of common interest to researchers in machine learning, pattern recognition, statistics, artificial intelligence, and high performance computing. An effective and robust method, the regression class mixture decomposition (RCMD) method, is proposed for the mining of regression classes in large data sets, especially those contaminated by noise. A concept, called “regression class” which is defined as a subset of the data set that is subject to a regression model, is proposed as a basic building block on which the mining process is based. A large data set is treated as a mixture population in which there are many such regression classes and others not accounted for by the regression models. Iterative and genetic-based algorithms for the optimization of the objective function in the RCMD method are also constructed. It is demonstrated that the RCMD method can resist a very large proportion of noisy data, identify each regression class, assign an inlier set of data points supporting each identified regression class, and determine the a priori unknown number of statistically valid models in the data set. Although the models are extracted sequentially, the final result is almost independent of the extraction order due to a dynamic classification strategy employed in the handling of overlapping regression classes. The effectiveness and robustness of the RCMD method are substantiated by a set of simulation experiments and a real-life application showing the way it can be used to fit mixed data to linear regression classes and nonlinear structures in various situations     

A new concept for separability problems in blind source separation

The goal of blind source separation (BSS) lies in recovering the original independent sources of a mixed random vector without knowing the mixing structure. A key ingredient for performing BSS successfully is to know the indeterminacies of the problem-that is, to know how the separating model relates to the original mixing model (separability). For linear BSS, Comon (1994) showed using the Darmois-Skitovitch theorem that the linear mixing matrix can be found except for permutation and scaling. In this work, a much simpler, direct proof for linear separability is given. The idea is based on the fact that a random vector is independent if and only if the Hessian of its logarithmic density (resp. characteristic function) is diagonal everywhere. This property is then exploited to propose a new algorithm for performing BSS. Furthermore, first ideas of how to generalize separability results based on Hessian diagonalization to more complicated nonlinear models are studied in the setting of postnonlinear BSS.     

A new bound for the D0L sequence equivalence problem

The D0L sequence equivalence problem consists of deciding, given two morphisms , and a word , whether or not g ⁱ (w) = h ⁱ (w) for all i ≥ 0. We show that in case of smooth and loop-free morphisms, to decide the D0L sequence equivalence problem, it suffices to consider the terms of the sequences with , where n is the cardinality of X.     

A new concept of the SCARA robot

Based on the SCARA concept, accepted worldwide, this paper considers the possibility of realizing SCARA with a full circle working area. The basis of the approach is a mechanism with two eccentrically positioned rotating discs instead several tools (hands) is also facilitated. This paper analyzes the advantages of the proposed solution and the possibilities of its realization.     

A new concept of compatibility structure in new product development

Notwithstanding the existence of few publications addressing the compatibility issues in new product development, an axiomatic basis supporting this literature and driving new contributions to the subject is still lacking. In this paper, we propose a definition of a compatibility structure that lays down the foundations of an axiomatic basis for modelling compatibility in new product development. Regarding the number of conditions comprised in this definition, a minimal representation of compatibility structure is proposed to ease the use and manipulation of a compatibility structure. The definition of compatibility structure and its minimal representation are inspired by those of preference structure in preference modelling. The similarities and dissimilarities between preference structures and compatibility structures are emphasized. The construction and the characterization of a compatibility structure without incomparability using the proposed definition are provided. In this paper, we also propose a method to evaluate the crisp compatibility relations between two alternatives with respect to attributes/criteria. The compatibility relations are evaluated by investigating the impact that an alternative has on another, and vice-versa with respect to a single attribute/criterion. Future research related to the compatibility structure proposed in this paper is described.