On the complexity of working set selection

The decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with Support Vector Machines (SVM-optimization). A key issue in this approach is the policy for working set selection. We would like to find policies that realize (as well as possible) three goals simultaneously: “(fast) convergence to an optimal solution”, “efficient procedures for working set selection”, and “a high degree of generality” (including typical variants of SVM-optimization as special cases). In this paper, we study a general policy for working set selection that has been proposed in [Nikolas List, Hans Ulrich Simon, A general convergence theorem for the decomposition method, in: Proceedings of the 17th Annual Conference on Computational Learning Theory, 2004, pp. 363–377] and further analyzed in [Nikolas List, Hans Ulrich Simon, General polynomial time decomposition algorithms, in: Proceedings of the 17th Annual Conference on Computational Learning Theory, 2005, pp. 308–322]. It is known that it efficiently approaches feasible solutions with minimum cost for any convex quadratic optimization problem. Here, we investigate its computational complexity when it is used for SVM-optimization. It turns out that, for a variable size of the working set, the general policy poses an NP-hard working set selection problem. But a slight variation of it (sharing the convergence properties with the original policy) can be solved in polynomial time. For working sets of fixed size 2, the situation is even better. In this case, the general policy coincides with the “rate certifying pair approach” (introduced by Hush and Scovel). We show that maximum rate certifying pairs can be found in linear time, which leads to a quite efficient decomposition method with a polynomial convergence rate for SVM-optimization.     

Optimal sensor scheduling for hidden Markov model state estimation

Consider the Hidden Markov model where the realization of a single Markov chain is observed by a number of noisy sensors. The sensor scheduling problem for the resulting hidden Markov model is as follows: design an optimal algorithm for selecting at each time instant, one of the many sensors to provide the next measurement. Each measurement has an associated measurement cost. The problem is to select an optimal measurement scheduling policy, so as to minimize a cost function of estimation errors and measurement costs. The problem of determining the optimal measurement policy is solved via stochastic dynamic programming. Numerical results are presented.     

基于文化算法的多agent 联盟在网络舆情监测中的应用

对网络舆情监测监控云平台上集聚的海量技术agent, 如果只是逐一agent 搜寻使联盟的利益最大化, 将耗费大量的时间和费用. 为解决该问题, 提出了基于“能力群”的动态联盟机制, 通过动态增加或删除“能力群”中的agent 来增加联盟完成复杂任务的能力; 并提出一种基于文化算法的“能力群”agent 联盟算法, 详细讨论了算法的流程、编码、选择、交叉和变异操作的规则, 以及基于“能力群”特征的交叉算法. 仿真结果表明, 所提出的算法是可行和有效的.

     

Multiagent learning using a variable learning rate

Learning to act in a multiagent environment is a difficult problem since the normal definition of an optimal policy no longer applies. The optimal policy at any moment depends on the policies of the other agents. This creates a situation of learning a moving target. Previous learning algorithms have one of two shortcomings depending on their approach. They either converge to a policy that may not be optimal against the specific opponents' policies, or they may not converge at all. In this article we examine this learning problem in the framework of stochastic games. We look at a number of previous learning algorithms showing how they fail at one of the above criteria. We then contribute a new reinforcement learning technique using a variable learning rate to overcome these shortcomings. Specifically, we introduce the WoLF principle, “Win or Learn Fast”, for varying the learning rate. We examine this technique theoretically, proving convergence in self-play on a restricted class of iterated matrix games. We also present empirical results on a variety of more general stochastic games, in situations of self-play and otherwise, demonstrating the wide applicability of this method.     

A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time

This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution.In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed.We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.     

Time and output warping of control systems: Comparing and imitating motions

The problem of making one system “mimic” a motion generated by another is studied. To address this, an optimal tracking problem is introduced that, in addition to tracking, optimizes over functions that deform or “warp” the time axis and the output space. Parametric and nonparametric versions of the time-warped tracking problem are presented and reduced to standard Bolza problems. The output warping problem is treated for affine and piecewise affine output warping functions. Example applications are given, including that of controlling a marionette to mimic a human dancer.     

A greedy algorithm for feedrate planning of CNC machines along curved tool paths with confined jerk

In this paper, the problem of optimal feedrate planning along a curved tool path for 3-axis CNC machines with the acceleration and jerk limits for each axis and the tangential velocity bound is addressed. It is proved that the optimal feedrate planning must be “Bang–Bang” or “Bang–Bang-Singular” control, that is, at least one of the axes reaches its acceleration or jerk bound, or the tangential velocity reaches its bound throughout the motion. As a consequence, the optimal parametric velocity can be expressed as a piecewise analytic function of the curve parameter u. The explicit formula for the velocity function when a jerk reaches its bound is given by solving a second-order differential equation. Under a “greedy rule”, an algorithm for optimal jerk confined feedrate planning is presented. Experiment results show that the new algorithm can be used to reduce the machining vibration and improve the machining quality.     

Finding optimal satisficing strategies for and-or trees

