Search

It is known [Mangasarian, A Newton method for linear programming, J. Optim. Theory Appl. 121 (2004), pp. 1–18] that every linear program can be solved exactly by minimizing an unconstrained quadratic penalty program. The penalty program is parameterized by a scalar t>0, and one is able to solve the original linear program in this manner when t is selected larger than a finite, but unknown t 0 > 0. In this paper, we show that every linear program can be solved using the solution to a parameter-free penalty program. We also characterize the solutions to the quadratic penalty programs using fixed points of certain nonexpansive maps. This leads to an iterative thresholding algorithm that converges to a desired limit point. We show in numerical experiments that this iterative method can outperform a variety of standard quadratic program solvers. Finally, we show that for every t ∈ R , the solution one obtains by solving a parameterized penalty program is guaranteed to lie in the feasible set of the original linear program. [ABSTRACT FROM AUTHOR]

Many computer-aided diagnosis (CAD) problems can be best modelled as a multiple-instance learning (MIL) problem with unbalanced data, i.e., the training data typically consists of a few positive bags, and a very large number of negative instances. Existing MIL algorithms are much too computationally expensive for these datasets. We describe CH, a framework for learning a Convex Hull representation of multiple instances that is significantly faster than existing MIL algorithms. Our CH framework applies to any standard hyperplane-based learning algorithm, and for some algorithms, is guaranteed to find the global optimal solution. Experimental studies on two different CAD applications further demonstrate that the proposed algorithm significantly improves diagnostic accuracy when compared to both MIL and traditional classifiers. Although not designed for standard MIL problems (which have both positive and negative bags and relatively balanced datasets), comparisons against other MIL methods on benchmark problems also indicate that the proposed method is competitive with the state-of-the-art. Index Terms--Alternate optimization, convex hull, Fisher discriminant, multiple-instance learning (MIL).

Hail risk is among the most challenging perils to insure and property damage due to hailstones has been on the top of the list of annual claims for most non‐life insurers. In this article, we present a simple yet flexible statistical model for insurers to assess and manage hail risks from two aspects: analysing the insurance claims arrival pattern upon occurrence of a hailstorm and quantifying the subsequent financial impact of the hailstorm. We formulate the problem using a marked point process where the reporting of insurance claims due to a hailstorm is treated as recurrent events and the claim amounts are viewed as associated marks. Three complications are addressed in model building: the unobserved heterogeneity in claim arrival, the dependence between the event time and the mark and the complex distribution in claim amount. Using a unique data that combine the exposure data from a major US insurer and the radar data from a third‐party vendor, we show the proposed method help improve predictive analytics for post‐hailstorm claims volume, arrival rate and severity, and thus claim management decisions for the insurer. [ABSTRACT FROM AUTHOR]

Recommender systems have become extremely important to various types of industries where customer interaction and feedback is paramount to the success of the business. For companies that face changes that arise with ever‐growing markets, providing product recommendations to new and existing customers is a challenge. Our goal is to give our customers personalized recommendations based on what other similar people with similar portfolios have, in order to make sure they are adequately covered for their needs. Our system uses customer characteristics in addition to customer portfolio data. Since the number of possible recommendable products is relatively small, compared to other recommender domains, and missing data is relatively frequent, we chose to use Bayesian Networks for modeling our systems. We also present a deep‐learning‐based approach to provide recommendations to prospects (potential customers) where only external marketing data is available at the time of prediction. This article is categorized under:Application Areas > Industry Specific ApplicationsAlgorithmic Development > Structure DiscoveryAlgorithmic Development > Bayesian ModelsTechnologies > Machine Learning [ABSTRACT FROM AUTHOR]

Background: Highly parallel analysis of gene expression has recently been used to identify gene sets or 'signatures' to improve patient diagnosis and risk stratification. Once a signature is generated, traditional statistical testing is used to evaluate its prognostic performance. However, due to the dimensionality of microarrays, this can lead to false interpretation of these signatures. Principal Findings: A method was developed to test batches of a user-specified number of randomly chosen signatures in patient microarray datasets. The percentage of random generated signatures yielding prognostic value was assessed using ROC analysis by calculating the area under the curve (AUC) in six public available cancer patient microarray datasets. We found that a signature consisting of randomly selected genes has an average 10% chance of reaching significance when assessed in a single dataset, but can range from 1% to ∼40% depending on the dataset in question. Increasing the number of validation datasets markedly reduces this number. Conclusions: We have shown that the use of an arbitrary cut-off value for evaluation of signature significance is not suitable for this type of research, but should be defined for each dataset separately. Our method can be used to establish and evaluate signature performance of any derived gene signature in a dataset by comparing its performance to thousands of randomly generated signatures. It will be of most interest for cases where few data are available and testing in multiple datasets is limited. [ABSTRACT FROM AUTHOR]

