Binary statistical decision making involves choosing between two states based on statistical evidence. The optimal decision strategy is typically formulated through a constrained optimization problem, where both the objective and constraints are expressed as integrals involving two Lebesgue measurable functions, one of which represents the strategy being optimized. In this work, we present a comprehensive formulation of the binary decision making problem and provide a detailed characterization of the optimal solution. Our framework encompasses a wide range of well-known and recently proposed decision making problems as specific cases. We demonstrate how our generic approach can be used to derive the optimal decision strategies for these diverse instances. Our results offer a robust mathematical tool that simplifies the process of solving both existing and novel formulations of binary decision making problems which are in the core of many Machine Learning algorithms.

It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.

In classification with a reject option, the classifier is allowed in uncertain cases to abstain from prediction. The classical cost-based model of a reject option classifier requires the rejection cost to be defined explicitly. The alternative bounded-improvement model and the bounded-abstention model avoid the notion of the reject cost. The bounded-improvement model seeks a classifier with a guaranteed selective risk and maximal cover. The bounded-abstention model seeks a classifier with guaranteed cover and minimal selective risk. We prove that despite their different formulations the three rejection models lead to the same prediction strategy: the Bayes classifier endowed with a randomized Bayes selection function. We define the notion of a proper uncertainty score as a scalar summary of the prediction uncertainty sufficient to construct the randomized Bayes selection function. We propose two algorithms to learn the proper uncertainty score from examples for an arbitrary black-box classifier. We prove that both algorithms provide Fisher consistent estimates of the proper uncertainty score and demonstrate their efficiency in different prediction problems, including classification, ordinal regression, and structured output classification.

It is well-known that for general convex optimization problems, block-coordinate descent can get stuck in poor local optima. Despite that, versions of this method known as convergent message passing are very successful to approximately solve the dual LP relaxation of the MAP inference problem in graphical models. In attempt to identify the reason why these methods often achieve good local minima, we argue that if in block-coordinate descent the set of minimizers over a variable block has multiple elements, one should choose an element from the relative interior of this set. We show that this rule is not worse than any other rule for choosing block-minimizers. Based on this observation, we develop a theoretical framework for block-coordinate descent applied to general convex problems. We illustrate this theory on convergent message-passing methods.

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.

We study the task of document layout analysis based on two-dimensional context-free grammars. We first identify a subclass of the grammars sufficient for a document structure description where productions follow a mechanism inducing regular languages in the case of one-dimensional productions. We then show that properties of such grammars can be conveniently utilized to implement a very fast top-down parser. Experimental results are reported for PDF documents, which are chosen as a test domain since we are motivated by a development of digital document access methods for people with disabilities in which a retrieval of structural information plays an important role.

We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is as hard as solving the general LP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation of each of these problems. This result poses a fundamental limitation for designing efficient algorithms to solve the LP relaxations, because finding such an algorithm might improve the complexity of best known algorithms for the general LP. Besides linear-time reductions, we show that the LP relaxations of the considered problems are P-complete under log-space reduction, therefore also hard to parallelize.

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).

We experiment with off-line recognition of handwritten flowcharts based on strokes reconstruction and our state-of-the-art on-line diagram recognizer. A simple baseline algorithm for strokes reconstruction is presented and necessary modifications of the original recognizer are identified. We achieve very promising results on a flowcharts database created as an extension of our previously published on-line database.

We show how the simplex algorithm can be tailored to the linear programming relaxation of pairwise energy minimization with binary variables. A special structure formed by basic and nonbasic variables in each stage of the algorithm is identified and utilized to perform the whole iterative process combinatorially over the input energy minimization graph rather than algebraically over the simplex tableau. This leads to a new efficient solver. We demonstrate that for some computer vision instances it performs even better than methods reducing binary energy minimization to finding maximum flow in a network.

