有理高斯函数曲线模拟技术

讨论了有理高斯函数曲线模拟技术。通过控制点位置和权值节点分布以及高斯标准误差来控制曲线形状。对于给定的插值点,根据曲线封闭和不封闭两种情况,分别反向求出控制点,并给出相应高斯标准误差的估计值。在此基础上,运用高斯函数曲线模拟技术对直线、圆进行模拟,并给出最大误差。     

Approximate Comparison of Functions Computed by Distance Automata

Distance automata are automata weighted over the semiring \((\mathbb {N}\cup \{\infty \},\min , +)\) (the tropical semiring). Such automata compute functions from words to \(\mathbb {N}\cup \{\infty \}\). It is known from Krob that the problems of deciding ‘ f≤g’ or ‘ f=g’ for f and g computed by distance automata is an undecidable problem. The main contribution of this paper is to show that an approximation of this problem is decidable. We present an algorithm which, given ε>0 and two functions f,g computed by distance automata, answers “yes” if f≤(1?ε)g, “no” if f≦?g, and may answer “yes” or “no” in all other cases. The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation of the closure under products of sets of matrices over the tropical semiring. Lastly, our theorem of affine domination gives better bounds on the precision of known decision procedures for cost automata, when restricted to distance automata.     

构造前向神经网络逼近多项式函数

首先用构造性的方法证明:对于任意的n阶多元多项式函数,可以构造一个三层前向神经网络以任意精度逼近该多项式,所构造网络的隐层节点个数仅与多项式的维数d和阶数n有关.然后,我们给出实现这一逼近的具体算法.最后,给出两个算例进一步验证所得的理论结果.本文结果对神经网络逼近多元多项式函数的具体网络构造以及实现这一逼近的方法等问题具有指导意义.     

The Relative Complexity of Approximate Counting Problems

Two natural classes of counting problems that are interreducible under approximation-preserving reductions are: (i) those that admit a particular kind of efficient approximation algorithm known as an “FPRAS”, and (ii) those that are complete for #P with respect to approximation-preserving reducibility. We describe and investigate not only these two classes but also a third class, of intermediate complexity, that is not known to be identical to (i) or (ii). The third class can be characterised as the hardest problems in a logically defined subclass of #P.     

The Relative Complexity of Approximate Counting Problems

Two natural classes of counting problems that are interreducible under approximation-preserving reductions are: (i) those that admit a particular kind of efficient approximation algorithm known as an FPRAS, and (ii) those that are complete for #P with respect to approximation-preserving reducibility. We describe and investigate not only these two classes but also a third class, of intermediate complexity, that is not known to be identical to (i) or (ii). The third class can be characterised as the hardest problems in a logically defined subclass of #P.     

An Upper Bound on the Loss from Approximate Optimal-Value Functions

Many reinforcement learning approaches can be formulated using the theory of Markov decision processes and the associated method of dynamic programming (DP). The value of this theoretical understanding, however, is tempered by many practical concerns. One important question is whether DP-based approaches that use function approximation rather than lookup tables can avoid catastrophic effects on performance. This note presents a result of Bertsekas (1987) which guarantees that small errors in the approximation of a task's optimal value function cannot produce arbitrarily bad performance when actions are selected by a greedy policy. We derive an upper bound on performance loss that is slightly tighter than that in Bertsekas (1987), and we show the extension of the bound to Q-learning (Watkins, 1989). These results provide a partial theoretical rationale for the approximation of value functions, an issue of great practical importance in reinforcement learning.     

Approximate Dynamic Programming for Stochastic Resource Allocation Problems

