On piecewise-linear classification

The authors make use of a real data set containing 9-D measurements of fine needle aspirates of a patient's breast for the purpose of classifying a tumor's malignancy for which early stopping in the generation of the separating hyperplanes is not appropriate. They compare a piecewise-linear classification method with classification based on a single linear separator. A precise methodology for comparing the relative efficacy of two classification methods for a particular task is described and is applied to the comparison on the breast cancer data of the relative performances of the two versions of the piecewise-linear classifier and the classification based on an optimal linear separator. It is found that for this data set, the piecewise-linear classifier that uses all the hyperplanes needed to separate the training set outperforms the other two methods and that these differences in performance are significant at the 0.001 level. There is no statistically significant difference between the performance of the other two methods. The authors discuss the relevance of these results for this and other applications     

Singular perturbation in piecewise-linear systems

A singular perturbation technique is developed that allows for a decoupling of a continuous piecewise-linear system into slow and fast subsystems. Under the assumption of asymptotic stability, the fast variable is found to decay in the boundary layer to its quasi-steady-state solution, which is given by a continuous implicit function of the slow variable. The solution is found using a finite step algorithm. Sufficient conditions for the approximation to be accurate to an order of O(μ), where μ is a parameter of the system, are given. The technique is illustrated by a numerical example     

Sequential piecewise-linear segmentation of binary contours

An algorithm for the segmentation of binary contours into linear segments is presented, which sequentially processes the lines of a digital image.     

Characterization of well-posedness of piecewise-linear systems

One of the basic issues in the study of hybrid systems is the well-posedness (existence and uniqueness of solutions) problem of discontinuous dynamical systems. The paper addresses this problem for a class of piecewise-linear discontinuous systems under the definition of solutions of Caratheodory. The concepts of jump solutions or of sliding modes are not considered here. In this sense, the problem to be discussed is one of the most basic problems in the study of well-posedness for discontinuous dynamical systems. First, we derive necessary and sufficient conditions for bimodal systems to be well-posed, in terms of an analysis based on lexicographic inequalities and the smooth continuation property of solutions. Next, its extensions to the multimodal case are discussed. As an application to switching control, in the case that two state feedback gains are switched according to a criterion depending on the state, we give a characterization of all admissible state feedback gains for which the closed loop system remains well-posed     

Integrated circuit implementation of multi-dimensional piecewise-linear functions

In this paper we present an integrated circuit implementing piecewise-linear (PWL) functions with three inputs, where each input can be either analog or digital. The PWL function to be implemented can be chosen by properly storing a set of coefficients in a 4 kB external memory. Experimental results are shown that demonstrate the circuit working up to 50 MHz with a maximum power consumption of 3.7 mW. Measurements corresponding to both static and time-varying inputs are provided and discussed.     

Realisation and estimation of piecewise-linear output-error models

Piecewise-linear systems in input/output form can have different switching schedules. In this article, two categories, instant and delayed switching, are analysed. Even though a general piecewise-linear state-space model cannot be converted into input/output form, it is shown that it is possible to find state-space models representing instant and delayed switching. In addition, a prediction-error minimisation (PEM) method for piecewise-linear output-error predictors is derived and it is concluded that the instant-switching model candidate is not necessarily the most suitable for the parameter estimation procedure.     

基于分片线性函数逼近的非线性观测器设计

综合分片线性函数模型辨识/逼近和鲁棒观测器设计方法,研究了一大类非线性鲁棒观测器设计方法.所提出的算法能有效解决非线性系统的辨识/建模问题,并保证在一定的逼近精度下观测误差可以控制在一定的范围内,且观测误差随着逼近精度的提高而减小.     

Identification of nonlinear systems using a piecewise-linear Hammerstein model

In the paper a method for nonlinear system identification is proposed. It is based on a piecewise-linear Hammerstein model, which is linear in the parameters. The model and the identification algorithm are adapted to allow the parameter identification in the presence of a special form of the excitation signal. The identification method is derived from a recursive least-squares algorithm, which is properly adapted to take into account the proposed model structure and the properties of the identification signal. The applicability of the approach is illustrated by an example in which a discontinuous nonlinear static function is connected to a dynamic block.     

Canonical Naming Systems

This paper outlines a framework for the abstract investigation of the concept of canonicity of names and of naming systems. Degrees of canonicity of names and of naming systems are distinguished. The structure of the degrees is investigated, and a notion of relative canonicity is defined. The notions of canonicity are formally expressed within a Carnapian system of second-order modal logic.     

Stochastic Canonical Flows

