The discriminator lemma is normally used to prove lower bounds for circuits with small-weight threshold gates. In this note we adapt the lemma to circuits with a general (large-weight) threshold gate at the top. The n...
详细信息
The discriminator lemma is normally used to prove lower bounds for circuits with small-weight threshold gates. In this note we adapt the lemma to circuits with a general (large-weight) threshold gate at the top. The new lemma is used to give a new proof of a previously known lower bound for the size of a threshold of parity gates that computes inner product mod 2, and to prove that a small-depth AND-OR circuit for parity must have exponential size even if we allow a threshold gate at the top. The latter result is a generalization to large weights of a result by Green, and depends heavily on Hastad's switching-lemma. (C) 1997 Elsevier science B.V.
The paper outlines a method for designing near optimal nonlinear classifiers based on a self-organizing technique for estimating probability density functions when only weak assumptions are made about the densities. T...
详细信息
The paper outlines a method for designing near optimal nonlinear classifiers based on a self-organizing technique for estimating probability density functions when only weak assumptions are made about the densities. The classical parametric and nonparametric methods for estimating density functions have a number of drawbacks;parametric methods give weak results on unknown distributions, while nonparametric methods require extensive amounts of design samples, storage capacity, and computing power. The present method avoids these disadvantages by parameterizing a set of component densities from which the actual densities are constructed. The parameters of the component densities are optimized by a self-organizing algorithm, reducing to a minimum the labeling of design samples. All the required computations are realized with the simple "sum of product" units commonly used in connectionist models. The density approximations produced by the method are illustrated in two dimensions for a multispectral image classification task. The practical use of the method is illustrated by a small speech recognition problem, that of recognizing 18 Swedish consonants. Related issues of invariant projections, cross-class pooling of data, and subspace partitioning are also discussed.
We prove that maximum H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable graph) is a Max SNP-hard problem for any graph H that has three or m...
详细信息
We prove that maximum H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable graph) is a Max SNP-hard problem for any graph H that has three or more nodes in some connected component. If H is connected and the degrees of the nodes in H are bounded by a constant the problem is Max SNP-complete.
We present a multi-scale representation of grey-level shape, called the scale-space primal sketch, that makes explicit features in scale-space as well as the relations between features at different levels of scale. Th...
详细信息
We present a multi-scale representation of grey-level shape, called the scale-space primal sketch, that makes explicit features in scale-space as well as the relations between features at different levels of scale. The representation gives a qualitative description of the image structure that allows for extraction of significant image structure - stable scales and regions of interest - in a solely bottom-up data-driven manner. Hence, it can be seen as preceding further processing, which can then be properly tuned. Experiments on real imagery demonstrate that the proposed theory gives intuitively reasonable results.
Computer graphics and computer vision deal with converse problems. In graphics the goal is to synthesize the image(s) of a scene from a given description in terms of a model or some observed data. In vision, on the ot...
详细信息
Computer graphics and computer vision deal with converse problems. In graphics the goal is to synthesize the image(s) of a scene from a given description in terms of a model or some observed data. In vision, on the other hand, the aim is to create a description of the world (the scene), given the image(s). Due to this difference of the goals the two fields have developed separately. Nevertheless, they often deal with aspects of the same physical reality. Therefore, many fundamental concepts and problems are shared by the two areas, even though the context may differ. In this paper we discuss some of the issues which unify and discriminate the fields. The purpose is not to present a self-contained presentation of the relevant notions and techniques. We refer to the existing literature for such details. Instead we try to elucidate aspects in which the two fields may benefit from each other and aspects in which this may be difficult.
The cylindrical algebraic decomposition method decomposes E r into regions over which a given polynomial has constant sign by extension of one complicated decomposition of E r-1 . We investigate a method which decompo...
The cylindrical algebraic decomposition method decomposes E r into regions over which a given polynomial has constant sign by extension of one complicated decomposition of E r-1 . We investigate a method which decomposes E r into sign-invariant region by combining several but simpler decompositions of E r-1 . We can obtain a sign-invariaat decomposition of E 2 defined by a bivariate polynomial of total degree n and coefficient size d in time O(n 12 (d + log n) 2 log n) . Preliminary experiments suggest that the method is useful in practice.
The characteristics of a project course (160 h of work for the students) oriented towards graphical interaction is described. Project proposals are presented to the students by researchers from different applications....
详细信息
The characteristics of a project course (160 h of work for the students) oriented towards graphical interaction is described. Project proposals are presented to the students by researchers from different applications. The students get a high degree of freedom during the project and partly as a result of this they are enthusiastic about the work and produce very impressive prototypes which they present at the end of the course. Copyright (C) 1996 Elsevier science Ltd
The edge focusing method produces a series of edge images ranging from coarser to finer scale resolution. The displacements of these extracted edges in this series are discussed. A three-step method of labelling the e...
详细信息
The edge focusing method produces a series of edge images ranging from coarser to finer scale resolution. The displacements of these extracted edges in this series are discussed. A three-step method of labelling the extracted edges as coming from objects or as coming from shadows and other illumination phenomena using this series is tried. More precisely, we show that it seems possible to label edges into the categories ‘diffuse’ and ‘non-diffuse’ from a binary multi-scale representation, i.e. without using the image intensities directly.
We consider Lipschitz-continuous nonlinear maps in finite-dimensional Banach and Hilbert spaces. Boundedness and monotonicity of the operator are characterized quantitatively in terms of certain functionals. These fun...
详细信息
We consider Lipschitz-continuous nonlinear maps in finite-dimensional Banach and Hilbert spaces. Boundedness and monotonicity of the operator are characterized quantitatively in terms of certain functionals. These functionals are used to assess qualitative properties such as invertibility, and also enable a generalization of some well-known matrix results directly to nonlinear operators. Closely related to the numerical range of a matrix, the Gerschgorin domain is introduced for nonlinear operators. This point set in the complex plane is always convex and contains the spectrum of the operator's Jacobian matrices. Finally, we focus on nonlinear operators in Hilbert space and hint at some generalizations of the von Neumann spectral theory.
暂无评论