Algorithms for finding logical regularities in pattern recognition

Three algorithms for finding logical regularities of classes in the precedent-based recognition problem are proposed. Logical regularities of classes are defined as conjunctions of special oneplace predicates that determine the membership of a value of a feature in a certain interval of the real axis. The conjunctions are true on as large subsets of reference objects of a certain class as possible. The problem of finding logical regularities is formulated as a special integer programming problem. Relaxation, genetic, and combinatorial algorithms are proposed for solving this problem. Comparison results for these algorithms using model and real-time problems are presented. Comparison results for various estimate evaluation recognition algorithms that use logical regularities of classes in voting procedures are also presented.     

On the construction of irredundant coverings of an integer matrix

New estimates are derived for the computational complexity of the problem of constructing irredundant coverings of an integer matrix (search for maximal conjunctions of a special logical function).     

Vectors of indicators and pointer function in the Multistage Bipolar Method

The Multistage Bipolar Method considered in the paper deals with multistage decision processes. Multistage alternatives are not compared directly to each other, but they are confronted with the stage sets of reference objects—desirable and non-acceptable. In the paper vectors and pointer functions are defined. The aim of the paper is to apply them to classify and rank multistage alternatives and search for the final solution. Our method simplifies the procedure of finding the final solution and allows to use single criterion dynamic programming to solve the problem.

     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

Formalization of a synthesis problem and methods for its solution

A formal formulation is proposed for the synthesis problem of finding objects with certain properties described only by a collection of precedents. A key feature of this formalization is that it is closely related to the pattern recognition theory. A general approach to solving the synthesis problem is described, and particular solution methods are presented in two important cases. For this purpose, a new recognition method is proposed that exhibits a high speed as applied to the data of the structure under study. The performance of the methods is demonstrated on actual data.     

Algorithms for generalized halfspace range searching and other intersection searching problems

In a generalized intersection searching problem, a set S of colored geometric objects is to be preprocessed so that, given a query object q, the distinct colors of the objects of S that are intersected by q can be reported or counted efficiently. These problems generalize the well-studied standard intersection searching problems and have many applications. Unfortunately, the solutions known for the standard problems do not yield efficient solutions to the generalized problems. Recently, efficient solutions have been given for generalized problems where the input and query objects are iso-oriented (i.e., axes-parallel) or where the color classes satisfy additional properties (e.g., connectedness). In this paper, efficient algorithms are given for several generalized problems involving objects that are not necessarily iso-oriented. These problems include: generalized halfspace range searching in , for any fixed d ≥ 2, and segment intersection searching, triangle stabbing, and triangle range searching in for certain classes of line segments and triangles. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.     

Sharp upper global a posteriori error estimates for nonlinear elliptic variational problems

The paper is devoted to the problem of verification of accuracy of approximate solutions obtained in computer simulations. This problem is strongly related to a posteriori error estimates, giving computable bounds for computational errors and detecting zones in the solution domain where such errors are too large and certain mesh refinements should be performed. A mathematical model embracing nonlinear elliptic variational problems is considered in this work. Based on functional type estimates developed on an abstract level, we present a general technology for constructing computable sharp upper bounds for the global error for various particular classes of elliptic problems. Here the global error is understood as a suitable energy type difference between the true and computed solutions. The estimates obtained are completely independent of the numerical technique used to obtain approximate solutions, and are sharp in the sense that they can be, in principle, made as close to the true error as resources of the used computer allow. The latter can be achieved by suitably tuning the auxiliary parameter functions, involved in the proposed upper error bounds, in the course of the calculations.     

Inverse problems for elliptic equations in the space: I

We consider inverse problems of finding the right-hand side of a linear secondorder elliptic equation of general form. We study the first boundary value problem. Two ways of representation of the additional information (over-determination) are considered: specification of the trace of the solution of the boundary value problem inside the domain on some manifold of smaller dimension and specification of values of the normal derivative on a part of the boundary. The Fredholm alternative is proved for the considered problems. Stability estimates are given for the case of unique solvability. The analysis is performed in classes of continuous functions whose derivatives satisfy the Hölder condition.     

Algorithm for choosing conjunctions for logical recognition methods

A new family of recognition algorithms for problems with binary information is constructed. A natural method is proposed for ordering conjunctions used in pattern recognition problems in the standard formulation and with binary features.     

Asymptotic estimates for the number of solutions of the dualization problem and its generalizations

Asymptotic estimates for the typical number of irreducible coverings and the typical length of an irreducible covering of a Boolean matrix are obtained in the case when the number of rows is no less than the number of columns. As a consequence, asymptotic estimates are obtained for the typical number of maximal conjunctions and the typical rank of a maximal conjunction of a monotone Boolean function of variables defined by a conjunctive normal form of clauses. Similar estimates are given for the number of irredundant coverings and the length of an irredundant covering of an integer matrix (for the number of maximal conjunctions and the rank of a maximal conjunction of a two-valued logical function defined by its zero set). Results obtained previously in this area are overviewed.     

Book review

The concept of antagonistic games for classical discrete control problems is applied and new classes of zero-sum dynamic games on networks are formulated and studied. Polynomial-time algorithms for solving max–min paths problem on networks are proposed and their applications (which might occur within certain financial applications) for solving max–min control problems and determining optimal strategies in zero-sum cyclic games are described. In addition max–min control problems with infinite time horizons which lead to cyclic games are studied and polynomial-time algorithm for solving zero value cyclic games is proposed.     

基于对象多属性差异的灰色发展聚类方法及应用

