Ing. Vojtěch Franc, Ph.D.

We propose a novel method for training Convolution Neural Network, named CNN-FQ, which takes a face image and outputs a scalar summary of the image quality. The CNN-FQ is trained from triplets of faces that are automatically labeled based on responses of a pre-trained face matcher. The quality scores extracted by the CNN-FQ are directly linked to the probability that the face matcher incorrectly ranks a randomly selected triplet of faces. We applied the proposed CNN-FQ, trained on CASIA database, for selection of the best quality image from a collection of face images capturing the same identity. The quality of the single face representation was evaluated on 1:1 Verification and 1:N Identification tasks defined by the challenging IJB-B protocol. We show that the recognition performance obtained when using faces selected based on the CNN-FQ scores is significantly higher than what can be achieved by competing state-of-the-art image quality extractors.

We tackle the problem of dominant subject recognition (DSR), which aims at identifying the faces of the subject whose faces appear most frequently in a given collection of images. We propose a simple algorithm solving the DSR problem in a principled way via Bayesian learning. The proposed algorithm has complexity quadratic in the number of detected faces, and it provides labeling of images along with an accurate estimate of the prediction confidence. The prediction confidence permits using the algorithm in semiautomatic mode when only a subset of images with uncertain labels are corrected manually. We demonstrate on a challenging IJB-B database, that the algorithm significantly reduces the number of images that need to be manually annotated to get the perfect performance of face verification and face identification systems using the face database created by the method.

We propose a neural network which takes two inputs, a hair image and a face image, and produces an output image having the hair of the hair image seamlessly merged with the inner face of the face image. Our architecture consists of neural networks mapping the input images into a latent code of a pretrained StyleGAN2 which generates the output high-definition image. We propose an algorithm for training parameters of the architecture solely from synthetic images generated by the StyleGAN2 itself without the need of any annotations or external dataset of hairstyle images. We empirically demonstrate the effectiveness of our method in applications including hair-style transfer, hair generation for 3D morphable models, and hair-style interpolation. Fidelity of the generated images is verified by a user study and by a novel hairstyle metric proposed in the paper.

Structured output classifiers based on the framework of Markov Networks provide a transparent way to model statistical dependencies between output labels. The Markov Network (MN) classifier can be efficiently learned by the maximum margin method, which however requires expensive completely annotated examples. We extend the maximum margin algorithm for learning of unrestricted MN classifiers from examples with partially missing annotation of labels. The proposed algorithm translates learning into minimization of a novel loss function which is convex, has a clear connection with the supervised margin-rescaling loss, and can be efficiently optimized by first-order methods. We demonstrate the efficacy of the proposed algorithm on a challenging structured output classification problem where it beats deep neural network models trained from a much higher number of completely annotated examples, while the proposed method used only partial annotations.