A stochastic resource allocation model, based on the principles of Markov decision processes (MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations (i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming (DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations, occurs. In particular, an approximate dynamic programming (ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.      

Exact Penalty Functions and Problems of Variation Calculus

The main problem (also known as the simplest problem) of variational calculus is used to demonstrate that the theory of exact penalties can be used to find the main results of variational calculus (for example, Euler's conditions) and the tools of nonsmooth analysis can be applied to find the internal nature of the Euler equation and design new direct numerical methods for solving problems in variational calculus through the concept of the subgradient of the exact penalty function (which is essentially nonsmooth).     

基于数据的一类部分未知仿射非线性系统近似解

针对一类部分未知仿射非线性系统无穷区间求解问题,利用在线采样数据,提出了 在线无偏最小二乘支持向量机(Least square support vector machines, LS-SVM)的方法. 首先,通过引入一个参数消除了LS-SVM的偏置项,避免了冗余计算,同时在优化目标中引入权值 函数,对靠近当前时刻的数据样本点赋予更高权重,提高了计算精度; 其次,采用滚动时间窗的方法,实现非线性系统无穷区间求解,并满足求解实时性要求;最后,通过 数值算例仿真验证了本文方法的有效性和优越性.     

Submodular Functions in Problems of Synthesis of Networks

It is established that any problem of minimization of a general submodular function is the problem of determination of a minimum cut in a network if, for an arbitrary set, the dual function is defined as the sum of its values on the two-element subsets of this set. This result is used to synthesize a network with the help of a cut submodular function.     

Partially Observed Stochastic Shortest Path Problems With Approximate Solution by Neurodynamic Programming

We analyze a class of Markov decision processes with imperfect state information that evolve on an infinite time horizon and have a total cost criterion. In particular, we are interested in problems with stochastic shortest path structure, assuming the following: 1) the existence of a policy that guarantees termination with probability one and 2) the property that any policy that fails to guarantee termination has infinite expected cost from some initial state. We also assume that termination is perfectly recognized. In this paper, we clarify and expand upon arguments (given in an earlier paper) for establishing the existence, uniqueness, and characterization of stationary optimal policies, and the convergence of value and policy iteration. We also present an illustrative example, involving the search for a partially observed target that moves randomly on a grid, and we develop a simulation-based algorithm (based on neurodynamic programming techniques) for computing policies that approximately minimize the expected number of stages to complete the search.     

Nonlinear Constrained Optimal Control Problems and Cardinal Hermite Interpolant Multiscaling Functions

In this paper, a numerical method for solving nonlinear quadratic optimal control problems with inequality constraints is presented. The method is based upon cardinal Hermite interpolant multiscaling function approximation. The properties of these multiscaling functions are presented first. These properties are then utilized to reduce the solution of the nonlinear constrained optimal control to a nonlinear programming one, to which existing algorithms may be applied. Illustrative examples are included to demonstrate the efficiency and applicability of the technique.     

Proof Transformation via Interpretation Functions: Results, Problems and Applications

Change is a constant factor in Software Engineering process. Redesign of a class structure requires transformation of the corresponding OCL constraints. In a previous paper we have shown how to use, what we call, interpretation functions for transformation of constraints. In this paper we discuss recently obtained results concerning proof transformations via such functions. In particular we detail the fact that they preserve proofs in equational logic, as well as proofs in other logical systems like propositional logic with modus ponens or proofs using resolution rule. Those results have direct applications to redesign of UML State Machines and Sequence Diagrams. If states in a State Machine are interpreted by State Invariants, then the topological relations between its states can be interpreted as logical relations between the corresponding formulas. Preservation of the consequence relation can bee seen as preservation of the topology of State Machines. We indicate also an unsolved problem and discuss the mining of its positive solution.     

Approximate Calculation of Triple Integrals of Rapidly Oscillating Functions with the Use of Lagrange Polynomial Interflation

The authors consider the cubature formula for the approximate calculation of triple integrals of rapidly oscillating functions by using Lagrange polynomial interlineation of functions with the optimal choice of the nodal planes for the approximation of the non-oscillating set. The error of the cubature formula is estimated on the class of differentiable functions defined on a unit cube.     

Some Extremum Problems for Continuous Real Functions Specified by Transducers

This paper considers extremal problems for continuous real functions from the space C[0,1] and the possibilities of implementing them. Some programming means are also introduced, which facilitate the process of writing of approximating programs.     

Solving Optimal Control Problems on the Class of Step Functions

Linear optimal control problems with multipoint non-separated conditions with a quadratic performance criterion of control are analyzed. An approach with a violation of intermediate conditions is proposed. The original problem is reduced to the classical quadratic programming problem with the dimension determined by the number of intermediate points. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 153–162, July–August 2005.     

Holant Problems for 3-Regular Graphs with Complex Edge Functions

We study several embeddings of doubling metrics into low dimensional normed spaces, in particular into ? ₂ and ? _∞ . Doubling metrics are a robust class of metric spaces that have low intrinsic dimension, and often occur in applications. Understanding the dimension required for a concise representation of such metrics is a fundamental open problem in the area of metric embedding. Here we show that the n-vertex Laakso graph can be embedded into constant dimensional ? ₂ with the best possible distortion, which has implications for possible approaches to the above problem.