This paper deals with recognition of arrows in online sketched diagrams. Arrows have varying appearance and thus it is a difficult task to recognize them directly. It is beneficial to detect arrows after other symbols (easier to detect) are already found. We proposed [4] an arrow detector which searches for arrows as arbitrarily shaped connectors between already found symbols. The detection is done two steps: a) a search for a shaft of the arrow, b) a search for its head. The first step is relatively easy. However, it might be quite difficult to find the head reliably. This paper brings two contributions. The first contribution is a design of an arrow recognizer where the head is detected using relative strokes positioning. We embedded this recognizer into the diagram recognition pipeline proposed earlier [4] and increased the overall accuracy. The second contribution is an introduction of a new approach to evaluate the relative position of two given strokes with neural networks (LSTM). This approach is an alternative to the fuzzy relative positioning proposed by Bout ruche et al. [2]. We made a comparison between the two methods through experiments performed on two datasets for two different tasks. First, we used a benchmark database of hand-drawn finite automata to evaluate detection of arrows. Second, we used a database presented in the paper by Bout ruche et al. containing pairs of reference and argument strokes, where argument strokes are classified into 18 classes. Our method gave significantly better results for the first task and comparable results for the second task.

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

We present our recent model of a diagram recognition engine. It extends our previous work which approaches the structural recognition as an optimization problem of choosing the best subset of symbol candidates. The main improvement is the integration of our own text separator into the pipeline to deal with text blocks occurring in diagrams. Second improvement is splitting the symbol candidates detection into two stages: uniform symbols detection and arrows detection. Text recognition is left for post processing when the diagram structure is already known. Training and testing of the engine was done on a freely available benchmark database of flowcharts. We correctly segmented and recognized 93.0% of the symbols having 55.1% of the diagrams recognized without any error. Considering correct stroke labeling, we achieved the precision of 95.7%. This result is superior to the state-of-the-art method with the precision of 92.4%. Additionally, we demonstrate the generality of the proposed method by adapting the system to finite automata domain and evaluating it on own database of such diagrams.

The work addresses the problem of clothing perception and manipulation by a two armed industrial robot aiming at a real-time automated folding of a piece of garment spread out on a flat surface. A complete solution combining vision sensing, garment segmentation and understanding, planning of the manipulation and its real execution on a robot is proposed. A new polygonal model of a garment is introduced. Fitting the model into a segmented garment contour is used to detect garment landmark points. It is shown how folded variants of the unfolded model can be derived automatically. Universality and usefulness of the model is demonstrated by its favorable performance within the whole folding procedure which is applicable to a variety of garments categories (towel, pants, shirt, etc.) and evaluated experimentally using the two armed robot. The principal novelty with respect to the state of the art is in the new garment polygonal model and its manipulation planning algorithm which leads to the speed up by two orders of magnitude.

We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the min-sum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time represent able by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.

This work deals with the on-line recognition of hand-drawn graphical sketches with structure. We present a novel approach, in which the search for a suitable interpretation of the input is formulated as a combinatorial optimization task - the max-sum problem. The recognition pipeline consists of two main stages. First, groups of strokes possibly representing symbols of a sketch (symbol candidates) are segmented and relations between them are detected. Second, a combination of symbol candidates best fitting the input is chosen by solving the optimization problem. We focused on flowchart recognition. Training and testing of our method was done on a freely available benchmark database. We correctly segmented and recognized 82.7% of the symbols having 31.5% of the diagrams recognized without any error. It indicates that our approach has promising potential and can compete with the state-of-the-art methods.

This paper announces a ground truthed database of on-line handwritten mathematical formulae. It have recently been collected in our group in connection with the research on methods for structural pattern recognition. Unlike the availability of handwritten characters or texts, collections of structural objects are rather scarce, thus we would like to provide them to the community. We also present the methodology and tools used for data acquisition. Finally, we report on our experiment with the automatic generation of additional samples. The process utilizes the dataset to extract statistical descriptions of symbols alignments and relative sizes.

We present a generic framework that can be used for an easy integration of editing and visualization support for a programming language or files with a structure into NetBeans IDE. Needed features are defined using a simple declarative language. It is also possible to provide custom Java methods to enhance the definition's capabilities. The concept aims at good maintenance and performance of implemented languages. We proved it to work well by integrating over twenty languages.

We present a method for off-line mathematical formulae recognition based on the structural construction paradigm and two-dimensional grammars. In general, this approach can be successfully used in the analysis of images containing objects that exhibit rich structural relations. An important benefit of the structural construction is in treating the symbol segmentation in the image and its structural analysis as a single intertwined process. This allows the system to avoid errors usually appearing during the segmentation phase. We have developed and tested a pilot study proving that the method is computationally efficient, practical and able to cope with noise.