Many real-world classification problems are significantly class-imbalanced to detriment of the class of interest. The standard set of proper evaluation metrics is well-known but the usual assumption is that the test dataset imbalance equals the real-world imbalance. In practice, this assumption is often broken for various reasons. The reported results are then often too optimistic and may lead to wrong conclusions about industrial impact and suitability of proposed techniques. We introduce methods (Supplementary code related to techniques described in this paper is available at: https://github.com/CiscoCTA/nci_eval) focusing on evaluation under non-constant class imbalance. We show that not only the absolute values of commonly used metrics, but even the order of classifiers in relation to the evaluation metric used is affected by the change of the imbalance rate. Finally, we demonstrate that using subsampling in order to get a test dataset with class imbalance equal to the one observed in the wild is not necessary, and eventually can lead to significant errors in classifier’s performance estimate.

In classification with a reject option, the classifier is allowed in uncertain cases to abstain from prediction. The classical cost based model of an optimal classifier with a reject option requires the cost of rejection to be defined explicitly. An alternative bounded-improvement model, avoiding the notion of the reject cost, seeks for a classifier with a guaranteed selective risk and maximal cover. We prove that both models share the same class of optimal strategies, and we provide an explicit relation between the reject cost and the target risk being the parameters of the two models. An optimal rejection strategy for both models is based on thresholding the conditional risk defined by posterior probabilities which are usually unavailable. We propose a discriminative algorithm learning an uncertainty function which preserves ordering of the input space induced by the conditional risk, and hence can be used to construct optimal rejection strategies.

Learning of convolutional neural networks (CNNs) to perform a face recognition task requires a large set of facial images each annotated with a label to be predicted. In this paper we propose a method for learning CNNs from weakly annotated images. The weak annotation in our setting means that a pair of an attribute label and a person identity label is assigned to a set of faces automatically detected in the image. The challenge is to link the annotation with the correct face. The weakly annotated images of this type can be collected by an automated process not requiring a human labor. We formulate learning from weakly annotated images as a maximum likelihood (ML) estimation of a parametric distribution describing the weakly annotated images. The ML problem is solved by an instance of the EM algorithm which in its inner loop learns a CNN to predict attribute label from facial images. Experiments on age and gender estimation problem show that the proposed algorithm significantly outperforms the existing heuristic approach for dealing with this type of data. A practical outcome of our paper is a new annotation of the IMDB database [26] containing 300 k faces each one annotated by biological age, gender and identity labels.

Discretization of continuous input functions into piecewise constant or piecewise linear approximations is needed in many mathematical modeling problems. It has been shown that choosing the length of the piecewise segments adaptively based on data samples leads to improved accuracy of the subsequent processing such as classification. Traditional approaches are often tied to a particular classification model which results in local greedy optimization of a criterion function. This paper proposes a technique for learning the discretization parameters along with the parameters of a decision function in a convex optimization of the true objective. The general formulation is applicable to a wide range of learning problems. Empirical evaluation demonstrates that the proposed convex algorithms yield models with fewer number of parameters with comparable or better accuracy than the existing methods.

The paper proposes Convolutional Neural Network (CNN) for License Plate Recognition (LPR) from low-resolution videos. The CNN accepts arbitrary long sequence of geometrically registered license plate (LP) images and outputs a distribution over a set of strings with an admissible length. Evaluation on 31k low-resolution videos shows that the proposed CNN significantly outperforms both baseline methods and humans by a large margin. Our second contribution is a CNN based super-resolution generator of LP images. The generator converts input low-resolution LP image into its high-resolution counterpart which i) preserves the structure of the input and ii) depicts a string that was previously recognized from video.

We propose a novel two-step convolutional neural network to estimate a heart rate from a sequence of facial images. The network is trained end-to-end by alternating op- timization and validated on three publicly available datasets yielding state-of-the-art results against three baseline methods. The network performs better by a 40% margin to the state-of-the-art method on a newly collected dataset. A challenging dataset of 204 fitness-themed videos is introduced. The dataset is designed to test the robustness of heart rate estimation methods to illumination changes and subject’s motion. 17 subjects perform 4 activities (talking, rowing, exercising on a stationary bike and an elliptical trainer) in 3 lighting setups. Each activity is captured by two RGB web-cameras, one is placed on a tripod, the other is attached to the fitness machine which vibrates significantly. Subject’s age ranges from 20 to 53 years, the mean heart rate is ≈ 110, the standard deviation ≈ 25.

In this paper, we propose a robust and fast transductive support vector machine (RTSVM) classifier that can be applied to large-scale data. To this end, we use the robust Ramp loss instead of Hinge loss for labeled data samples. The resulting optimization problem is non-convex but it can be decomposed to a convex and concave parts. Therefore, the optimization is accomplished iteratively by solving a sequence of convex problems known as concave-convex procedure. Stochastic gradient (SG) is used to solve the convex problem at each iteration, thus the proposed method scales well with large training set size for the linear case (to the best of our knowledge, it is the second transductive classification method that is practical for more than a million data). To extend the proposed method to the nonlinear case, we proposed two alternatives where one uses the primal optimization problem and the other uses the dual. But in contrast to the linear case, both alternatives do not scale well with large-scale data. Experimental results show that the proposed method achieves comparable results to other related transductive SVM methods, but it is faster than other transductive learning methods and it is more robust to the noisy data.

