Negative selection algorithms on strings with efficient training and linear-time classification

A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σ^? into “normal” and “anomalous” partitions from a training set S containing only samples from the “normal” partition. The algorithm generates a set of patterns, called “detectors”, to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as “anomalous”. A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r-chunk and r-contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S⊆Σ^? and parameter r≤? one can construct an automaton whose acceptance behaviour is equivalent to the algorithm’s classification outcome. The resulting runtime is O(|S|?r|Σ|) for constructing the automaton in the training phase and O(?) for classifying a string.     

A class of aggregation functions encompassing two-dimensional OWA operators

In this paper we prove that, under suitable conditions, Atanassov’s K_α operators, which act on intervals, provide the same numerical results as OWA operators of dimension two. On one hand, this allows us to recover OWA operators from K_α operators. On the other hand, by analyzing the properties of Atanassov’s operators, we can generalize them. In this way, we introduce a class of aggregation functions - the generalized Atanassov operators - that, in particular, include two-dimensional OWA operators. We investigate under which conditions these generalized Atanassov operators satisfy some properties usually required for aggregation functions, such as bisymmetry, strictness, monotonicity, etc. We also show that if we apply these aggregation functions to interval-valued fuzzy sets, we obtain an ordered family of fuzzy sets.     

Obtaining more information from conjoint experiments by best-worst choices

Conjoint choice experiments elicit individuals’ preferences for the attributes of a good by asking respondents to indicate repeatedly their most preferred alternative in a number of choice sets. However, conjoint choice experiments can be used to obtain more information than that revealed by the individuals’ single best choices. A way to obtain extra information is by means of best-worst choice experiments in which respondents are asked to indicate not only their most preferred alternative but also their least preferred one in each choice set. To create D-optimal designs for these experiments, an expression for the Fisher information matrix for the maximum-difference model is developed. Semi-Bayesian D-optimal best-worst choice designs are derived and compared with commonly used design strategies in marketing in terms of the D-optimality criterion and prediction accuracy. Finally, it is shown that best-worst choice experiments yield considerably more information than choice experiments.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

On cool congruence formats for weak bisimulations

In TCS 146, Bard Bloom presented rule formats for four main notions of bisimulation with silent moves. He proved that weak bisimulation equivalence is a congruence for any process algebra defined by WB cool rules, and established similar results for rooted weak bisimulation (Milner’s “observational congruence”), branching bisimulation and rooted branching bisimulation. This study reformulates Bloom’s results in a more accessible form and contributes analogues for (rooted) η-bisimulation and (rooted) delay bisimulation. Moreover, finite equational axiomatisations of rooted weak bisimulation equivalence are provided that are sound and complete for finite processes in any RWB cool process algebra. These require the introduction of auxiliary operators with lookahead, and an extension of Bloom’s formats for this type of operator with lookahead. Finally, a challenge is presented for which Bloom’s formats fall short and further improvement is called for.     

Online computation with advice

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b=0 corresponds to the classical online model, and b=⌈log∣A∣⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones.In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1≤b≤Θ(logn), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω(log(n)/b) and we present a deterministic online algorithm for MTS with competitive ratio O(log(n)/b). For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k^O(1/b) for any choice of Θ(1)≤b≤logk.     

A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

Model-free Q-learning designs for linear discrete-time zero-sum games with application to H-infinity control

In this paper, the optimal strategies for discrete-time linear system quadratic zero-sum games related to the H-infinity optimal control problem are solved in forward time without knowing the system dynamical matrices. The idea is to solve for an action dependent value function Q(x,u,w) of the zero-sum game instead of solving for the state dependent value function V(x) which satisfies a corresponding game algebraic Riccati equation (GARE). Since the state and actions spaces are continuous, two action networks and one critic network are used that are adaptively tuned in forward time using adaptive critic methods. The result is a Q-learning approximate dynamic programming (ADP) model-free approach that solves the zero-sum game forward in time. It is shown that the critic converges to the game value function and the action networks converge to the Nash equilibrium of the game. Proofs of convergence of the algorithm are shown. It is proven that the algorithm ends up to be a model-free iterative algorithm to solve the GARE of the linear quadratic discrete-time zero-sum game. The effectiveness of this method is shown by performing an H-infinity control autopilot design for an F-16 aircraft.     

Approximate dynamic programming-based approaches for input-output data-driven control of nonlinear processes

We propose two approximate dynamic programming (ADP)-based strategies for control of nonlinear processes using input-output data. In the first strategy, which we term ‘J-learning,’ one builds an empirical nonlinear model using closed-loop test data and performs dynamic programming with it to derive an improved control policy. In the second strategy, called ‘Q-learning,’ one tries to learn an improved control policy in a model-less manner. Compared to the conventional model predictive control approach, the new approach offers some practical advantages in using nonlinear empirical models for process control. Besides the potential reduction in the on-line computational burden, it offers a convenient way to control the degree of model extrapolation in the calculation of optimal control moves. One major difficulty associated with using an empirical model within the multi-step predictive control setting is that the model can be excessively extrapolated into regions of the state space where identification data were scarce or nonexistent, leading to performances far worse than predicted by the model. Within the proposed ADP-based strategies, this problem is handled by imposing a penalty term designed on the basis of local data distribution. A CSTR example is provided to illustrate the proposed approaches.     

Partially varying coefficient single index proportional hazards regression models