We propose a novel privacy-preserving support vector machine (SVM) classifier for a data matrix A whose input feature columns are divided into groups belonging to different entities. Each entity is unwilling to share its group of columns or make it public. Our classifier is based on the concept of a reduced kernel K(A, B′), where B′ is the transpose of a random matrix B. The column blocks of B corresponding to the different entities are privately generated by each entity and never made public. The proposed linear or nonlinear SVM classifier, which is public but does not reveal any of the privately held data, has accuracy comparable to that of an ordinary SVM classifier that uses the entire set of input features directly. [ABSTRACT FROM AUTHOR]

This paper describes a support vector machine-based (SVM) parametric optimization method for semi-supervised classification, called LIAM (for linear hyperplane classifier with a priori metric information). Our method takes advantage of similarity information to leverage the unlabelled data in training SVMs. In addition to the smoothness constraints in existing semi-supervised methods, LIAM incorporates local class similarity constraints, that we empirically show, improved the accuracies in the presence of a few labelled points. We present and discuss a general convex mathematical-programming-based formulation to solve the inductive semi-supervised problem; i.e. our proposed algorithm directly classifies test samples not present when training. This general formulation results in different variants depending on the choice of the norms that are used in the objective function. For example, when using the 1-norm the proposed formulation becomes a linear programming problem that has the advantage of generating sparse solutions depending on a minimal set of the original features (feature selection). On the other hand, one of the proposed formulations results in an unconstrained quadratic problem for which solutions can be obtained by solving a simple system of linear equations, resulting in a fast competitive alternative to state-of-the-art semi-supervised algorithms. Our experiments on public benchmarks indicate that LIAM is at least one order of magnitude faster and at least as or more accurate (in most of the cases) than other state-of-the-art semi-supervised classification methods. [ABSTRACT FROM AUTHOR]

A finite concave minimization algorithm is proposed for constructing kernel classifiers that use a minimal number of data points both in generating and characterizing a classifier. The algorithm is theoretically justified on the basis of linear programming perturbation theory and a leave-one-out error bound as well as effective computational results on seven real world datasets. A nonlinear rectangular kernel is generated by systematically utilizing as few of the data as possible both in training and in characterizing a nonlinear separating surface. This can result in substantial reduction in kernel data-dependence (over 94% in six of the seven public datasets tested on) and with test set correctness equal to that obtained by using a conventional support vector machine classifier that depends on many more data points. This reduction in data dependence results in a much faster classifier that requires less storage. To eliminate data points, the proposed approach makes use of a novel loss function, the "pound" function (·)#, which is a linear combination of the 1-norm and the step function that measures both the magnitude and the presence of any error. [ABSTRACT FROM AUTHOR]

Abstract: Early detection of lung nodules is an important clinical indication for obtaining routine CT studies of the thorax. To date, research has mainly focused on the sensitivity of CAD compared with expert chest radiologists using data obtained from single or multi-detector CT scanners. But, beside sensitivity and specificity it is also import to know how well the CAD system does perform on datasets from different sites with different slice thicknesses and differences in the dosage. The present study focuses on the generalization ability of a prototype CAD system that is not yet commercially available. It describes the architecture of a recent CAD system and assesses the performance on a heterogeneous dataset collected from multiple geographically diverse sites. [Copyright &y& Elsevier]

Transformers have emerged as a preferred model for many tasks in natural langugage processing and vision. Recent efforts on training and deploying Transformers more efficiently have identified many strategies to approximate the self-attention matrix, a key module in a Transformer architecture. Effective ideas include various prespecified sparsity patterns, low-rank basis expansions and combinations thereof. In this paper, we revisit classical Multiresolution Analysis (MRA) concepts such as Wavelets, whose potential value in this setting remains underexplored thus far. We show that simple approximations based on empirical feedback and design choices informed by modern hardware and implementation challenges, eventually yield a MRA-based approach for self-attention with an excellent performance profile across most criteria of interest. We undertake an extensive set of experiments and demonstrate that this multi-resolution scheme outperforms most efficient self-attention proposals and is favorable for both short and long sequences. Code is available at https://github.com/mlpen/mra-attention.

Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences - a topic being actively studied in the community. To address this limitation, we propose Nyströmformer - a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with O ( n ) complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard self-attention. On longer sequence tasks in the Long Range Arena (LRA) benchmark, Nyströmformer performs favorably relative to other efficient self-attention methods. Our code is available at https://github.com/mlpen/Nystromformer.