Supervised learning of convolutional neural networks (CNNs) for face recognition requires a large set of facial images each annotated with a single attribute label to be predicted. In this paper we propose a method for learning CNNs from weakly annotated images. The weak annotation in our setting means that a pair of an attribute label and a person identity label is assigned to a set of faces automatically detected in the image. The challenge is to link the annotation with the correct face. The weakly annotated images of this type can be collected by an automated process not requiring a human labor. We formulate learning from weakly annotated images as a maximum likelihood estimation of a parametric distribution describing the data. The ML problem is solved by an instance of EM algorithm which in its inner loop learns a CNN to perform given face recognition task. Experiments on age and gender estimation problem show that the proposed EM-CNN algorithm significantly outperforms the state-of-the-art approach for dealing with this type of data.

The automatic Visual Language IDentification (VLID), i.e. a problem of using visual information to identify the language being spoken, using no audio information, is studied. The proposed method employs facial landmarks automatically detected in a video. A convex optimisation problem to find jointly both the discriminative representation (a softhistogram over a set of lip shapes) and the classifier is formulated. A 10-fold cross-validation is performed on dataset consisting of 644 videos collected from youtube.com resulting in accuracy 73% in a pairwise iscrimination between English and French (50% for a chance).Astudy, inwhich 10 videos were used, suggests that the proposed method performs better than average human in discriminating between the languages.

Statistical learning theory relies on an assumption that the joint distributions of observations and labels are the same in training and testing data. However, this assumption is violated in many real world problems, such as training a detector of malicious network traffic that can change over time as a result of attacker's detection evasion efforts. We propose to address this problem by creating an optimized representation, which significantly increases the robustness of detectors or classifiers trained under this distributional shift. The representation is created from bags of samples (e.g. network traffic logs) and is designed to be invariant under shifting and scaling of the feature values extracted from the logs and under permutation and size changes of the bags. The invariance is achieved by combining feature histograms with feature self-similarity matrices computed for each bag and significantly reduces the difference between the training and testing data. The parameters of the representation, such as histogram bin boundaries, are learned jointly with the classifier. We show that the representation is effective for training a detector of malicious traffic, achieving 90% precision and 67% recall on samples of previously unseen malware variants.

An algorithm for accurate localization of facial landmarks coupled with a head pose estimation from a single monocular image is proposed. The algorithm is formulated as an optimization problem where the sum of individual landmark scoring functions is maximized with respect to the camera pose by fitting a parametric 3D shape model. The landmark scoring functions are trained by a structured output SVM classifier that takes a distance to the true landmark position into account when learning. The optimization criterion is non-convex and we propose a robust initialization scheme which employs a global method to detect a raw but reliable initial landmark position. Self-occlusions causing landmarks invisibility are handled explicitly by excluding the corresponding contributions from the data term. This allows the algorithm to operate correctly for a large range of viewing angles. Experiments on standard ``in-the-wild'' datasets demonstrate that the proposed algorithm outperforms several state-of-the-art landmark detectors especially for non-frontal face images. The algorithm achieves the average relative landmark localization error below 10% of the interocular distance in 98.3% of the 300W dataset test images.

Abstract We propose a real-time multi-view landmark detector based on Deformable Part Models (DPM). The detector is composed of a mixture of tree based DPMs, each component describing landmark configurations in a specific range of viewing angles. The usage of view specific DPMs allows to capture a large range of poses and to deal with the problem of self-occlusions. Parameters of the detector are learned from annotated examples by the Structured Output Support Vector Machines algorithm. The learning objective is directly related to the performance measure used for detector evaluation. The tree based DPM allows to find a globally optimal landmark configuration by the dynamic programming. We propose a coarse-to-fine search strategy which allows real-time processing by the dynamic programming also on high resolution images. Empirical evaluation on “in the wild” images shows that the proposed detector is competitive with the state-of-the-art methods in terms of speed and accuracy yet it keeps the guarantee of finding a globally optimal estimate in contrast to other methods.