在现实决策问题中,决策对象在不同时期行为状态和所属类型往往呈现一定的发展规律,而现有聚类方法难以充分挖掘聚类对象的发展信息、对象间的关系信息和发展属性的差异信息。为有效处理此类问题,考虑到研究对象的发展趋势、发展行为和发展绝对量与增长量的属性差异,采用GM(1,1)和灰色定权聚类方法,构建了基于对象多属性差异的灰色发展聚类方法,并以我国区域高新技术产业化聚类评估问题为例验证了模型的有效性与合理性。结果表明,所构建模型能够有效描述研究对象呈现发展趋势或未来行为,并实现对研究对象的有效聚类。     

On the relationship between markov strategies in multistep search games and probability distributions

A certain statement of a matrix antagonistic game, commonly encountered in discrete problems of search of objects, is considered. The statement enables one to find strategies that reduce a multistep search problem to a sequence of related one-step matrix games. Bibliography: 5 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 80, 1996, pp. 119–126.     

An introduction to the perplex number system

The perplex number system is a generalization of the abstract logical relationships among electrical particles. The inferential logic of the new number system is homologous to the inferential logic of the progression of the atomic numbers. An electrical progression is defined categorically as a sequence of objects with teridentities. Each identity infers corresponding values of an integer, units and a correspondence relation between each unit and its integer. Thus, in this logical system, each perplex numeral contains an exact internal representational structure; it carries an internal message. This structure is a labeled bipartite graph that is homologous to the internal electrical structure of a chemical atom. The formal logical operations are conjunctions and disjunctions. Combinations of conjunctions and disjunctions compose the spatiality of objects. Conjunctions may include the middle term of pairs of propositions with a common term, thereby creating new information. The perplex numerals are used as a universal source of diagrams.The perplex number system, as an abstract generalization of concrete objects and processes, constitutes a new exact notation for chemistry without invoking alchemical symbols. Practical applications of the number system to concrete objects (chemical elements, simple ions and molecules, and the perplex isomers, ethanol and dimethyl ether) are given. In conjunction with the real number system, the relationships between the perplex number system and scientific theories of concrete systems (thermodynamics, intra-molecular dynamics, molecular biology and individual medicine) are described.     

Budgeting with bounded multiple-choice constraints

We consider a budgeting problem where a specified number of projects from some disjoint classes has to be selected such that the overall gain is largest possible, and such that the costs of the chosen projects do not exceed a fixed upper limit. The problem has several application in government budgeting, planning, and as relaxation from other combinatorial problems. It is demonstrated that the problem can be transformed to an equivalent multiple-choice knapsack problem through dynamic programming. A naive transformation however leads to a drastic increase in the number of variables, thus we propose an algorithm for the continuous problem based on Dantzig–Wolfe decomposition. A master problem solves a continuous multiple-choice knapsack problem knowing only some extreme points in each of the transformed classes. The individual subproblems find extreme points for each given direction, using a median search algorithm. An integer optimal solution is then derived by using the dynamic programming transformation to a multiple-choice knapsack problem for an expanding core. The individual classes are considered in an order given by their gradients, and the transformation to a multiple-choice knapsack problem is performed when needed. In this way, only a dozen of classes need to be transformed for standard instances from the literature. Computational experiments are presented, showing that the developed algorithm is orders of magnitude faster than a general LP/MIP algorithm.     

Parametric linear programming and cluster analysis

In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed in different groups. For certain classes of the problem or, under certain assumptions, the partitioning exercise can be formulated as a sequence of linear programs (LPs), each with a parametric objective function. Such LPs can be solved using the parametric linear programming procedure developed by Gass and Saaty [(Gass, S., Saaty, T. (1955), Naval Research Logistics Quarterly 2, 39–45)]. In this paper, a parametric linear programming model for solving cluster analysis problems is presented. We show how this model can be used to find optimal solutions for certain variations of the clustering problem or, in other cases, for an approximation of the general clustering problem.     

Supervised fuzzy pattern recognition

This paper is devoted to the problem of supervised fuzzy pattern recognition. The cases with non-fuzzy and fuzzy labels are considered. Based on the properties of linearly separable fuzzy classes, some algorithms are proposed for building matching functions of these classes. All algorithms are computer oriented and can be implemented for the automatic recognition of fuzzy patterns.     

Two-sided a posteriori estimates for a generalized Stokes problem

The paper is concerned with a three-field statement of a generalized Stokes problem related to viscous flow problems for fluids with polymeric chains. For homogeneous Dirichlét boundary conditions, this model and respective numerical methods have been studied previously. In the present paper, a generalized Stokes problem with variable viscosity and nonhomogeneous Dirichlét or mixed Dirichlét/Neumann boundary conditions is considered, and functional a posteriori error estimates for the velocity, pressure, and stress fields are derived. The estimates are practically computable, sharp (i.e., have no gap between the left- and right-hand sides), and are valid for arbitrary functions from respective functional classes. The estimates are obtained by transformations of the integral identity that assigns the generalized solution (this method was suggested and used earlier for certain classes of elliptic type problems). Error majorants are weighted sums of terms penalizing violations of the constitutive, equilibrium, and divergence relations with weights determined by the constants in the Friederichs inequality and the inf-sup (LBB) condition. Bibliography: 53 titles. Dedicated to the jubilee of Professor V. A. Solonnikov Published in Zapiski Nauchnykh Seminarov POMI, Vol. 362, 2008, pp. 272–302.     

椭圆方程在Orlicz类中的正则估计(英文)

The purpose of this paper is to give the element proof of the regularity estimates in Orlicz classes for the second order derivatives of the solutions to the general second order elliptic equations.The global regularities in Orlicz for the second order derivatives of the solutions of the Dirichlet problems are also given.