Many tasks require evaluating a specified Boolean expression φ over a set of probabilistic tests whose costs and success probabilities are each known. A strategy specifies when to perform which test, towards determining the overall outcome of φ. We are interested in finding the strategy with the minimum expected cost.As this task is typically NP-hard—for example, when tests can occur many times within φ, or when there are probabilistic correlations between the test outcomes—we consider those cases in which the tests are probabilistically independent and each appears only once in φ. In such cases, φ can be written as an and-or tree, where each internal node corresponds to either the “and” or “or” of its children, and each leaf node is a probabilistic test. In this paper we investigate “probabilistic and-or tree resolution” (PAOTR), namely the problem of finding optimal strategies for and-or trees.We first consider a depth-first approach: evaluate each penultimate rooted subtree in isolation, replace each such subtree with a single “mega-test”, and recurse on the resulting reduced tree. We show that the strategies produced by this approach are optimal for and-or trees with depth at most two but can be arbitrarily sub-optimal for deeper trees.Each depth-first strategy can be described by giving the linear relative order in which tests are to be executed, with the understanding that any test whose outcome becomes irrelevant is skipped. The class of linear strategies is strictly larger than depth-first strategies. We show that even the best linear strategy can also be arbitrarily sub-optimal.We next prove that an optimal strategy honors a natural partial order among tests with a common parent node (“leaf-sibling tests”), and use this to produce a dynamic programming algorithm that finds the optimal strategy in time O(d²d(r+1)), where r is the maximum number of leaf-siblings and d is the number of leaf-parents; hence, for trees with a bounded number of internal nodes, this run-time is polynomial in the tree size. We also present another special class of and-or trees for which this task takes polynomial time.We close by presenting a number of other plausible approaches to PAOTR, together with counterexamples to show their limitations.     

Minimum-cost delegation in service composition

The paradigm of automated service composition through the integration of existing services promises a fast and efficient development of new services in cooperative service (e.g., business) environments. Although the “why” part of this paradigm is well understood, many key pieces are missing to utilize the available opportunities. Recently “service communities” where service providers with similar interests can register their services are proposed toward realizing this goal. In these communities, requests for services posed by users can be processed by delegating them to existing services, and orchestrating their executions. We use a service framework similar to the “Roman” model departing from it particularly assuming service requirements are specified in a sequence form. We also extend the framework to integrate activity processing costs into the delegation computation and to have services with bounded storage as opposed to finite storage. We investigate the problem of efficient processing of service requests in service communities and develop polynomial time delegation techniques guaranteeing optimality.     

FOE estimation: Can image measurement errors be totally “corrected” by the geometric method?

For the FOE estimation, there are basically three kinds of estimation methods in the literature: algebraic, geometric, and the maximum likelihood-based ones. In this paper, our attention is focused on the geometric method. The computational complexity of the classical geometric method is usually very high because it needs to solve a non-linear minimum problem with many variables. In this work, such a minimum problem is converted into an equivalent one with only two variables and accordingly a simplified geometric method is proposed. Based on the equivalence of the classical geometric method and the proposed simplified geometric method, we show that the measurement errors can at most be “corrected” only in one of the two images by geometric methods. In other words, it is impossible to correct the measurement errors in both of the two images. In addition, we show that the “corrected” corresponding pairs by geometric methods cannot in general meet some of the inherent constraints of corresponding pairs under pure camera translations. Hence, it is not proper to consider the “corrected” corresponding pairs as “faithful” corresponding pairs in geometric methods, and the estimated FOE from such pairs is not necessarily trustworthier. Finally, a new geometric algorithm, which automatically enforces the inherent constraints, is proposed in this work, and better FOE estimation and more faithful corresponding pairs are obtained.     

A mathematical model on EPQ for stochastic demand in an imperfect production system

In the paper, we develop an EPQ (economic production quantity) inventory model to determine the optimal buffer inventory for stochastic demand in the market during preventive maintenance or repair of a manufacturing facility with an EPQ (economic production quantity) model in an imperfect production system. Preventive maintenance, an essential element of the just-in-time structure, may cause shortage which is reduced by buffer inventory. The products are sold with the free minimal repair warranty (FRW) policy. The production system may undergo “out-of-control” state from “in-control” state, after a certain time that follows a probability density function. The defective (non-conforming) items in “in-control” or “out-of-control” state are reworked at a cost just after the regular production time. Finally, an expected cost function regarding the inventory cost, unit production cost, preventive maintenance cost and shortage cost is minimized analytically. We develop another case where the buffer inventory as well as the production rate are decision variables and the expected unit cost considering the above cost functions is optimized also. The numerical examples are provided to illustrate the behaviour and application of the model. Sensitivity analysis of the model with respect to key parameters of the system is carried out.     

The price of forgetting in parallel and non-observable queues