New and unseen polymorphic malware, zero-day attacks, or other types of advanced persistent threats are usually not detected by signature-based security devices, firewalls, or anti-viruses. This represents a challenge to the network security industry as the amount and variability of incidents has been increasing. Consequently, this complicates the design of learning-based detection systems relying on features extracted from network data. The problem is caused by different joint distribution of observation (features) and labels in the training and testing data sets. This paper proposes a classification system designed to detect both known as well as previously-unseen security threats. The classifiers use statistical feature representation computed from the network traffic and learn to recognize malicious behavior. The representation is designed and optimized to be invariant to the most common changes of malware behaviors. This is achieved in part by a feature histogram constructed for each group of HTTP flows (proxy log records) of a user visiting a particular hostname and in part by a feature self-similarity matrix computed for each group. The parameters of the representation (histogram bins) are optimized and learned based on the training samples along with the classifiers. The proposed classification system was deployed on large corporate networks, where it detected 2,090 new and unseen variants of malware samples with 90% precision (9 of 10 alerts were malicious), which is a considerable improvement when compared to the current flow-based approaches or existing signature-based web security devices.

We address a problem of learning ordinal classifiers from partially annotated examples. We introduce a V-shaped interval-insensitive loss function to measure discrepancy between predictions of an ordinal classifier and a partial annotation provided in the form of intervals of candidate labels. We show that under reasonable assumptions on the annotation process the Bayes risk of the ordinal classifier can be bounded by the expectation of an associated interval-insensitive loss. We propose several convex surrogates of the interval-insensitive loss which are used to formulate convex learning problems. We described a variant of the cutting plane method which can solve large instances of the learning problems. Experiments on a real-life application of human age estimation show that the ordinal classifier learned from cheap partially annotated examples can achieve accuracy matching the results of the so-far used supervised methods which require expensive precisely annotated examples.

In this paper we study statistical consistency of partial losses suitable for learning structured output predictors from examples containing missing labels. We provide sufficient conditions on data generating distribution which admit to prove that the expected risk of the structured predictor learned by minimizing the partial loss converges to the optimal Bayes risk defined by an associated complete loss. We define a concept of surrogate classification calibrated partial losses which are easier to optimize yet their minimization preserves the statistical consistency. We give some concrete examples of surrogate partial losses which are classification calibrated. In particular, we show that the ramp-loss which is in the core of many existing algorithms is classification calibrated.