In this paper, the partially varying coefficient single index proportional hazards regression models are discussed. All unknown functions are fitted by polynomial B splines. The index parameters and B-spline coefficients are estimated by the partial likelihood method and a two-step Newton-Raphson algorithm. Consistency and asymptotic normality of the estimators of all the parameters are derived. Through a simulation study and the VA data example, we illustrate that the proposed estimation procedure is accurate, rapid and stable.     

Arithmetic operators in interval-valued fuzzy set theory

We introduce the addition, subtraction, multiplication and division on L^I, where L^I is the underlying lattice of both interval-valued fuzzy set theory [R. Sambuc, Fonctions Φ-floues. Application à l’aide au diagnostic en pathologie thyroidienne, Ph.D. Thesis, Université de Marseille, France, 1975] and intuitionistic fuzzy set theory [K.T. Atanassov, Intuitionistic fuzzy sets, 1983, VII ITKR’s Session, Sofia (deposed in Central Sci. Technical Library of Bulg. Acad. of Sci., 1697/84) (in Bulgarian)]. We investigate some algebraic properties of these operators. We show that using these operators the pseudo-t-representable extensions of the ?ukasiewicz t-norm and the product t-norm on the unit interval to L^I and some related operators can be written in a similar way as their counterparts on ([0,1],?).     

Three-dimensional beta shapes

The Voronoi diagram of a point set has been extensively used in various disciplines ever since it was first proposed. Its application realms have been even further extended to estimate the shape of point clouds when Edelsbrunner and Mücke introduced the concept of α-shape based on the Delaunay triangulation of a point set.In this paper, we present the theory of β-shape for a set of three-dimensional spheres as the generalization of the well-known α-shape for a set of points. The proposed β-shape fully accounts for the size differences among spheres and therefore it is more appropriate for the efficient and correct solution for applications in biological systems such as proteins.Once the Voronoi diagram of spheres is given, the corresponding β-shape can be efficiently constructed and various geometric computations on the sphere complex can be efficiently and correctly performed. It turns out that many important problems in biological systems such as proteins can be easily solved via the Voronoi diagram of atoms in proteins and β-shapes transformed from the Voronoi diagram.     

Fuzzy and possibilistic clustering for fuzzy data

The Fuzzy k-Means clustering model (FkM) is a powerful tool for classifying objects into a set of k homogeneous clusters by means of the membership degrees of an object in a cluster. In FkM, for each object, the sum of the membership degrees in the clusters must be equal to one. Such a constraint may cause meaningless results, especially when noise is present. To avoid this drawback, it is possible to relax the constraint, leading to the so-called Possibilistic k-Means clustering model (PkM). In particular, attention is paid to the case in which the empirical information is affected by imprecision or vagueness. This is handled by means of LR fuzzy numbers. An FkM model for LR fuzzy data is firstly developed and a PkM model for the same type of data is then proposed. The results of a simulation experiment and of two applications to real world fuzzy data confirm the validity of both models, while providing indications as to some advantages connected with the use of the possibilistic approach.     

On the complexity of sandpile critical avalanches

In this work, we study The Abelian Sandpile Model from the point of view of computational complexity. We begin by studying the length distribution of sandpile avalanches triggered by the addition of two critical configurations: we prove that those avalanches are long on average, their length is bounded below by a constant fraction of the length of the longest critical avalanche which is, in most of the cases, superlinear. At the end of the paper we take the point of view of computational complexity, we analyze the algorithmic hardness of the problem consisting in computing the addition of two critical configurations, we prove that this problem is P complete, and we prove that most algorithmic problems related to The Abelian Sandpile Model are NC reducible to it.     

Functional linear regression after spline transformation

Functional linear regression has been widely used to model the relationship between a scalar response and functional predictors. If the original data do not satisfy the linear assumption, an intuitive solution is to perform some transformation such that transformed data will be linearly related. The problem of finding such transformations has been rather neglected in the development of functional data analysis tools. In this paper, we consider transformation on the response variable in functional linear regression and propose a nonparametric transformation model in which we use spline functions to construct the transformation function. The functional regression coefficients are then estimated by an innovative procedure called mixed data canonical correlation analysis (MDCCA). MDCCA is analogous to the canonical correlation analysis between two multivariate samples, but is between a multivariate sample and a set of functional data. Here, we apply the MDCCA to the projection of the transformation function on the B-spline space and the functional predictors. We then show that our estimates agree with the regularized functional least squares estimate for the transformation model subject to a scale multiplication. The dimension of the space of spline transformations can be determined by a model selection principle. Typically, a very small number of B-spline knots is needed. Real and simulation data examples are further presented to demonstrate the value of this approach.     

Incorporating historical control information into quantal bioassay with Bayesian approach

A Bayesian approach with an iterative reweighted least squares is used to incorporate historical control information into quantal bioassays to estimate the dose-response relationship, where the logit of the historical control responses are assumed to have a normal distribution. The parameters from this normal distribution are estimated from both empirical and full Bayesian approaches with a marginal likelihood function being approximated by Laplace’s Method. A comparison is made using real data between estimates that include the historical control information and those that do not. It was found that the inclusion of the historical control information improves the efficiency of the estimators. In addition, this logit-normal formulation is compared with the traditional beta-binomial for its improvement in parameter estimates. Consequently the estimated dose-response relationship is used to formulate the point estimator and confidence bands for ED(100p) for various values of risk rate p and the potency for any dose level.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.