We consider a broker-based network of non-observable parallel queues and analyze the minimum expected response time and the optimal routing policy when the broker has the memory of its previous routing decisions. We provide lower bounds on the minimum response time by means of convex programming that are tight, as follows by a numerical comparison with a proposed routing scheme. The “Price of Forgetting” (PoF), the ratio between the minimum response times achieved by a probabilistic broker and a broker with memory, is shown to be unbounded or arbitrarily close to one depending on the coefficient of variation of the service time distributions. In the case of exponential service times, the PoF is bounded from above by two, which is tight in heavy-traffic, and independent of the network size and heterogeneity. These properties yield a simple engineering product-form approximating tightly the minimum response time. Finally, we put our results in the context of game theory revisiting the “Price of Anarchy” (PoA) of parallel queues: it can be decomposed into the product of the PoA achieved by a probabilistic broker (already well understood) and the PoF.     

A bio-inspired pursuit strategy for optimal control with partially constrained final state

We discuss a biologically inspired cooperative control strategy which allows a group of autonomous systems to solve optimal control problems with free final time and partially constrained final state. The proposed strategy, termed “generalized sampled local pursuit” (GSLP), mimics the way in which ants optimize their foraging trails, and guides the group toward an optimal solution, starting from an initial feasible trajectory. Under GSLP, an optimal control problem is solved in many “short” segments, which are constructed by group members interacting locally with lower information, communication and storage requirements compared to when the problem is solved all at once. We include a series of simulations that illustrate our approach.     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.     

A size-insensitive integrity-based fuzzy c-means method for data clustering

Fuzzy c-means (FCM) is one of the most popular techniques for data clustering. Since FCM tends to balance the number of data points in each cluster, centers of smaller clusters are forced to drift to larger adjacent clusters. For datasets with unbalanced clusters, the partition results of FCM are usually unsatisfactory. Cluster size insensitive FCM (csiFCM) dealt with “cluster-size sensitivity” problem by dynamically adjusting the condition value for the membership of each data point based on cluster size after the defuzzification step in each iterative cycle. However, the performance of csiFCM is sensitive to both the initial positions of cluster centers and the “distance” between adjacent clusters. In this paper, we present a cluster size insensitive integrity-based FCM method called siibFCM to improve the deficiency of csiFCM. The siibFCM method can determine the membership contribution of every data point to each individual cluster by considering cluster's integrity, which is a combination of compactness and purity. “Compactness” represents the distribution of data points within a cluster while “purity” represents how far a cluster is away from its adjacent cluster. We tested our siibFCM method and compared with the traditional FCM and csiFCM methods extensively by using artificially generated datasets with different shapes and data distributions, synthetic images, real images, and Escherichia coli dataset. Experimental results showed that the performance of siibFCM is superior to both traditional FCM and csiFCM in terms of the tolerance for “distance” between adjacent clusters and the flexibility of selecting initial cluster centers when dealing with datasets with unbalanced clusters.     

A sound and complete model-generation procedure for consistent and confidentiality-preserving databases

This article introduces and investigates a new model-theoretic mechanism to enforce confidentiality (or privacy) requirements in a database instance; at the same time it ensures maximum availability of correct database answers. The aim is to materialize and publish a secure view that satisfies the properties of “inference-proofness” and “distortion minimality”. A comprehensive class of first-order constraints (representing a user’s a priori knowledge and a confidentiality policy) can be handled by the presented algorithm in a sound and complete way: tuple-generating dependencies, denial constraints and existential constraints. The due proof of refutation soundness makes use of Herbrand’s theorem and semantic trees.     

Efficiency evaluation for allocating community-based health services

When allocating community-based health services for a geographically defined region, health planners are often faced with the serious conflict for improved health service and a limited budget. This paper extends the cost-based P-median location–allocation model (Daskin & Dean, 2005) to include a public service element and uses the non-inferior set estimation (NISE) method for evaluation of cost/service trade-offs. Service is measured by the percentage of demand volume that can be served within exogenously specified coverage distances. Importantly, we evaluate the efficiency (i.e. the relative cost and service) of the non-inferior solutions of our model using the commonly used “population-based” allocation policy as standard. Computational results illustrate the value of our model under several practical problem settings.     

An efficient renovation on kernel Fisher discriminant analysis and face recognition experiments

A reformative kernel algorithm, which can deal with two-class problems as well as those with more than two classes, on Fisher discriminant analysis is proposed. In the novel algorithm the supposition that in feature space discriminant vector can be approximated by some linear combination of a part of training samples, called “significant nodes”, is made. If the “significant nodes” are found out, the novel algorithm on kernel Fisher discriminant analysis will be superior to the naive one in classification efficiency. In this paper, a recursive algorithm for selecting “significant nodes”, is developed in detail. Experiments show that the novel algorithm is effective and much efficient in classifying.     

Finding rectilinear least cost paths in the presence of convex polygonal congested regions

This paper considers the problem of finding the least cost rectilinear distance path in the presence of convex polygonal congested regions. We demonstrate that there are a finite, though exponential number of potential staircase least cost paths between a specified pair of origin–destination points. An upper bound for the number of entry/exit points of a rectilinear path between two points specified a priori in the presence of a congested region is obtained. Based on this key finding, a “memory-based probing algorithm” is proposed for the problem and computational experience for various problem instances is reported. A special case where polynomial time solutions can be obtained has also been outlined.