In this paper we describe a tracker of facial landmarks submitted to the 300 Videos in the Wild (300-VW) challenge. Our tracker is a straightforward extension of a well tuned tree-based DPM landmark detector originally developed for static images. The tracker is obtained by applying the static detector independently in each frame and using the Kalman filter to smooth estimates of the face positions as well as to compensate possible failures of the face detector. The resulting tracker provides a robust estimate of 68 landmarks running at 5 fps on an ordinary PC. We provide an open-source implementation of the proposed tracker at (http://cmp.felk.cvut.cz/~uricamic/clandmark/).

We address the problem of learning a detector of malicious behavior in network traffic. The malicious behavior is detected based on the analysis of network proxy logs that capture malware communication between client and server computers. The conceptual problem in using the standard supervised learning methods is the lack of sufficiently representative training set containing examples of malicious and legitimate communication. Annotation of individual proxy logs is an expensive process involving security experts and does not scale with constantly evolving malware. However, weak supervision can be achieved on the level of properly defined bags of proxy logs by leveraging internet domain black lists, security reports, and sandboxing analysis. We demonstrate that an accurate detector can be obtained from the collected security intelligence data by using a Multiple Instance Learning algorithm tailored to the Neyman-Pearson problem. We provide a thorough experimental evaluation on a large corpus of network communications collected from various company network environments.

While the problem of facial landmark detection is getting big attention i n the computer vision community recently, most of the methods deal only with near-frontal views and there is only a few really multi-view detectors available, that are capable of detection in a wide range of yaw angle (e.g. $phi in (-90, 90)$). We describe a multi-view facial landmark detector based on the Deformable Part Models, which treats the problem of the simultaneous landmark detection and the viewing angle estimation within a structured output classification framework. We prese nt an easily extensible and flexible framework which provides a real-time performance on the ``in the wild'' images, evaluated on a challenging ``Annotated Facial Landmarks in the Wild'' database. We show that our det ector achieves better results than the current state of the art in terms of the localization error.

A real-time algorithm for accurate localization of facial landmarks in a single monocular image is proposed. The algorithm is formulated as an optimization problem, in which the sum of responses of local classifiers is maximized with respect to the camera pose by fit ting a generic (not a person specific) 3D model. The algorithm simultaneously estimates a head position and orientation and detects the facial landmarks in the image. Despite being local, we show that the basin of attraction is large to the extent it can be initialized by a scannin g window face detector. Other experiments on standard datasets demonstrate that the proposed a lgorithm outperforms a state-of-the-art landmark detector especially for non-frontal face imag es, and that it is capable of reliable and stable tracking for large set of viewing angles.

This paper proposes a novel Fast Algorithm for Structured Ouput LEarning (FASOLE). FASOLE implements the dual coordinate ascent (DCA) algorithm for solving the dual problem of the Structured Output Support Vector Machines (SO-SVM). Unlike existing instances of DCA algorithm applied for SO-SVM, the proposed FASOLE uses a different working set selection strategy which provides nearly maximal improvement of the objective function in each update. FASOLE processes examples in on-line fashion and it provides certificate of optimality. FASOLE is guaranteed to find the {$veps$}-optimal solution in {$SO(frac{1}{veps^2})$} time in the worst case. In the empirical comparison FASOLE consistently outperforms the existing state-of-the-art solvers, like the Cutting Plane Algorithm or the Block-Coordinate Frank-Wolfe algorithm, achieving up to an order of magnitude speedups while obtaining the same precise solution.

We address a problem of learning ordinal classifier from partially annotated examples. We introduce an interval-insensitive loss function to measure discrepancy between predictions of an ordinal classifier and a partial annotation provided in the form of intervals of admissible labels. The proposed interval-insensitive loss is an instance of loss functions previously used for learning of different classification models from partially annotated examples. We propose several convex surrogates of the interval-insensitive loss which can be efficiently optimized by existing solvers. Experiments on standard benchmarks and a real-life application show that ordinal classifiers learned from partially annotated examples can achieve accuracy close to the accuracy of classifiers learned from completely annotated examples.

Discriminative methods for learning structured output classifiers have been gaining popularity in recent years due to their successful applications in fields like computer vision, natural language processing, etc. Learning of the structured output classifiers leads to solving a convex minimization problem, still hard to solve by standard algorithms in real-life settings. A significant effort has been put to development of specialized solvers among which the Bundle Method for Risk Minimization (BMRM) [1] is one of the most successful. The BMRM is a simplified variant of bundle methods well known in the filed of non-smooth optimization. In this paper, we propose two speed-up improvements of the BMRM: i) using the adaptive prox-term known from the original bundle methods, ii) starting optimization from a non-trivial initial solution. We combine both improvements with the multiple cutting plane model approximation [2]. Experiments on real-life data show consistently faster convergence achieving speedup up to factor of 9.7.

In this paper, we consider face detection along with facial landmark localization inspired by the recent studies showing that incorporating object parts improves the detection accuracy. To this end, we train roots and parts detectors where the roots detector returns candidate image regions that cover the entire face, and the parts detector searches for the landmark locations within the candidate region. We use a cascade of binary and one-class type classifiers for the roots detection and SVM like learning algorithm for the parts detection. Our proposed face detector outperforms the most of the successful face detection algorithms in the literature and gives the second best result on all tested challenging face detection databases. Experimental results show that including parts improves the detection performance when face images are large and the details of eyes and mouth are clearly visible, but does not introduce any improvement when the images are small.

