1,721,067 research outputs found
Using K-Winner Machines for domain analysis
No full textThe K-WinnerMachine (KWM) model combines unsupervised with supervised training paradigms, and builds up a family of nested classifiers that differ in their expected generalization performances. A KWM allows members of the classifier family to reject a test pattern, and predicting the rejection rate is a crucial issue to the ultimate method effectiveness. The aspects involved by the analytical properties of the KWM first drive a theoretical analysis of the rejection performance. Then the paper shows that the KWM classification process can also be profitably used for domain inspection. Novel theorems connect the outputs of KWMs directly to the class-separating boundaries in the data space. Empirical evidence eventually supports the intuitive result that smaller confidence values characterize boundary regions
Quantum-computing optimization for K-Winner Machines
No full textWhile addressing Vector Quantization (VQ) as a general paradigm for data representation, the paper adopts the K-winner Machine model as a case study, which provides a reference for analyzing both theoretical and implementation aspects. The design of vector quantizers often requires that the (often overlooked) dichotomy between ‘analogue’ modeling and ‘digital’ implementation be taken in account. In the case of digital VQ systems, optimal design can bring about NP-hard problems that prove intractable in terms of computational complexity. The paper discusses the possibility of using advanced paradigms such as Quantum Computing for digital optimization processes in order to overcome the limitations of conventional machinery. The presented research provides analytical criteria determining the relative advantages of conventional over quantum-computing approaches
Tuning the distribution dependent prior in the PAC-Bayes framework based on empirical data
No full textIn this paper we further develop the idea that the PAC-Bayes prior can be defined based on the data-generating distribution. In particular, following Catoni [1], we refine some recent generalisation bounds on the risk of the Gibbs Classifier, when the prior is defined in terms of the data generating distribution, and the posterior is defined in terms of the observed one. Moreover we show that the prior and the posterior distributions can be tuned based on the observed samples without worsening the convergence rate of the bounds and with a marginal impact on their constants
A local Vapnik-Chervonenkis complexity
No full textWe define in this work a new localized version of a Vapnik-Chervonenkis (VC) complexity, namely the Local VC-Entropy, and, building on this new complexity, we derive a new generalization bound for binary classifiers. The Local VC-Entropy-based bound improves on the original Vapnik's results because it is able to discard those functions that, most likely, will not be selected during the learning phase. The result is achieved by applying the localization principle to the original global complexity measure, in the same spirit of the Local Rademacher Complexity. By exploiting and improving a recently developed geometrical framework, we show that it is also possible to relate the Local VC-Entropy to the Local Rademacher Complexity by finding an admissible range for one given the other. In addition, the Local VC-Entropy allows one to reduce the computational requirements that arise when dealing with the Local Rademacher Complexity in binary classification problems
Maximal Discrepancy for Support Vector Machines
No full textThe Maximal Discrepancy and the Rademacher Complexity
are powerful statistical tools that can be exploited to obtain reliable, albeit not tight, upper bounds of the generalization error of a classifier. We study the different behavior of the two methods when applied to linear classifiers and suggest a practical procedure to tighten the bounds. The resulting generalization estimation can be succesfully used for classifier model selection
- …
