| 1. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
A Dual Active-Set Algorithm for Regularized Slope-Constrained Monotonic Regression
- 2017
-
Ingår i: Iranian Journal of Operations Research. - Tehran : CMV Verlag. - 2008-1189. ; 8:2, s. 40-47
-
Tidskriftsartikel (refereegranskat)abstract
- In many problems, it is necessary to take into account monotonic relations. Monotonic (isotonic) Regression (MR) is often involved in solving such problems. The MR solutions are of a step-shaped form with a typical sharp change of values between adjacent steps. This, in some applications, is regarded as a disadvantage. We recently introduced a Smoothed MR (SMR) problem which is obtained from the MR by adding a regularization penalty term. The SMR is aimed at smoothing the aforementioned sharp change. Moreover, its solution has a far less pronounced step-structure, if at all available. The purpose of this paper is to further improve the SMR solution by getting rid of such a structure. This is achieved by introducing a lowed bound on the slope in the SMR. We call it Smoothed Slope-Constrained MR (SSCMR) problem. It is shown here how to reduce it to the SMR which is a convex quadratic optimization problem. The Smoothed Pool Adjacent Violators (SPAV) algorithm developed in our recent publications for solving the SMR problem is adapted here to solving the SSCMR problem. This algorithm belongs to the class of dual active-set algorithms. Although the complexity of the SPAV algorithm is o(n2) its running time is growing in our computational experiments almost linearly with n. We present numerical results which illustrate the predictive performance quality of our approach. They also show that the SSCMR solution is free of the undesirable features of the MR and SMR solutions.
|
|
| 2. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
An O(n2) algorithm for isotonic regression
- 2006
-
Ingår i: Large-Scale Nonlinear Optimization. - New York : Springer Science+Business Media B.V.. - 0387300635 ; , s. 25-33
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- We consider the problem of minimizing the distance from a given n-dimensional vector to a set defined by constraints of the form xi ≤ xj. Such constraints induce a partial order of the components xi, which can be illustrated by an acyclic directed graph. This problem is also known as the isotonic regression (IR) problem. IR has important applications in statistics, operations research and signal processing, with most of them characterized by a very large value of n. For such large-scale problems, it is of great practical importance to develop algorithms whose complexity does not rise with n too rapidly. The existing optimization-based algorithms and statistical IR algorithms have either too high computational complexity or too low accuracy of the approximation to the optimal solution they generate. We introduce a new IR algorithm, which can be viewed as a generalization of the Pool-Adjacent-Violator (PAV) algorithm from completely to partially ordered data. Our algorithm combines both low computational complexity O(n2) and high accuracy. This allows us to obtain sufficiently accurate solutions to IR problems with thousands of observations.
|
|
| 3. |
|
|
| 4. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Data preordering in generalized PAV algorithm for monotonic regression
- 2006
-
Ingår i: Journal of Computational Mathematics. - 0254-9409 .- 1991-7139. ; 24:6, s. 771-790
-
Tidskriftsartikel (refereegranskat)abstract
- Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. {\sl Nonconvex Optimization and Its Applications}, Springer-Verlag, (2006) {\bf 83}, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.
|
|
| 5. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
Monotonic data fitting and interpolation with application to postprocessing of FE solutions
- 2007
-
Ingår i: CERFACS 20th Anniversary Conference on High-performance Computing,2007. ; , s. 11-12
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- In this talk we consider the isotonic regression (IR) problem which can be formulated as follows. Given a vector $\bar{x} \in R^n$, find $x_* \in R^n$ which solves the problem: \begin{equation}\label{ir2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0. \end{array} \end{equation} The set of constraints $Mx \ge 0$ represents here the monotonicity relations of the form $x_i \le x_j$ for a given set of pairs of the components of $x$. The corresponding row of the matrix $M$ is composed mainly of zeros, but its $i$th and $j$th elements, which are equal to $-1$ and $+1$, respectively. The most challenging applications of (\ref{ir2}) are characterized by very large values of $n$. We introduce new IR algorithms. Our numerical experiments demonstrate the high efficiency of our algorithms, especially for very large-scale problems, and their robustness. They are able to solve some problems which all existing IR algorithms fail to solve. We outline also our new algorithms for monotonicity-preserving interpolation of scattered multivariate data. In this talk we focus on application of our IR algorithms in postprocessing of FE solutions. Non-monotonicity of the numerical solution is a typical drawback of the conventional methods of approximation, such as finite elements (FE), finite volumes, and mixed finite elements. The problem of monotonicity is particularly important in cases of highly anisotropic diffusion tensors or distorted unstructured meshes. For instance, in the nuclear waste transport simulation, the non-monotonicity results in the presence of negative concentrations which may lead to unacceptable concentration and chemistry calculations failure. Another drawback of the conventional methods is a possible violation of the discrete maximum principle, which establishes lower and upper bounds for the solution. We suggest here a least-change correction to the available FE solution $\bar{x} \in R^n$. This postprocessing procedure is aimed on recovering the monotonicity and some other important properties that may not be exhibited by $\bar{x}$. The mathematical formulation of the postprocessing problem is reduced to the following convex quadratic programming problem \begin{equation}\label{ls2} \begin{array}{cl} \mbox{min} & \|x-\bar{x}\|^2 \\ \mbox{s.t.} & Mx \ge 0, \quad l \le x \le u, \quad e^Tx = m, \end{array} \end{equation} where$e=(1,1, \ldots ,1)^T \in R^n$. The set of constraints $Mx \ge 0$ represents here the monotonicity relations between some of the adjacent mesh cells. The constraints $l \le x \le u$ originate from the discrete maximum principle. The last constraint formulates the conservativity requirement. The postprocessing based on (\ref{ls2}) is typically a large scale problem. We introduce here algorithms for solving this problem. They are based on the observation that, in the presence of the monotonicity constraints only, problem (\ref{ls2}) is the classical monotonic regression problem, which can be solved efficiently by some of the available monotonic regression algorithms. This solution is used then for producing the optimal solution to problem (\ref{ls2}) in the presence of all the constraints. We present results of numerical experiments to illustrate the efficiency of our algorithms.
|
|
| 6. |
- Burdakov, Oleg, 1953-, et al.
(författare)
-
New optimization algorithms for large-scale isotonic regression in L2-norm
- 2007
-
Ingår i: EUROPT-OMS Conference on Optimization,2007. - University of Hradec Kralove, Czech Republic : Guadeamus. ; , s. 44-44
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Isotonic regression problem (IR) has numerous important applications in statistics, operations research, biology, image and signal processing and other areas. IR in L2-norm is a minimization problem in which the objective function is the squared Euclidean distance from a given point to a convex set defined by monotonicity constraints of the form: i-th component of the decision vector is less or equal to its j-th component. Unfortunately, the conventional optimization methods are unable to solve IR problems originating from large data sets. The existing IR algorithms, such as the minimum lower sets algorithm by Brunk, the min-max algorithm by Lee, the network flow algorithm by Maxwell & Muchstadt and the IBCR algorithm by Block et al. are able to find exact solution to IR problem for at most a few thousands of variables. The IBCR algorithm, which proved to be the most efficient of them, is not robust enough. An alternative approach is related to solving IR problem approximately. Following this approach, Burdakov et al. developed an algorithm, called GPAV, whose block refinement extension, GPAVR, is able to solve IR problems with a very high accuracy in a far shorter time than the exact algorithms. Apart from this, GPAVR is a very robust algorithm, and it allows us to solve IR problems with over hundred thousands of variables. In this talk, we introduce new exact IR algorithms, which can be viewed as active set methods. They use the approximate solution produced by the GPAVR algorithm as a starting point. We present results of our numerical experiments demonstrating the high efficiency of the new algorithms, especially for very large-scale problems, and their robustness. They are able to solve the problems which all existing exact IR algorithms fail to solve.
|
|
| 7. |
- Sysoev, Oleg, 1981-, et al.
(författare)
-
A smoothed monotonic regression via L2 regularization
- 2019
-
Ingår i: Knowledge and Information Systems. - : Springer. - 0219-1377 .- 0219-3116. ; 59:1, s. 197-218
-
Tidskriftsartikel (refereegranskat)abstract
- Monotonic regression is a standard method for extracting a monotone function from non-monotonic data, and it is used in many applications. However, a known drawback of this method is that its fitted response is a piecewise constant function, while practical response functions are often required to be continuous. The method proposed in this paper achieves monotonicity and smoothness of the regression by introducing an L2 regularization term. In order to achieve a low computational complexity and at the same time to provide a high predictive power of the method, we introduce a probabilistically motivated approach for selecting the regularization parameters. In addition, we present a technique for correcting inconsistencies on the boundary. We show that the complexity of the proposed method is O(n2). Our simulations demonstrate that when the data are large and the expected response is a complicated function (which is typical in machine learning applications) or when there is a change point in the response, the proposed method has a higher predictive power than many of the existing methods.
|
|
| 8. |
- Sysoev, Oleg, 1981-, et al.
(författare)
-
New optimization methods for isotonic regression in L1 norm
- 2007
-
Ingår i: EUROPT-OMS Conference on Optimization,2007. - University of Hradec Kralove, Czech Republic : Guadeamus. ; , s. 133-133
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Isotonic regression problem (IR) has numerous important applications in statistics, operations research, biology, image and signal processing and other areas. IR is a minimization problem with the objective function defined by the distance from a given point to a convex set defined by monotonicity constraints of the form: i-th component of the decision vector is less or equal to its j-th component. The distance in IR is usually associated with the Lp norm, whereas the norms L1 and L2 are of the highest practical interest. The conventional optimization methods are unable to solve large-scale IR problems originating from large data sets. Historically, the major efforts were focused on IR problem in the L2 norm. Exact algorithms such as the minimum lower sets algorithm by Brunk, the min-max algorithm by Lee, the network flow algorithm by Maxwell & Muchstadt and the IBCR algorithm by Block et al. were developed. Among them the IBCR algorithm has been proved to be the most numerically efficient, but it is not robust enough. An alternative approach is related to solving IR problem approximately. Following this approach, Burdakov et al. developed GPAV algorithm whose block refinement extension, GPAVR, is able to solve IR problem with high accuracy in a far shorter time than the exact algorithms. Apart from this, GPAVR is a very robust algorithm. Unfortunately, for the norm L1 there are no algorithms which are as efficient as those in L2 norm. In our talk, we introduce new algorithms, GPAVR1 and IBCR1. They are extensions of the algorithms GPAV and IBCR to L1 norm. We present also results of numerical experiments, which demonstrate the high efficiency of the new algorithms, especially for very large-scale problems.
|
|
| 9. |
- Gawel, Danuta, 1988-, et al.
(författare)
-
Stor potential när genomikdatakan implementeras i klinisk rutin : [Clinical translation of genomic medicine]
- 2021
-
Ingår i: Läkartidningen. - : Sveriges Läkarförbund. - 0023-7205 .- 1652-7518. ; 118
-
Forskningsöversikt (refereegranskat)abstract
- Recent technical developments and early clinical examples support that precision medicine has potential to provide novel diagnostic and therapeutic solutions for patients with complex diseases, who are not responding to existing therapies. Those solutions will require integration of genomic data with routine clinical, imaging, sensor, biobank and registry data. Moreover, user-friendly tools for informed decision support for both patients and clinicians will be needed. While this will entail huge technical, ethical, societal and regulatory challenges, it may contribute to transforming and improving health care towards becoming predictive, preventive, personalised and participatory (4P-medicine).
|
|
| 10. |
- Svahn, Caroline
(författare)
-
Prediction Methods for High Dimensional Data with Censored Covariates
- 2022
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- While access to data steadily increases, not all data are straight-forward to use for prediction. Censored data are common in several industrial scenarios, and typically arise when there are some limitations to measuring equipment such as for instance concentration measuring equipment in chemistry or signal receivers in signal processing. In this thesis, we take several angles to censored covariate data for prediction problem. We explore the impact on both covariates and the response when the censored covariates are imputed. We consider linear approaches as well as non-linear approaches, and we explore how both frequentist models as well as Bayesian models perform with censored covariate data. While the focus is using the imputed covariate data for prediction, we also investigate model parameter inference and uncertainty inferred by the imputations. We use real, censored covariate telecommunications data for prediction with some of the most commonly used prediction models and evaluate the performance when single imputations are made. We propose a selective multiple imputation approach which is suitable for high dimensional data that perform well with heavy censoring. We take a Bayesian linear regression approach leveraging information from auxiliary variables using multivariate regression and introduce multivariate draws from conditional distributions to update censored values in the covariates. We fnally offer a bridge between the fexibility of Neural Networks and the probabilistic nature of Bayesian methods by taking a Variational Autoencoder approach and introducing Zero-Infated Truncated Gaussian likelihoods for the covariates to better ft the censored distributions.
|
|