We propose a principled approach to supervised learning of facial landmarks detector based on the Deformable Part Models (DPM). We treat the task of landmarks detection as an instance of the structured output classification. To learn the parameters of the detector we use the Structured Output Support Vector Machines algorithm. The objective function of the learning algorithm is directly related to the performance of the detector and controlled by the user-defined loss function, in contrast to the previous works. Our proposed detector is real-time on a standard computer, simple to implement and easily modifiable for detection of various set of landmarks. We evaluate the performance of our detector on a challenging ``Labeled Faces in the Wild'' (LFW) database. The empirical results show that our detector consistently outperforms two public domain implementations based on the Active Appearance Models and the DPM. We are releasing open-source code implementing our proposed detector along with the manual annotation of seven facial landmarks for nearly all images in the LFW database.

We show that classification rules used in ordinal regression are equivalent to a certain class of linear multi-class classifiers. This observation not only allows to design new learning algorithms for ordinal regression using existing methods for multi-class classification but it also allows to derive new models for ordinal regression. For example, one can convert learning of ordinal classifier with (almost) arbitrary loss function to a convex unconstrained risk minimization problem for which many efficient solvers exist. The established equivalence also allows to increase discriminative power of the ordinal classifier without need to use kernels by introducing a piece-wise ordinal classifier. We demonstrate advantages of the proposed models on standard benchmarks as well as in solving a real-life problem. In particular, we show that the proposed piece-wise ordinal classifier applied to visual age estimation outperforms other standard prediction models.

This paper describes statistical models and an efficient Monte-Carlo algorithm for detecting tracks of slowly moving objects in optical telescope imagery sequences. The algorithm is based on accurate robust image pre-registration with respect to the star background, hot/warm pixel suppression, extracting dense normalized local image features, pixelwise statistical event detection, segmentation of event maps to putative image primitives, and finding consistent track sequences composed of the image primitives. Good performance at low SNR and robustness of detection with respect to fast or slow-moving thin overhead clouds is achieved by an event detection model which requires collecting at least 10 images of a particular spatial direction. The method does not degrade due to an accumulation of acquisition artifacts if more images are available. The track sequence detection method is similar in spirit to LINE [Yanagisawa et al, T JPN SOC AERONAUT S 2012]. The detection is performed by the RANSAC robust method modified for a concurrent detection of a fixed number of tracks, followed by an acceptance test based on a maximum posterior probability classifier. The statistical model of an image primitive track is based on the consistence between the size and the inclination angle of the image primitive, its image motion velocity, and the sidereal velocity, together with a consistence in relative magnitude. The method does not presume any particular movements of the object, as long as its motion velocity is constant. It can detect tracks without any constraints on their angular direction or length. The detection does not require repeated image transformations (rotations etc.), which makes it computationally efficient. The detection time is linear in the number of input images and, unlike in the LINE proposal method, the number of RANSAC proposals is (theoretically) independent of the number of putative image primitives. The current (unoptimized) experimental implementation run

We introduce Ravel (Robots with Audiovisual Abilities), a publicly available data set which covers examples of Human Robot Interaction (HRI) scenarios. These scenarios are recorded using the audio-visual robot head POPEYE, equipped with two cameras and four microphones, two of which being plugged into the ears of a dummy head. All the recordings were performed in a standard room with no special equipment, thus providing a challenging indoor scenario. This data set provides a basis to test and benchmark methods and algorithms for audio-visual scene analysis with the ultimate goal of enabling robots to interact with people in the most natural way. The data acquisition setup, sensor calibration, data annotation and data content are fully detailed. Moreover, three examples of using the recorded data are provided, illustrating its appropriateness for carrying out a large variety of HRI experiments. The Ravel data are publicly available at: http://ravel.humavips.eu/.

