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.     

Learning graph prototypes for shape recognition

This paper presents some new approaches for computing graph prototypes in the context of the design of a structural nearest prototype classifier. Four kinds of prototypes are investigated and compared: set median graphs, generalized median graphs, set discriminative graphs and generalized discriminative graphs. They differ according to (i) the graph space where they are searched for and (ii) the objective function which is used for their computation. The first criterion allows to distinguish set prototypes which are selected in the initial graph training set from generalized prototypes which are generated in an infinite set of graphs. The second criterion allows to distinguish median graphs which minimize the sum of distances to all input graphs of a given class from discriminative graphs, which are computed using classification performance as criterion, taking into account the inter-class distribution. For each kind of prototype, the proposed approach allows to identify one or many prototypes per class, in order to manage the trade-off between the classification accuracy and the classification time.Each graph prototype generation/selection is performed through a genetic algorithm which can be specialized to each case by setting the appropriate encoding scheme, fitness and genetic operators.An experimental study performed on several graph databases shows the superiority of the generation approach over the selection one. On the other hand, discriminative prototypes outperform the generative ones. Moreover, we show that the classification rates are improved while the number of prototypes increases. Finally, we show that discriminative prototypes give better results than the median graph based classifier.     

基于互信息学习贝叶斯网络等价类*

由数据构造贝叶斯网络结构是NP-难问题,根据互信息和条件独立测试,提出了一种构建最优贝叶斯网络结构的新算法。数值实验表明,新算法能较快地确定出与数据匹配程度最高的网络结构,从而能更高效地学习贝叶斯网络结构。     

Learning shape from shading by a multilayer network

The multilayer feedforward network has often been used for learning a nonlinear mapping based on a set of examples of the input-output data. In this paper, we present a novel use of the network, in which the example data are not explicitly given. We consider the problem of shape from shading in computer vision, where the input (image coordinates) and the output (surface depth) satisfy only a known differential equation. We use the feedforward network as a parametric representation of the object surface and reformulate the shape from shading problem as the minimization of an error function over the network weights. The stochastic gradient and conjugate gradient methods are used for the minimization. Boundary conditions for either surface depth or surface normal (or both) can be imposed by adjusting the same network at different levels. It is further shown that the light source direction can be estimated, based on an initial guess, by integrating the source estimation with the surface estimation. Extensions of the method to a wider class of problems are discussed. The efficiency of the method is verified by examples of both synthetic and real images.     

Learning gains associated with annotation and communication software designed for large undergraduate classes

Abstract The purpose of this study was to explore the potential of annotation and communication software (eFuzion) developed for the improvement of students' learning and to determine the effectiveness of the software. eFuzion is designed to be useful in a significantly large classroom by allowing instructors and teaching assistants to provide immediate responses to students' questions and to provide a broader array of options for the lucid presentation of complex concepts. To determine the effectiveness of the software, two groups that took the same course were compared in terms of their learning scores, one group having used the software, the other having not used it. In the three measures of learning, the students who used the software showed significantly higher learning scores than students who did not use it. In addition, students indicated that they felt closer to the instructor and that their understanding of the lecture material was increased by using the software. The results imply that the software has great potential for improving students' learning when it is appropriately used and free of technical difficulties.     

Learning visual models from shape contours using multiscaleconvex/concave structure matching

A novel approach is proposed for learning a visual model from real shape samples of the same class. The approach can directly acquire a visual model by generalizing the multiscale convex/concave structure of a class of shapes, that is, the approach is based on the concept that shape generalization is shape simplification wherein perceptually relevant features are retained. The simplification does not mean the approximation of shapes but rather the extraction of the optimum scale convex/concave structure common to shape samples of the class. The common structure is obtained by applying the multiscale convex/concave structure-matching method to all shape pairs among given shape samples of the class and by integrating the matching results. The matching method, is applicable to heavily deformed shapes and is effectively implemented with dynamic programming techniques. The approach can acquire a visual model from a few samples without any a priori knowledge of the class. The obtained model is very useful for shape recognition. Results of applying the proposed method are presented     

Conceptual classes and system classes in object databases

In this paper, formal relationships between classes of objects based on semantic data models (i.e. conceptual classes) and classes of objects based on object models (i.e system classes), are established. The proposed method starts from conceptual classes and generates system classes. This method can be employed to implement semantic data models on top of currently available object oriented database systems. As a consequence, the database applications can be specified with the flexibility of a conceptual schema while the obtained implementation exploits the efficiency of an object-oriented database system. Both the correctness and the completeness of our method are demonstrated and a discussion on its complexity is provided. Received January 24, 1992 / March 6, 1997     

Characterizing classes

Class characterization is a key step of object design. It serves two purposes: to clarify at a glance some important aspects of a class's expected behavior and to communicate its design intent to others. Depending on the type of systems we design and build, we naturally find certain characterizations to be more compelling than others. Recognizing and choosing effective characterizations is an essential skill that all class designers should master. In this column, the author introduces several characteristics to classes when trying to understand their nature and purpose.     

Learning to pour with a robot arm combining goal and shape learning for dynamic movement primitives

When describing robot motion with dynamic movement primitives (DMPs), goal (trajectory endpoint), shape and temporal scaling parameters are used. In reinforcement learning with DMPs, usually goals and temporal scaling parameters are predefined and only the weights for shaping a DMP are learned. Many tasks, however, exist where the best goal position is not a priori known, requiring to learn it. Thus, here we specifically address the question of how to simultaneously combine goal and shape parameter learning. This is a difficult problem because learning of both parameters could easily interfere in a destructive way. We apply value function approximation techniques for goal learning and direct policy search methods for shape learning. Specifically, we use “policy improvement with path integrals” and “natural actor critic” for the policy search. We solve a learning-to-pour-liquid task in simulations as well as using a Pa10 robot arm. Results for learning from scratch, learning initialized by human demonstration, as well as for modifying the tool for the learned DMPs are presented. We observe that the combination of goal and shape learning is stable and robust within large parameter regimes. Learning converges quickly even in the presence of disturbances, which makes this combined method suitable for robotic applications.     

Efficient shape matching using shape contexts

We demonstrate that shape contexts can be used to quickly prune a search for similar shapes. We present two algorithms for rapid shape retrieval: representative shape contexts, performing comparisons based on a small number of shape contexts, and shapemes, using vector quantization in the space of shape contexts to obtain prototypical shape pieces.     

Unifying classes and processes

Previously, we presented Circus, an integration of Z, CSP, and Morgan’s refinement calculus, with a semantics based on the unifying theories of programming. Circus provides a basis for development of state-rich concurrent systems; it has a formal semantics, a refinement theory, and a development strategy. The design of Circus is our solution to combining data and behavioural specifications. Here, we further explore this issue in the context of object-oriented features. Concretely, we present an object-oriented extension of Circus called OhCircus. We present its syntax, describe its semantics, explain the formalisation of method calls, and discuss our approach to refinement.     

Learnability of automatic classes

The present work initiates the study of the learnability of automatic indexable classes which are classes of regular languages of a certain form. Angluin?s tell-tale condition characterises when these classes are explanatorily learnable. Therefore, the more interesting question is when learnability holds for learners with complexity bounds, formulated in the automata–theoretic setting. The learners in question work iteratively, in some cases with an additional long-term memory, where the update function of the learner mapping old hypothesis, old memory and current datum to new hypothesis and new memory is automatic. Furthermore, the dependence of the learnability on the indexing is also investigated. This work brings together the fields of inductive inference and automatic structures.