25642875
Approximate Maximum Entropy Joint Feature Inference Consistent with Arbitrary Lower-Order Probability Constraints: Application to Statistical Classification
We propose a new learning method for discrete space statistical classifiers. Similar to Chow and Liu (1968) and Cheeseman (1983), we cast classification/inference within the more general framework of estimating the joint probability mass function (p.m.f.) for the (feature vector, class label) pair. Cheeseman's proposal to build the maximum entropy (ME) joint p.m.f. consistent with general lower-order probability constraints is in principle powerful, allowing general dependencies between features. However, enormous learning complexity has severely limited the use of this approach. Alternative models such as Bayesian networks (BNs) require explicit determination of conditional independencies. These may be difficult to assess given limited data. Here we propose an approximate ME method, which, like previous methods, incorporates general constraints while retaining quite tractable learning. The new method restricts joint p.m.f. support during learning to a small subset of the full feature space. Classification gains are realized over dependence trees, tree-augmented naive Bayes networks, BNs trained by the Kutato algorithm, and multilayer perceptrons. Extensions to more general inference problems are indicated. We also propose a novel exact inference method when there are several missing features.
11687326
An Information-theoretic Learning Algorithm for Neural Network Classification
A new learning algorithm is developed for the design of statistical classifiers minimizing the rate of misclassification. The method, which is based on ideas from information theory and analogies to statistical physics, assigns data to classes in probability. The distributions are chosen to minimize the expected classification error while simultaneously enforcing the classifier's structure and a level of "randomness" measured by Shannon's entropy. Achievement of the classifier structure is quantified by an associated cost. The constrained optimization problem is equivalent to the minimization of a Helmholtz free energy, and the resulting optimization method is a basic extension of the deterministic annealing algorithm that explicitly enforces structural constraints on assignments while reducing the entropy and expected cost with temperature. In the limit of low temperature, the error rate is minimized directly and a hard classifier with the requisite structure is obtained. This learning algorithm can be used to design a variety of classifier structures. The approach is compared with standard methods for radial basis function design and is demonstrated to substantially outperform other design methods on several benchmark examples, while often retaining design complexity comparable to, or only moderately greater than that of strict descent-based methods.
22360460
Entropy-constrained tree-structured vector quantizer design
Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.
17425751
A Mixture of Experts Classifier with Learning Based on Both Labelled and Unlabelled Data
We address statistical classifier design given a mixed training set consisting of a small labelled feature set and a (generally larger) set of unlabelled features. This situation arises, e.g., for medical images, where although training features may be plentiful, expensive expertise is required to extract their class labels. We propose a classifier structure and learning algorithm that make effective use of unlabelled data to improve performance. The learning is based on maximization of the total data likelihood, i.e. over both the labelled and unlabelled data subsets. Two distinct EM learning algorithms are proposed, differing in the EM formalism applied for unlabelled data. The classifier, based on a joint probability model for features and labels, is a "mixture of experts" structure that is equivalent to the radial basis function (RBF) classifier, but unlike RBFs, is amenable to likelihood-based training. The scope of application for the new method is greatly extended by the observation that test data, or any new data to classify, is in fact additional, unlabelled data - thus, a combined learning/classification operation - much akin to what is done in image segmentation - can be invoked whenever there is new data to classify. Experiments with data sets from the UC Irvine database demonstrate that the new learning algorithms and structure achieve substantial performance gains over alternative approaches.
27853952
A non-greedy approach to tree-structured clustering
Abstract We propose a new interdisciplinary approach for the hard optimization problem of tree-structured clustering, wherein the imposition of structural constraints on the solution drastically reduces the complexity of classifying data. The method, derived with analogy to statistical physics, performs a global optimization over the entire tree. Experimentation with non-trivial examples shows that our approach consistently outperforms greedy methods and avoids local minima that may trap them.
26607
Firehose Architectures for Free-Space Optically Interconnected VLSI Circuits
Free-space optical interconnects will soon be able to provide input/output bandwidths to a VLSI chip in excess of a terabit per second. The successful application of this technology to parallel distributed processing systems depends on the development of high-bandwidth interconnects and the ability of the architecture to sustain a stream of data at these bandwidths to the processing elements. We review examples of computational tasks that require scalable input/output, that is, computations where the I/O bandwidth of a processing element must grow in proportion to its computational bandwidth. We present several classes of optoelectronic architectures that can support a high-bandwidth data firehose and mention applications in switching, FFT, sorting, matrix?vector processing, database search, and processor-to-memory interconnect.
2634305
Deadlines, Travel Time, and Robot Problem Solving
1 Abstract This paper describes some extensions to the reductionist planning paradigm typified by Sacerdoti's NOAH program. Certain inadequacies of the partial ordering scheme used in NOAH are pointed out and a new architecture is detailed which circumvents these problems. An example from the semi-automated factory domain is used to illustrate features of the new planner. Techniques for eliminating unnecessary travel time by the robot and avoiding backtracking due to deadline failures are discussed and their incorporation in the planner is described. 2 Introduction Most planners since NOAH [8] have represented a plan for a set of tasks as a partial (ie., non-linear) ordering of the steps required for carrying out those tasks. NOAH and its successors (eg., NONLIN [9] and DEVISER [10]) employ a partially ordered network of tasks to avoid early and unnecessary commitment to task orderings. The motivation for this is to eliminate backtrack-ing. However, maintaining a consistent partial order is difficult in domains where the fact that tasks actually take time plays an important role: domains in which deadlines or robot travel time are serious considerations. That a partial order leads unavoidably to a deadline failure usually cannot be discovered until an attempt is made to linearize the ordering. However, failure to notice a deadline violation early will require backtracking later. In addition, planning with a partial order is not well suited to efficiently managing factors like travel or machine running time. It's not difficult to represent that moving from one workstation to another takes time proportional to the distance separating the two workstations. However, generating a plan that eliminates unnecessary travel between workstations requires exploring some of the linearized task orderings. It is not until tasks are completely ordered that the source and destination workstations of each movement can be known and the travel time computed with any accuracy. In this paper we describe an approach to planning that combines the use of a partial order with a method for exploring the possible repercussions of that partial order. This approach has been implemented in the FORBIN planner (First Order RoBot INtender). FORBIN is a planner capable of solving a significantly wider class of problems than any of its predecessors. 2.1 The Factory Domain One problem domain that has been used for exploring our approach to planning is what we refer to as the semi-automated factory. In this domain a mobile robot operator wanders about the …
9016351
A framework for evaluating computer supported collaborative learning
Starting from some central issues of Information and Communications Technology (ICT) in learning and of collaborative learning, this paper postulates a composite framework for evaluating learning environments. Using the framework, one scenario is described and analysed. The framework identifies where ICT in learning (e-learning) may be enhanced and where ICT may be difficult for students. Some conclusions are made relevant to the design of ICT learning environments. Areas for future research are suggested.
10025794
Higher-Order Quantification and Proof Search
Logical equivalence between logic programs that are first-order logic formulas holds between few logic programs, partly because first-order logic does not allow auxiliary programs and data structures to be hidden. As a result of not having such abstractions, logical equivalence will force these auxiliaries to be present in any equivalence program. Higher-order quantification can be use to hide predicates and function symbols. If such higher-order quantification is restricted so that operationally, only hiding is specified, then the cost of such higher-order quantifiers within proof search can be small: one only needs to deal with adding new eigenvariables and clauses involving such eigenvariables. On the other hand, the specification of hiding via quantification can allow for novel and interesting proofs of logical equivalence between programs. This paper will present several example of how reasoning directly on a logic program can benefit significantly if higher-order quantification is used to provide abstractions.
15032028
Higher-order Horn clauses
A generalization of Horn clauses to a higher-order logic is described and examined as a basis for logic programming. In qualitative terms, these higher-order Horn clauses are obtained from the first-order ones by replacing first-order terms with simply typed λ-terms and by permitting quantification over all occurrences of function symbols and some occurrences of predicate symbols. Several proof-theoretic results concerning these extended clauses are presented. One result shows that although the substitutions for predicate variables can be quite complex in general, the substitutions necessary in the context of higher-order Horn clauses are tightly constrained. This observation is used to show that these higher-order formulas can specify computations in a fashion similar to first-order Horn clauses. A complete theorem-proving procedure is also described for the extension. This procedure is obtained by interweaving higher-order unification with backchaining and goal reductions, and constitutes a higher-order generalization of SLD-resolution. These results have a practical realization in the higher-order logic programming language called λProlog.