There has been some opposition to the use of Markov processes in quantum mechanics based upon the fact that no quantum mechanical regression principle can be applied. It is argued here however that one may just as well conclude that there is no classical mechanical regression principal either. The dissipative component of a canonical stochastic flow is of the form of a double Poisson bracket 1/2 {{·, F } F } while the vector component of the noise is the Hamiltonian vector field {·, F }; thus the dissipative term is smoother than the noise coefficient. In contrast, the classical Langevin theory is based upon the Ornstein-Uhlenbeck process which has linear drift and constant noise coefficient. Preservation of the canonical structure is at odds with the approximation procedure by Ornstein-Uhlenbeck processes and this is the case in both classical and quantum situations.     

Canonical logic programs

Consider the class of programs P where the greatest fixpoint of T_P is equal to the complement of the finite failure set of P. Programs in this calss possess some important properties which others do not. The main result in this paper proves that this class is representative of all programs. Specifically, we call the programs in this class canonical and we prove that for any program P₁, there exists a semantically equivalent program P₂ which is canonical.     

Canonical density control

The Sparse Table is a data structure for controlling density in an array which was first proposed in 1981 and has recently reappeared as a component of cache-oblivious data structures. All existing variants of the Sparse Table divide the array into blocks that have a calibrator tree above them. We show that the same amortized complexity can be achieved without this auxiliary structure, obtaining a canonical data structure that can be updated by conceptually simpler algorithms.     

Minimizing the number of tardy jobs under piecewise-linear deterioration

In this paper, we consider a single machine scheduling problem with piecewise-linear deterioration where its objective is to minimize the number of tardy jobs, in which the processing time of each job depends on its starting time where all the jobs have a specific deterioration rate. The problem is known to be NP-hard; therefore a Branch and Bound algorithm and a heuristic algorithm with O(n²) are proposed. The proposed heuristic algorithm has been utilized for solving large scale problems and upper bound of the B&B algorithm. Computational experiments on 1840 problems demonstrate that the Branch and Bound procedure can solve problems with 28 jobs and 85.4% of all the sample problems optimally showing the high capability of the proposed procedure. Also it is shown that the average value of the ratio of optimal answer to the heuristic algorithm result with the objective ∑(1-_Ui)$\sum (1-U_i)$ is at last 1.08 which is more efficient in contrast to other proposed algorithms in related studies in the literature. According to high efficacy of the heuristic algorithm, large scale samples are also being solved and the results are presented. A specific form of this problem is also being considered and it is proven that the B&B procedure can handle problems with more jobs even up to 44 jobs.     

Identification of Wiener systems with nonlinearity being piecewise-linear function

Identification of the Wiener system with the nonlinear block being a piecewiselinear function is considered in the paper, generalizing the results given by H. E. Chen to the case of noisy observation. Recursive algorithms are given for estimating all unknown parameters contained in the system, and their strong consistency is proved. The estimation method is similar to that used by H. E. Chen for Hammerstein systems with the same nonlinearity. However, the assumption imposed by H. E. Chen on the availability of an upper bound for the nonsmooth points of the piecewise-linear function has been removed in this paper with the help of designing an additional algorithm for estimating the upper bound.     

Design of piecewise-linear switching functions for relay control systems

The design of piecewise-linear switching functions is investigated for linear, constant, lumped systems with a single ideal relay controller with respect to a transient response (minimum-time) performance criterion. A design method is presented which consists of a series of steps leading finally to the optimization of parameters by a gradient or other search technique suitable for computer implementation. The preliminary steps are devoted to reducing the dimensionality of the parameter space which must be searched, defining the criterion function so as to yield a surface which is reasonably smooth and free of relative minima, and insuring that the search is started with a feasible parameter set. It is concluded that easily implemented piecewise-linear switching functions can be designed so as to yield improved performance, both in terms of settling times and region of stability in the state space, over that attainable with linear switching functions. The complexities of the performance surface are such, however, that it is felt that frequently the determination of a switching function by the heuristic guides described, constitutes an adequate design without the refinement of parameter optimization.     

A multilayer neural network with piecewise-linear structure andback-propagation learning

A multilayer neural network which is given a two-layer piecewise-linear structure for every cascaded section is proposed. The neural networks have nonlinear elements that are neither sigmoidal nor of a signum type. Each nonlinear element is an absolute value operator. It is almost everywhere differentiable, which makes back-propagation feasible in a digital setting. Both the feedforward signal propagation and the backward coefficient update rules belong to the class of regular iterative algorithms. This form of neural network specializes in functional approximation and is anticipated to have applications in control, communications, and pattern recognition.     

Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs

We present two efficient algorithms for the minimum-cost flow problem in which arc costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear arc costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity isO(M logU(m+n logM)) for a network withn vertices,m arcs, M linear cost segments, and an upper boundU on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity isO(M logM(m+n logM)). Both algorithms improve by a factor of at leastM/m the complexity of directly applying existing algorithms to a transformed network in which arc costs are linear.The final stage of this work was performed while Ron Shamir was a visitor at DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University. Supported in part by National Science Foundation Grant NSF-STC88-09648, and by Air Force Grants AFOSR-89-0512 and AFOSR-90-0008.