Cutting plane methods are optimization techniques that incrementally construct an approximation of a feasible set or an objective function by linear inequalities, called cutting planes. Numerous variants of this basic idea are among standard tools used in convex nonsmooth optimization and integer linear programing. Recently, cutting plane methods have seen growing interest in the field of machine learning. In this chapter, we describe the basic theory behind these methods and we show three of their successful applications to solving machine learning problems: regularized risk minimization, multiple kernel learning, and MAP inference in graphical models.

In this paper we describe a detector of facial landmarks based on the Deformable Part Models. We treat the task of landmark detection as an instance of the structured output classification problem. We propose to learn the parameters of the detector from data by the Structured Output Support Vector Machines algorithm. In contrast to the previous works, the objective function of the learning algorithm is directly related to the performance of the resulting detector which is controlled by a user-defined loss function. The resulting detector is real-time on a standard PC, simple to implement and it can be easily modified for detection of a different set of landmarks. We evaluate performance of the proposed landmark detector on a challenging ''''Labeled Faces in the Wild`` (LFW) database. The empirical results demonstrate that the proposed detector is consistently more accurate than two public domain implementations based on the Active Appearance Models and the Deformable Part Models. We provide an open-source implementation of the proposed detector and the manual annotation of the facial landmarks for all images in the LFW database.

Many machine learning algorithms lead to solving a convex regularized risk minimization problem. Despite its convexity the problem is often very demanding in practice due to a high number of variables or a complex objective function. The Bundle Method for Risk Minimization (BMRM) is a recently proposed method for minimizing a generic regularized risk. Unlike the approximative methods, the BMRM algorithm comes with convergence guarantees but it is often too slow in practice. We propose a modified variant of the BMRM algorithm which decomposes the objective function into several parts and approximates each part by a separate cutting plane model instead of a single cutting plane model used in the original BMRM. The finer approximation of the objective function can significantly decrease the number of iterations at the expense of higher memory requirements. A preliminary experimental comparison shows promising results.

During the last decade the super-modular Pair-wise Markov Networks (SM-PMN) have become a routinely used model for structured prediction. Their popularity can be attributed to efficient algorithms for the MAP inference. Comparably efficient algorithms for learning their parameters from data have not been available so far. We propose an instance of the Analytic Center Cutting Plane Method (ACCPM) for discriminative learning of the SM-PMN from annotated examples. We empirically evaluate the proposed ACCPM on a problem of learning the SM-PMN for image segmentation. Results obtained on two public datasets show that the proposed ACCPM significantly outperforms the current state-of-the-art algorithm in terms of computational time as well as the accuracy because it can learn models which were not tractable by existing methods.

We show that learning of a general Markov network can be expressed as a convex optimization problem which is solvable efficiently without calling any external max-sum solver. The key idea is to use a linear programing relaxation of the max-sum problem directly in the formulation of the learning problem. We show that the proposed learning problem can be solved efficiently by the Generalized Proximal Point Algorithm. The empirical evaluation shows that our algorithm speeds up learning of general Markov networks by a factor of up to 20 compared to the ACP algorithm.

We show how the SVM can be viewed as a maximum likelihood estimate of a class of probabilistic models. This model class can be viewed as a reparametrization of the SVM in a similar vein to the v-SVM reparametrizing the classical (C-)SVM. It is not discriminative, but has a non-uniform marginal. We illustrate the benefits of this new view by re-deriving and re-investigating two established SVM-related algorithms.

Clanek popisuje obecny algoritmus pro minimalizaci convexnich problemu, na ktere je prevedeno velke mnostvi problemu strojoveho uceni.

In a variety of applications, kernel machines such as Support Vector Machines (SVMs) have been used with great success often delivering stat e-of-the-art results. Using the kernel trick, they work on several domains and even enable heterogeneous data fusion by concatenating feature spaces or multiple kernel learning. Unfortunately, they are not suited for truly large-scale applications since they suffer from the curse of supporting vectors, i.e., the speed of applying SVMs decays linearly with the number of support vectors. In this paper we develop COFFIN - a new training strategy for linear SVMs that effectively allows the use of on demand computed kernel feature spaces and virtual examples in the primal. With linear training and prediction effort this framework leverages SVM applications to truly large-scale problems: As an example, we train SVMs for human splice site recognition involving 50 million examples and sophisticated string kernels. Additionally, we learn an SVM based gende

We have developed a machine learning toolbox, called SHOGUN, which is designed for unified large-scale learning for a broad range of feature types and learning settings. It offers a considerable number of machine learning models such as support vector machines, hidden Markov models, multiple kernel learning, linear discriminant analysis, and more. Most of the specific algorithms are able to deal with several different data classes. We have used this toolbox in several applications from computational biology, some of them coming with no less than 50 million training examples and others with 7 billion test examples. With more than a thousand installations worldwide, SHOGUN is already widely adopted in the machine learning community and beyond. SHOGUN is implemented in C++ and interfaces to MATLABTM, R, Octave, Python, and has a stand-alone command line interface. The source code is freely available under the GNU General Public License, Version 3 at http://www.shogun-toolbox.org.

We have developed an optimized cutting plane algorithm (OCA) for solving large-scale risk minimization problems. We prove that the number of iterations OCA requires to converge to a epsilon precise solution is approximately linear in the sample size. We also derive OCAS, an OCA-based linear binary SVM solver, and OCAM, a linear multi-class SVM solver. In an extensive empirical evaluation we show that OCAS outperforms current state-of-the-art SVM solvers like svmlight, svmperf and BMRM, achieving speedup factor more than 1,200 over svmlight on some data sets and speedup factor of 29 over svmperf, while obtaining the same precise support vector solution.

In this article, we extend an existing discriminative structured output learning approach to new three classes of max-sum classifiers with an arbitrary neighbourhood structure. We derive learning algorithms for two subclasses of max-sum classifiers whose response can be computed in polynomial time: (i) the max-sum classifiers with supermodular quality functions and (ii) the max-sum classifiers whose response can be computed exactly by a linear programming relaxation. Moreover, we show that the learning problem can be approximately solved even for a general max-sum classifier.

This contribution discusses one aspect of statistical learning and generalization. Theory of learning is very relevant to cognitive systems including cognitive vision. A technique allowing to approximate a huge training set is proposed. The approach aims to represent data in a low dimensional space with possibly minimal representation error which is similar to the Principal Component Analysis (PCA). In contrast to the PCA, the basis vectors of the low dimensional space used for data representation are properly selected vectors from the training set and not as their linear combinations. The basis vectors can be selected by a simple algorithm which has low computational requirements and allows on-line processing of huge data sets. As the computations in the proposed algorithm appear in a form of dot product, kernel methods can be used to cope with non-linear problems. The proposed method was tested to approximate training sets of the Support Vector Machines and Kernel Fisher Linear Discr

We propose a method for segmentation of a line of character in a noisy lov resolution image of a ca license plate. The Hidden Markov Chains are used to model a stochastic relation between an input image and a corresponding character segmentation. The segmentation problem is sxpressed as the maximum a posterionri estimation from set of admissible segmentations.

The paper contributes to the solution of the non-negative least squares problem. We propose a novel sequential coordinat-wise algorithm which is easy to implement and it is able to cope with larte scale problems. We derive stopping conditioons which allow to control te distance of the solution found to the optimal one in terms of the optimized objective function.

We describe solvers for specific quadratic programming (QP) tasks. The QP task becomes challenging when large number of variables is to be optimized. We propose QP solvers which are simple to iplement and still able to cope with problems having hudred thousanda variables.

This contribution builds on M.I. Schlesinger's results. M.I. Schlesinger discovered that in a special case of a statistical model (conditional independence with two hidden states only) the EM algorithm converges to a global extreme. Under the same assumptions we shortened and simplified the proof of global convergence. We also smoothed away two minor imprecisions in the original proof and learned that they do not affect validity.