We present a methodology for model evaluation and selection in binary classification models with the presence of correlations in the data, where the sampling mechanism violates the i.i.d. assumption. Our methodology involves a formulation of the bias term between the standard Cross-Validation (CV) estimator and the mean generalization error, and practical data-based procedures to estimate this term. Consequently, we present the bias-corrected CV estimator, which is the standard CV estimate supplemented by an estimate of the bias term. This concept was introduced in the literature only in the context of a linear model with squared error loss as the criterion for prediction performance. Our suggested bias-corrected CV estimator can be applied to any learning model, including deep neural networks, and to standard criteria for prediction performance for classification tasks, including misclassification rate, cross-entropy and hinge loss. We demonstrate the applicability of the proposed methodology in various scenarios where the data contains complex correlation structures (such as clustered and spatial relationships) with synthetic data and real-world datasets, providing evidence that the bias-corrected CV estimator is better than the standard CV estimator.

We introduce copula-based neural networks (COPNN), a novel framework that extends beyond the limitations of Gaussian marginals for random effects in mixed models. COPNN integrates the flexibility of Gaussian copulas in capturing rich dependence structures with arbitrary marginal distributions, with the expressive power of deep neural networks (DNN), allowing it to model large non-Gaussian data in both regression and classification settings, while using batch learning and stochastic gradient descent. Unlike traditional linear and non-linear mixed models, which assume Gaussianity for random effects, COPNN leverages copulas to decouple the marginal distribution from the dependence structure, caused by spatial, temporal and high-cardinality categorical features. This is achieved by minimizing a batch negative log-likelihood (NLL) loss in the continuous case, and a batch negative pairwise log-likelihood in the binary case. We demonstrate COPNN’s effectiveness through extensive experiments on both simulated and real datasets. COPNN reduces NLL and MSE in the regression setting, and improves predictive accuracy in the classification setting, compared to previous state of the art methods which integrate random effects into DNN. Our real-world experiments, conducted on datasets from automotive pricing and retail traffic forecasting, further validate COPNN’s ability to improve performance over traditional methods for dealing with high-cardinality categorical features.

Accurate and reliable probability predictions are essential for multi-class supervised learning tasks, where well-calibrated models enable rational decision-making. While isotonic regression has proven effective for binary calibration, its extension to multi-class problems via one-vs-rest calibration often produces suboptimal results, limiting its practical adoption. In this work, we propose novel isotonic normalization-aware techniques for multi-class calibration, grounded in natural and intuitive assumptions expected by practitioners. Unlike prior approaches, our methods inherently account for probability normalization by either incorporating normalization directly into the optimization process (NA-FIR) or modeling the problem as a cumulative bivariate isotonic regression (SCIR). Empirical evaluations on a variety of text and image classification datasets across different model architectures reveal that our approach consistently improves log loss and expected calibration error (ECE) metrics. These findings underscore the potential of our approach to enhance a-parametric multi-class calibration practices, offering an adaptable solution for real-world applications.

Modern approaches to supervised learning like deep neural networks (DNNs) typically implicitly assume that observed responses are statistically independent. In contrast, correlated data are prevalent in real-life large-scale applications, with typical sources of correlation including spatial, temporal and clustering structures. These correlations are either ignored by DNNs, or ad-hoc solutions are developed for specific use cases. We propose to use the mixed models framework to handle correlated data in DNNs. By treating the effects underlying the correlation structure as random effects, mixed models are able to avoid overfitted parameter estimates and ultimately yield better predictive performance. The key to combining mixed models and DNNs is using the Gaussian negative log-likelihood (NLL) as a natural loss function that is minimized with DNN machinery including stochastic gradient descent (SGD). Since NLL does not decompose like standard DNN loss functions, the use of SGD with NLL presents some theoretical and implementation challenges, which we address. Our approach which we call LMMNN is demonstrated to improve performance over natural competitors in various correlation scenarios on diverse simulated and real datasets. Our focus is on a regression setting and tabular datasets, but we also show some results for classification. Our code is available at https://github.com/gsimchoni/lmmnn.

This paper presents a new approach for regression tree-based models, such as simple regression tree, random forest and gradient boosting, in settings involving correlated data. We show the problems that arise when implementing standard regression tree-based models, which ignore the correlation structure. Our new approach explicitly takes the correlation structure into account in the splitting criterion, stopping rules and fitted values in the leaves, which induces some major modifications of standard methodology. The superiority of our new approach over tree-based models that do not account for the correlation, and over previous work that integrated some aspects of our approach, is supported by simulation experiments and real data analyses.

High-cardinality categorical features are a major challenge for machine learning methods in general and for deep learning in particular. Existing solutions such as one-hot encoding and entity embeddings can be hard to scale when the cardinality is very high, require much space, are hard to interpret or may overfit the data. A special scenario of interest is that of repeated measures, where the categorical feature is the identity of the individual or object, and each object is measured several times, possibly under different conditions (values of the other features). We propose accounting for high-cardinality categorical features as random effects variables in a regression setting, and consequently adopt the corresponding negative log likelihood loss from the linear mixed models (LMM) statistical literature and integrate it in a deep learning framework. We test our model which we call LMMNN on simulated as well as real datasets with a single categorical feature with high cardinality, using various baseline neural networks architectures such as convolutional networks and LSTM, and various applications in e-commerce, healthcare and computer vision. Our results show that treating high-cardinality categorical features as random effects leads to a significant improvement in prediction performance compared to state of the art alternatives. Potential extensions such as accounting for multiple categorical features and classification settings are discussed. Our code and simulations are available at https://github.com/gsimchoni/lmmnn.

Typically, real-world stochastic processes are not easy to analyze. In this paper, we study the representation of different stochastic process as a memoryless innovation process triggering a dynamic system. We show that such a representation is always feasible for innovation processes taking values over a continuous set. However, the problem becomes more challenging when the alphabet size of the innovation is finite. In this case, we introduce both lossless and lossy frameworks, and provide closed-form solutions and practical algorithmic methods. In addition, we discuss the properties and uniqueness of our suggested approach. Finally, we show that the innovation representation problem has many applications. We focus our attention on entropic causal inference, which has recently demonstrated promising performance, compared to alternative methods.

Modern data sets in various domains often include units that were sampled non-randomly from the population and have a latent correlation structure. Here we investigate a common form of this setting, where every unit is associated with a latent variable, all latent variables are correlated, and the probability of sampling a unit depends on its response. Such settings often arise in case-control studies, where the sampled units are correlated due to spatial proximity, family relations, or other sources of relatedness. Maximum likelihood estimation in such settings is challenging from both a computational and statistical perspective, necessitating approximations that take the sampling scheme into account. We propose a family of approximate likelihood approaches which combine composite likelihood and expectation propagation. We demonstrate the efficacy of our solutions via extensive simulations. We utilize them to investigate the genetic architecture of several complex disorders collected in case-control genetic association studies, where hundreds of thousands of genetic variants are measured for every individual, and the underlying disease liabilities of individuals are correlated due to genetic similarity. Our work is the first to provide a tractable likelihood-based solution for case-control data with complex dependency structures.

The problem of handling adaptivity in data analysis, intentional or not, permeates a variety of fields, including test-set overfitting in ML challenges and the accumulation of invalid scientific discoveries. We propose a mechanism for answering an arbitrarily long sequence of potentially adaptive statistical queries, by charging a price for each query and using the proceeds to collect additional samples. Crucially, we guarantee statistical validity without any assumptions on how the queries are generated. We also ensure with high probability that the cost for $M$ non-adaptive queries is $O(\log M)$, while the cost to a potentially adaptive user who makes $M$ queries that do not depend on any others is $O(\sqrt{M})$.

MOTIVATION: Epigenome-wide association studies can provide novel insights into the regulation of genes involved in traits and diseases. The rapid emergence of bisulfite-sequencing technologies enables performing such genome-wide studies at the resolution of single nucleotides. However, analysis of data produced by bisulfite-sequencing poses statistical challenges owing to low and uneven sequencing depth, as well as the presence of confounding factors. The recently introduced Mixed model Association for Count data via data AUgmentation (MACAU) can address these challenges via a generalized linear mixed model when confounding can be encoded via a single variance component. However, MACAU cannot be used in the presence of multiple variance components. Additionally, MACAU uses a computationally expensive Markov Chain Monte Carlo (MCMC) procedure, which cannot directly approximate the model likelihood. RESULTS: We present a new method, Mixed model Association via a Laplace ApproXimation (MALAX), that is more computationally efficient than MACAU and allows to model multiple variance components. MALAX uses a Laplace approximation rather than MCMC based approximations, which enables to directly approximate the model likelihood. Through an extensive analysis of simulated and real data, we demonstrate that MALAX successfully addresses statistical challenges introduced by bisulfite-sequencing while controlling for complex sources of confounding, and can be over 50% faster than the state of the art. AVAILABILITY AND IMPLEMENTATION: The full source code of MALAX is available at https://github.com/omerwe/MALAX . CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Recursive partitioning methods producing tree-like models are a long standing staple of predictive modeling. However, a fundamental flaw in the partitioning (or splitting) rule of commonly used tree building methods precludes them from treating different types of variables equally. This most clearly manifests in these methods' inability to properly utilize categorical variables with a large number of categories, which are ubiquitous in the new age of big data. We propose a framework to splitting using leave-one-out (LOO) cross validation (CV) for selecting the splitting variable, then performing a regular split (in our case, following CART's approach) for the selected variable. The most important consequence of our approach is that categorical variables with many categories can be safely used in tree building and are only chosen if they contribute to predictive power. We demonstrate in extensive simulation and real data analysis that our splitting approach significantly improves the performance of both single tree models and ensemble methods that utilize trees. Importantly, we design an algorithm for LOO splitting variable selection which under reasonable assumptions does not substantially increase the overall computational complexity compared to CART for two-class classification.

Large alphabet source coding is a basic and well-studied problem in data compression. It has many applications, such as compression of natural language text, speech, and images. The classic perception of most commonly used methods is that a source is best described over an alphabet, which is at least as large as the observed alphabet. In this paper, we challenge this approach and introduce a conceptual framework in which a large alphabet source is decomposed into “as statistically independent as possible” components. This decomposition allows us to apply entropy encoding to each component separately, while benefiting from their reduced alphabet size. We show that in many cases, such decomposition results in a sum of marginal entropies which is only slightly greater than the entropy of the source. Our suggested algorithm, based on a generalization of the binary independent component analysis, is applicable for a variety of large alphabet source coding setups. This includes the classical lossless compression, universal compression, and high-dimensional vector quantization. In each of these setups, our suggested approach outperforms most commonly used methods. Moreover, our proposed framework is significantly easier to implement in most of these cases.

Encoding a sequence of independent symbols over a large alphabet size is a challenging problem with applications in many fields. The most widely used adaptive entropy coding techniques (namely, arithmetic and Huffman coding) are known to achieve an average codeword length which may be significantly greater than the empirical entropy of the sequence, as the alphabet size increases. In this work we introduce an efficient and easy-to-implement method for large alphabet adaptive encoding. We propose a conceptual framework in which a sequence of symbols, over a large alphabet size, is decomposed into multiple "almost independent" sequences over a smaller alphabet. Then each of these sequences is encoded separately. This way, we allow encoding of small alphabet sequences, at the cost of the "remaining dependence" among the sequences. We demonstrate the advantages of our suggested scheme through a series of theorems and experiments, showing it reduces both the average codeword length and the compression runtime in many large alphabet setups.

Ensemble methods are considered among the state-of-the-art predictive modeling approaches. Applied to modern big data, these methods often require a large number of sub-learners, where the complexity of each learner typically grows with the size of the dataset. This phenomenon results in an increasing demand for storage space, which may be very costly. This problem mostly manifests in a subscriber based environment, where a user-specific ensemble needs to be stored on a personal device with strict storage limitations (such as a cellular device). In this work we introduce a novel method for lossless compression of tree-based ensemble methods, focusing on Random Forests. Our suggested method is based on probabilistic modeling of the ensemble's trees, followed by model clustering via Bregman divergence. This allows us to find a minimal set of models that provides an accurate description of the trees, and at the same time is small enough to store and maintain. Our compression scheme demonstrates high compression rates on a variety of modern datasets. Importantly, our scheme enables predictions from the compressed format and a perfect reconstruction of the original ensemble.

In this paper we present an algorithmic approach for fitting isotonic models under convex, yet non-differentiable, loss functions. It is a generalization of the greedy non-regret approach proposed by Luss and Rosset (2014) for differentiable loss functions, taking into account the sub-gradiental extensions required. We prove that our suggested algorithm solves the isotonic modeling problem while maintaining favorable computational and statistical properties. As our suggested algorithm may be used for any non-differentiable loss function, we focus our interest on isotonic modeling for either regression or two-class classification with appropriate log-likelihood loss and lasso penalty on the fitted values. This combination allows us to maintain the non-parametric nature of isotonic modeling, while controlling model complexity through regularization. We demonstrate the efficiency and usefulness of this approach on both synthetic and real world data. An implementation of our suggested solution is publicly available from the first author's website (https://sites.google.com/site/amichaipainsky/software).

Independent component analysis (ICA) is a statistical method for transforming an observable multi-dimensional random vector into components that are as statistically independent as possible from each other. Usually, the ICA framework assumes a model according to which the observations are generated (such as a linear transformation with additive noise). ICA over finite fields is a special case of ICA in which both the observations and the independent components are over a finite alphabet. In this paper, we consider a generalization of this framework in which an observation vector is decomposed to its independent components (as much as possible) with no prior assumption on the way it was generated. This generalization is also known as Barlow's minimal redundancy representation problem and is considered an open problem. We propose several theorems and show that this hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. Our contribution provides the first efficient set of solutions to Barlow's problem. The minimal redundancy representation (also known as factorial code) has many applications, mainly in the fields of neural networks and deep learning. The binary ICA is also shown to have applications in several domains, including medical diagnosis, multi-cluster assignment, network tomography, and internet resource management. In this paper, we show that this formulation further applies to multiple disciplines in source coding, such as predictive coding, distributed source coding, and coding of large alphabet sources.

Many applications of universal compression involve sources such as text, speech and image, whose alphabet is extremely large. In this work we propose a conceptual framework in which a large alphabet memory less source is decomposed into multiple 'as independent as possible' sources whose alphabet is much smaller. This way we slightly increase the average codeword length as the compressed symbols are no longer perfectly independent, but at the same time significantly reduce the overhead redundancy resulted by the large alphabet of the observed source. Our proposed algorithm, based on a generalization of the Binary Independent Component Analysis, shows to efficiently find the ideal trade-off so that the overall compression size is minimal. We demonstrate our framework on memory less draws from a variety of natural languages and show that the redundancy we achieve is remarkably smaller than most commonly used methods.

Independent component analysis (ICA) is a statistical method for transforming an observed multidimensional random vector into components that are as statistically independent as possible from each other. Usually the ICA framework assumes a model according to which the observations are generated (generative function, additive noise). Binary ICA (BICA) is a special case of ICA in which both the observations and the independent components are over the binary field GF(2). In this work we introduce a generalized BICA framework in which an observation vector is decomposed to its independent components (as much as possible) with no prior assumption on the way it was generated. We propose several theorems and show that this NP hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear programs. BICA was shown to have applications in many domains including medical diagnosis, multi-cluster assignment, network tomography and internet resource management. We suggest that BICA also applies in source coding; we argue that instead of generating statistically independent prediction errors, as in predictive coding, an improved encoder shall assemble a vector of observations and apply the generalized BICA on it. This is shown to achieve improved performance at the cost of introducing some time delay (working in batch).

Memoryless processes hold many theoretical and practical advantages. They are easy to describe, analyze, store and encrypt. They can also be seen as the essence of a family of regression processes, or as an innovation process triggering a dynamic system. The Gram-Schmidt procedure suggests a linear sequential method of whitening (decorrelating) any stochastic process. Applied on a Gaussian process, memorylessness (that is, statistical independence) is guaranteed. It is not clear however, how to sequentially construct a memoryless process from a non-Gaussian process. In this paper we present a non-linear sequential method to generate a memoryless process from any given Markov process under varying objectives and constraints. We differentiate between lossless and lossy methods, closed form and algorithmic solutions and discuss the properties and uniqueness of our suggested methods.

The availability of large microarray data has led to a growing interest in biclustering methods in the past decade. Several algorithms have been proposed to identify subsets of genes and conditions according to different similarity measures and under varying constraints. In this paper we focus on the exclusive row biclusteing problem (also known as projected clustering) for gene expression data sets, in which each row can only be a member of a single bicluster while columns can participate in multiple clusters. This type of biclustering may be adequate, for example, for clustering groups of cancer patients where each patient (row) is expected to be carrying only a single type of cancer, while each cancer type is associated with multiple (and possibly overlapping) genes (columns). In this paper we present a novel method to identify these exclusive row biclusters through a combination of existing biclustering algorithms and combinatorial auction techniques. We devise an approach for tuning the threshold for our algorithm based on comparison to a null model in the spirit of the Gap statistic approach. We demonstrate our approach on both synthetic and real-world gene expression data and show its power in identifying large span non-overlapping rows sub matrices, while considering their unique nature. The Gap statistic approach succeeds in identifying appropriate thresholds in all our examples.

MOTIVATION: Despite the rapid decline in sequencing costs, sequencing large cohorts of individuals is still prohibitively expensive. Recently, several sophisticated pooling designs were suggested that can identify carriers of rare alleles in large cohorts with a significantly smaller number of pools, thus dramatically reducing the cost of such large-scale sequencing projects. These approaches use combinatorial pooling designs where each individual is either present or absent from a pool. One can then infer the number of carriers in a pool, and by combining information across pools, reconstruct the identity of the carriers. RESULTS: We show that one can gain further efficiency and cost reduction by using 'weighted' designs, in which different individuals donate different amounts of DNA to the pools. Intuitively, in this situation, the number of mutant reads in a pool does not only indicate the number of carriers, but also their identity. We describe and study a powerful example of such weighted designs, using non-overlapping pools. We demonstrate that this approach is not only easier to implement and analyze but is also competitive in terms of accuracy with combinatorial designs when identifying rare variants, and is superior when sequencing common variants. We then discuss how weighting can be incorporated into existing combinatorial designs to increase their accuracy and demonstrate the resulting improvement using simulations. Finally, we argue that weighted designs have enough power to facilitate detection of common alleles, so they can be used as a cornerstone of whole-exome sequencing projects.

Deemed “one of the top ten data mining mistakes”, leakage is the introduction of information about the data mining target that should not be legitimately available to mine from. In addition to our own industry experience with real-life projects, controversies around several major public data mining competitions held recently such as the INFORMS 2010 Data Mining Challenge and the IJCNN 2011 Social Network Challenge are evidence that this issue is as relevant today as it has ever been. While acknowledging the importance and prevalence of leakage in both synthetic competitions and real-life data mining projects, existing literature has largely left this idea unexplored. What little has been said turns out not to be broad enough to cover more complex cases of leakage, such as those where the classical independently and identically distributed (i.i.d.) assumption is violated, that have been recently documented. In our new approach, these cases and others are explained by explicitly defining modeling goals and analyzing the broader framework of the data mining problem. The resulting definition enables us to derive general methodology for dealing with the issue. We show that it is possible to avoid leakage with a simple specific approach to data management followed by what we call a learn-predict separation, and present several ways of detecting leakage when the modeler has no control over how the data have been collected. We also offer an alternative point of view on leakage that is based on causal graph modeling concepts.

Deemed "one of the top ten data mining mistakes", leakage is essentially the introduction of information about the data mining target, which should not be legitimately available to mine from. In addition to our own industry experience with real-life projects, controversies around several major public data mining competitions held recently such as the INFORMS 2010 Data Mining Challenge and the IJCNN 2011 Social Network Challenge are evidence that this issue is as relevant today as it has ever been. While acknowledging the importance and prevalence of leakage in both synthetic competitions and real-life data mining projects, existing literature has largely left this idea unexplored. What little has been said turns out not to be broad enough to cover more complex cases of leakage, such as those where the classical i.i.d. assumption is violated, that have been recently documented. In our new approach, these cases and others are explained by explicitly defining modeling goals and analyzing the broader framework of the data mining problem. The resulting definition enables us to derive general methodology for dealing with the issue. We show that it is possible to avoid leakage with a simple specific approach to data management followed by what we call a learn-predict separation, and present several ways of detecting leakage when the modeler has no control over how the data have been collected.

MOTIVATION: Random effects models have recently been introduced as an approach for analyzing genome wide association studies (GWASs), which allows estimation of overall heritability of traits without explicitly identifying the genetic loci responsible. Using this approach, Yang et al. (2010) have demonstrated that the heritability of height is much higher than the ~10% associated with identified genetic factors. However, Yang et al. (2010) relied on a heuristic for performing estimation in this model. RESULTS: We adopt the model framework of Yang et al. (2010) and develop a method for maximum-likelihood (ML) estimation in this framework. Our method is based on Monte-Carlo expectation-maximization (MCEM; Wei et al., 1990), an expectation-maximization algorithm wherein a Markov chain Monte Carlo approach is used in the E-step. We demonstrate that this method leads to more stable and accurate heritability estimation compared to the approach of Yang et al. (2010), and it also allows us to find ML estimates of the portion of markers which are causal, indicating whether the heritability stems from a small number of powerful genetic factors or a large number of less powerful ones. CONTACT: [email protected].

The common scenario in computational biology in which a community of researchers conduct multiple statistical tests on one shared database gives rise to the multiple hypothesis testing problem. Conventional procedures for solving this problem control the probability of false discovery by sacrificing some of the power of the tests. We suggest a scheme for controlling false discovery without any power loss by adding new samples for each use of the database and charging the user with the expenses. The crux of the scheme is a carefully crafted pricing system that fairly prices different user requests based on their demands while keeping the probability of false discovery bounded. We demonstrate this idea in the context of HIV treatment research, where multiple researchers conduct tests on a repository of HIV samples.

A new algorithm for isotonic regression is presented based on recursively partitioning the solution space. We develop efficient methods for each partitioning subproblem through an equivalent representation as a network flow problem, and prove that this sequence of partitions converges to the global solution. These network flow problems can further be decomposed in order to solve very large problems. Success of isotonic regression in prediction and our algorithm's favorable computational properties are demonstrated through simulated examples as large as 2x10^5 variables and 10^7 constraints.

MOTIVATION: Y-chromosome short tandem repeats (Y-STRs) are widely used for population studies, forensic purposes and, potentially, the study of disease, therefore knowledge of their mutation rate is valuable. Here we show a novel method for estimation of site-specific Y-STR mutation rates from partial phylogenetic information, via the maximum likelihood framework. RESULTS: Given Y-STR data classified into haplogroups, we de-scribe the likelihood of observed data, and develop optimization strategies for deriving maximum likelihood estimates of mutation rates. We apply our method to Y-STR data from two recent papers. We show that our estimates are comparable, often more accurate than those obtained in familial studies, although our data sample is much smaller, and was not collected specifically for our study. Furthermore, we obtain mutation rate estimates for DYS388, DYS426, DYS457, three STRs for which there were no mutation rate measures until now.

We develop and evaluate an approach to causal modeling based on time series data, collectively referred to as "grouped graphical Granger modeling methods." Graphical Granger modeling uses graphical modeling techniques on time series data and invokes the notion of "Granger causality" to make assertions on causality among a potentially large number of time series variables through inference on time-lagged effects. The present paper proposes a novel enhancement to the graphical Granger methodology by developing and applying families of regression methods that are sensitive to group information among variables, to leverage the group structure present in the lagged temporal variables according to the time series they belong to. Additionally, we propose a new family of algorithms we call group boosting, as an improved component of grouped graphical Granger modeling over the existing regression methods with grouped variable selection in the literature (e.g group Lasso). The introduction of group boosting methods is primarily motivated by the need to deal with non-linearity in the data. We perform empirical evaluation to confirm the advantage of the grouped graphical Granger methods over the standard (non-grouped) methods, as well as that specific to the methods based on group boosting. This advantage is also demonstrated for the real world application of gene regulatory network discovery from time-course microarray data.

We consider the problem of discovering gene regulatory networks from time-series microarray data. Recently, graphical Granger modeling has gained considerable attention as a promising direction for addressing this problem. These methods apply graphical modeling methods on time-series data and invoke the notion of 'Granger causality' to make assertions on causality through inference on time-lagged effects. Existing algorithms, however, have neglected an important aspect of the problem--the group structure among the lagged temporal variables naturally imposed by the time series they belong to. Specifically, existing methods in computational biology share this shortcoming, as well as additional computational limitations, prohibiting their effective applications to the large datasets including a large number of genes and many data points. In the present article, we propose a novel methodology which we term 'grouped graphical Granger modeling method', which overcomes the limitations mentioned above by applying a regression method suited for high-dimensional and large data, and by leveraging the group structure among the lagged temporal variables according to the time series they belong to. We demonstrate the effectiveness of the proposed methodology on both simulated and actual gene expression data, specifically the human cancer cell (HeLa S3) cycle data. The simulation results show that the proposed methodology generally exhibits higher accuracy in recovering the underlying causal structure. Those on the gene expression data demonstrate that it leads to improved accuracy with respect to prediction of known links, and also uncovers additional causal relationships uncaptured by earlier works.

Modeling of conditional quantiles requires specification of the quantile being estimated and can thus be viewed as a parameterized predictive modeling problem. Quantile loss is typically used, and it is indeed parameterized by a quantile parameter. In this paper we show how to follow the path of cross validated solutions to regularized kernel quantile regression. Even though the bi-level optimization problem we encounter for every quantile is non-convex, the manner in which the optimal cross-validated solution evolves with the parameter of the loss function allows tracking of this solution. We prove this property, construct the resulting algorithm, and demonstrate it on data. This algorithm allows us to efficiently solve the whole family of bi-level problems.

We consider the problem of predicting the likelihood that a company will purchase a new product from a seller. The statistical models we have developed at IBM for this purpose rely on historical transaction data coupled with structured firmographic information like the company revenue, number of employees and so on. In this paper, we extend this methodology to include additional text-based features based on analysis of the content on each company's website. Empirical results demonstrate that incorporating such web content can significantly improve customer targeting. Furthermore, we present methods to actively select only the web content that is likely to improve our models, while reducing the costs of acquisition and processing.

In this paper we discuss the important practical problem of customer wallet estimation, i.e., estimation of potential spending by customers(rather than their expected spending). For this purpose we utilize quantile modeling, whose goal is to estimate a quantile of the discriminative conditional distribution of the response, rather than the mean, which is the implicit goal of most standard regression approaches. We argue that a notion of wallet can be captured through high quantile modeling (e.g, estimating the 90th percentile), and describe a wallet estimation implementation within IBM's Market Alignment Program (MAP). We also discuss the wide range of domains where high-quantile modeling can be practically important: estimating opportunities in sales and marketing domains, defining 'surprising' patterns for outlier and fraud detection and more. We survey some existing approaches for quantile modeling, and propose adaptations of nearest-neighbor and regression-tree approaches to quantile modeling. We demonstrate the various models' performance in high quantile estimation in several domains, including our motivating problem of estimating the 'realistic' IT wallets of IBM customers.

Mass-produced goods tend to be highly standardized in order to maximize manufacturing efficiencies. Some high-value goods with limited production quantities remain much less standardized and each sale can be configured to meet the specific requirements of the customer. In this work we suggest a novel methodology to reduce the number of options for complex product configurations by identifying meaningful sets of options that exhibit strong empirical dependencies in previous customer orders. Our approach explores different measures from statistics and information theory to capture the degree of interdependence between the choices for any pair of product components. We use hierarchical clustering to identify meaningful sets of components that can be combined to decrease the number of unique product specifications and increase production standardization. The focus of our analysis is on the influence of different similarity measure - including chi-squared statistics and versions of mutual information - on the ability of the clustering to find meaningful clusters.

MOTIVATION: We suggest the use of Poisson regression for time inference and hypothesis testing on a bifurcating Phylogenetic tree with known topology. This method is computationally simple and naturally accommodates variable substitution rates across different sites, without requiring the estimation of these rates. We identify the assumptions under which this is a maximum-likelihood inference approach and show that in some realistic situations--in particular, when the probability of repeated mutation within each branch of the tree is small--these assumptions hold with high probability. RESULTS: Our motivating domain is human mitochondrial DNA trees, and we illustrate our method on a problem of estimating the time to most recent common ancestor of all non-African mtDNA, using publicly available data. We test for molecular clock violations using multiple comparisons, and conclude that the global molecular clock hypothesis cannot be rejected based on these data.

Motivated by the problem of customer wallet estimation, we propose a new setting for multi-view regression, where we learn a completely unobserved target (in our case, customer wallet) by modeling it as a "central link" in a directed graphical model, connecting multiple sets of observed variables. The resulting conditional independence allows us to reduce the maximum discriminative likelihood estimation problem to a convex optimization problem for exponential linear models. We show that under certain modeling assumptions, in particular, when there exist two conditionally independent views and the noise is Gaussian, this problem can be reduced to a single least squares regression. Thus, for this specific, but widely applicable setting, the "unsupervised" multi-view problem can be solved via a simple supervised learning approach. This reduction also allows us to test the statistical independence assumptions underlying the graphical model and perform variable selection. We demonstrate the effectiveness of our approach on our motivating problem of customer wallet estimation and on simulation data.

We describe and analyze the idea of data-enhanced predictive modeling (DEM). The term “enhanced” here refers to the case that the data used for modeling is sampled not from the true target population, but from an alternative (closely related) population, from which much larger samples are available. This leads to a “bias-variance” tradeoff, which implies that in some cases, DEM can improve predictive performance on the true target population. We theoretically analyze this tradeoff for the case of linear regression. We illustrate DEM on a problem of sales targeting for a set of software products. The “correct” learning problem is to differentiate non-customers from newly acquired customers. The latter, however, are scarce. We illustrate how we can build better prediction models by using more flexible definitions of interesting targets, which give bigger learning samples.

We suggest the use of ranking-based evaluation measures for regression models, as a complement to the commonly used residual-based evaluation. We argue that in some cases, such as the case study we present, ranking can be the main underlying goal in building a regression model, and ranking performance is the correct evaluation metric. However, even when ranking is not the contextually correct performance metric, the measures we explore still have significant advantages: They are robust against extreme outliers in the evaluation set; and they are interpretable. The two measures we consider correspond closely to non-parametric correlation coefficients commonly used in data analysis (Spearman's p and Kendall's r); and they both have interesting graphical representations, which, similarly to ROC curves, offer useful "partial" model performance views, in addition to a one-number summary in the area under the curve. We illustrate our methods on a case study of evaluating IT wallet size estimation models for IBM's customers.

This paper is about constructing confidence bands around ROC curves. We first introduce to the machine learning community three band-generating methods from the medical field, and evaluate how well they perform. Such confidence bands represent the region where the "true" ROC curve is expected to reside, with the designated confidence level. To assess the containment of the bands we begin with a synthetic world where we know the true ROC curve---specifically, where the class-conditional model scores are normally distributed. The only method that attains reasonable containment out-of-the-box produces non-parametric, "fixed-width" bands (FWBs). Next we move to a context more appropriate for machine learning evaluations: bands that with a certain confidence level will bound the performance of the model on future data. We introduce a correction to account for the larger uncertainty, and the widened FWBs continue to have reasonable containment. Finally, we assess the bands on 10 relatively large benchmark data sets. We conclude by recommending these FWBs, noting that being non-parametric they are especially attractive for machine learning studies, where the score distributions (1) clearly are not normal, and (2) even for the same data set vary substantially from learning method to learning method.

Several authors have suggested viewing boosting as a gradient descent search for a good fit in function space. At each iteration observations are re-weighted using the gradient of the underlying loss function. We present an approach of weight decay for observation weights which is equivalent to "robustifying" the underlying loss function. At the extreme end of decay this approach converges to Bagging, which can be viewed as boosting with a linear underlying loss function. We illustrate the practical usefulness of weight decay for improving prediction performance and present an equivalence between one form of weight decay and "Huberizing" --- a statistical method for making loss functions more robust.

We present a statistical analysis of the AUC as an evaluation criterion for classification scoring models. First, we consider significance tests for the dierence between AUC scores of two algorithms on the same test set. We derive exact moments under simplifying assumptions and use them to examine approximate practical methods from the literature. We then compare AUC to empirical misclassification error when the prediction goal is to minimize future error rate. We show that the AUC may be preferable to empirical error even in this case and discuss the tradeoff between approximation error and estimation error underlying this phenomenon.

In this paper we argue that the choice of the SVM cost parameter can be critical. We then derive an algorithm that can fit the entire path of SVM solutions for every value of the cost parameter, with essentially the same computational cost as fitting one SVM model.

Regularization plays a central role in the analysis of modern data, where non-regularized fitting is likely to lead to over-fitted models, useless for both prediction and interpretation. We consider the design of incremen- tal algorithms which follow paths of regularized solutions, as the regu- larization varies. These approaches often result in methods which are both efficient and highly flexible. We suggest a general path-following algorithm based on second-order approximations, prove that under mild conditions it remains "very close" to the path of optimal solutions and illustrate it with examples. 1 Introduction Given a data sample (xi, yi)n i=1 (with xi Rp and yi R for regression, yi {1} for classification), the generic regularized optimization problem calls for fitting models to the data while controlling complexity by solving a penalized fitting problem: ^ (1) () = arg min C(yi, xi) + J() i where C is a convex loss function and J is a convex model complexity penalty (typically taken to be the lq norm of , with q 1).1 Many commonly used supervised learning methods can be cast in this form, including regularized 1-norm and 2-norm support vector machines [13, 4], regularized linear and logistic regression (i.e. Ridge regression, lasso and their logistic equivalents) and more. In [8] we show that boosting can also be described as approximate regularized optimization, with an l1-norm penalty. Detailed discussion of the considerations in selecting penalty and loss functions for regu- larized fitting is outside the scope of this paper. In general, there are two main areas we need to consider in this selection: Statistical considerations: robustness (which affects selection of loss), sparsity (l1-norm penalty encourages sparse solutions) and identifiability are among the questions we should 1We assume a linear model in (1), but this is much less limiting than it seems, as the model can be linear in basis expansions of the original predictors, and so our approach covers Kernel methods, wavelets, boosting and more keep in mind when selecting our formulation. 2. Computational considerations: we should be able to solve the problems we pose with the computational resources at our disposal. Kernel methods and boosting are examples of computational tricks that allow us to solve very high dimensional problems exactly or approximately with a relatively small cost. In this paper we suggest a new computational approach. Once we have settled on a loss and penalty, we are still faced with the problem of select- ing a "good" regularization parameter , in terms of prediction performance. A common approach is to solve (1) for several values of , then use holdout data (or theoretical ap- proaches, like AIC or SRM) to select a good value. However, if we view the regularized optimization problem as a family of problems, parameterized by the regularization parame- ter , it allows us to define the "path" of optimal solutions { ^ () : 0 }, which is a 1-dimensional curve through Rp. Path following methods attempt to utilize the mathemat- ical properties of this curve to devise efficient procedures for "following" it and generating the full set of regularized solutions with a (relatively) small computational cost. As it turns out, there is a family of well known and interesting regularized problems for which efficient exact path following algorithms can be devised. These include the lasso [3], 1- and 2-norm support vector machines [13, 4] and many others [9]. The main property of these problems which makes them amenable to such methods is the piecewise linearity of the regularized solution path in Rp. See [9] for detailed exposition of these properties and the resulting algorithms. However, the path following idea can stretch beyond these exact piecewise linear algo- rithms. The "first order" approach is to use gradient-based approaches. In [8] we have described boosting as an approximate gradient-based algorithm for following l1-norm reg- ularized solution paths. [6] suggest a gradient descent algorithm for finding an optimal so- lution for a fixed value of and are seemingly unaware that the path they are going through is of independent interest as it consists of approximate (alas very approximate) solutions to l1-regularized problems. Gradient-based methods, however, can only follow regularized paths under strict and non-testable conditions, and theoretical "closeness" results to the optimal path are extremely difficult to prove for them (see [8] for details). In this paper, we suggest a general second-order algorithm for following "curved" regu- larized solution paths (i.e. ones that cannot be followed exactly by piecewise-linear al- gorithms). It consists of iteratively changing the regularization parameter, while making a single Newton step at every iteration towards the optimal penalized solution, for the current value of . We prove that if both the loss and penalty are "nice" (in terms of bounds on their relevant derivatives in the relevant region), then the algorithm is guaranteed to stay "very close" to the true optimal path, where "very close" is defined as: If the change in the regularization parameter at every iteration is , then the solution path we generate is guaranteed to be within O( 2) from the true path of penalized optimal solutions In section 2 we present the algorithm, and we then illustrate it on l1- and l2-regularized logistic regression in section 3. Section 4 is devoted to a formal statement and proof outline of our main result. We discuss possible extensions and future work in section 5. 2 Path following algorithm We assume throughout that the loss function C is twice differentiable. Assume for now also that the penalty J is twice differentiable (this assumption does not apply to the l1- norm penalty which is of great interest and we address this point later). The key to our method are the normal equations for (1): (2) C( ^ ()) + J( ^ ()) = 0 Our algorithm iteratively constructs an approximate solution ( ) t by taking "small" Newton-Raphson steps trying to maintain (2) as the regularization changes. Our main result in this paper is to show, both empirically and theoretically, that for small , the dif- ference ( ) t - ^ (0 + t) is small, and thus that our method successfully tracks the path of optimal solutions to (1). Algorithm 1 gives a formal description of our quadratic tracking method. We start from a solution to (1) for some fixed 0 (e.g. ^ (0), the non-regularized solution). At each iteration we increase by and take a single Newton-Raphson step towards the solution to (2) with the new value in step 2(b). Algorithm 1 Approximate incremental quadratic algorithm for regularized optimization 1. Set ( ) 0 = ^ (0), set t = 0. 2. While (t < max) (a) t+1 = t + (b) ( ) t+1 = -1 ( ) 2 t - 2C(( ) t ) + t+1 J(( ) t ) C(( ) t ) + t+1 J(( ) t ) (c) t = t + 1 2.1 The l1-norm penalty The l1-norm penalty, J() = 1, is of special interest because of its favorable statistical properties (e.g. [2]) and its widespread use in popular methods, such as the lasso [10] and 1-norm SVM [13]. However it is not differentiable and so our algorithm does not apply to l1-penalized problems directly. To understand how we can generalize Algorithm 1 to this situation, we need to consider the Karush-Kuhn-Tucker (KKT) conditions for optimality of the optimization problem implied by (1). It is easy to verify that the normal equations (2) can be replaced by the following KKT-based condition for l1-norm penalty: (3) | C( ^ ())j| < ^ ()j = 0 ^ (4) ()j = 0 | C( ^ ())j| = these conditions hold for any differentiable loss and tell us that at each point on the path we have a set A of non-0 coefficients which corresponds to the variables whose current "gen- eralized correlation" | C( ^ ())j| is maximal and equal to . All variables with smaller generalized correlation have 0 coefficient at the optimal penalized solution for this . Note that the l1-norm penalty is twice differentiable everywhere except at 0. So if we carefully manage the set of non-0 coefficients according to these KKT conditions, we can still apply our algorithm in the lower-dimensional subspace spanned by non-0 coefficients only. Thus we get Algorithm 2, which employs the Newton approach of Algorithm 1 for twice differentiable penalty, limited to the sub-space of "active" coefficients denoted by A. It adds to Algorithm 1 updates for the "add variable to active set" and "remove variable from active set" events, when a variable becomes "highly correlated" as defined in (4) and when a coefficient hits 0 , respectively. 2 Algorithm 2 Approximate incremental quadratic algorithm for regularized optimization with lasso penalty 1. Set ( ) 0 = ^ (0), set t = 0, set A = {j : ^ (0)j = 0}. 2. While (t < max) (a) t+1 = t + (b) -1 ( ) t+1 = ( ) t - 2C(( ) t )A C(( ) t )A + t+1sgn(( ) t )A (c) A = A {j / A : C(( ) t+1)j > t+1} (d) A = A - {j A : |( ) | < } t+1,j (e) t = t + 1 2.2 Computational considerations For a fixed 0 and max, Algorithms 1 and 2 take O(1/ ) steps. At each iteration they need to calculate the Hessians of both the loss and the penalty at a typical computational cost of O(n p2); invert the resulting p p matrix at a cost of O(p3); and perform the gradient calculation and multiplication, which are o(n p2) and so do not affect the complexity calculation. Since we implicitly assume throughout that n p, we get overall complexity of O(n p2/ ). The choice of represents a tradeoff between computational complexity and accuracy (in section 4 we present theoretical results on the relationship between and the accuracy of the path approximation we get). In practice, our algorithm is practical for problems with up to several hundred predictors and several thousand observations. See the example in section 3. It is interesting to compare this calculation to the obvious alternative, which is to solve O(1/ ) regularized problems (1) separately, using a Newton-Raphson approach, resulting in the same complexity (assuming the number of Newton-Raphson iterations for finding each solution is bounded). There are several reasons why our approach is preferable: The number of iterations until convergence of Newton-Raphson may be large even if it does converge. Our algorithm guarantees we stay very close to the optimal solution path with a single Newton step at each new value of . Empirically we observe that in some cases our algorithm is able to follow the path while direct solution for some values of fails to converge. We assume this is related to various numeric properties of the specific problems being solved. For the interesting case of l1-norm penalty and a "curved" loss function (like logis- tic log-likelihood), there is no direct Newton-Raphson algorithm. Re-formulating the problem into differentiable form requires doubling the dimensionality. Using our Algorithm 2, we can still utilize the same Newton method, with significant computational savings when many coefficients are 0 and we work in a lower- dimensional subspace. 2When a coefficient hits 0 it not only hits a non-differentiability point in the penalty, it also ceases to be maximally correlated as defined in (4). A detailed proof of this fact and the rest of the "accounting" approach can be found in [9] On the flip side, our results in section 4 below indicate that to guarantee successful tracking we require to be small, meaning the number of steps we do in the algorithm may be significantly larger than the number of distinct problems we would typically solve to select using a non-path approach. 2.3 Connection to path following methods from numerical analysis There is extensive literature on path-following methods for solution paths of general para- metric problems. A good survey is given in [1]. In this context, our method can be described as a "predictor-corrector" method with a redundant first order predictor step. That is, the corrector step starts from the previous approximate solution. These methods are recognized as attractive options when the functions defining the path (in our case, the combination of loss and penalty) are "smooth" and "far from linear". These conditions for efficacy of our approach are reflected in the regularity conditions for the closeness result in Section 4. 3 Example: l2- and l1-penalized logistic regression Regularized logistic regression has been successfully used as a classification and proba- bility estimation approach [11, 12]. We first illustrate applying our quadratic method to this regularized problem using a small subset of the "spam" data-set, available from the UCI repository (http://www.ics.uci.edu/~mlearn/MLRepository.html) which allows us to present some detailed diagnostics. Next, we apply it to the full "spam" data-set, to demonstrate its time complexity on bigger problems. We first choose five variables and 300 observations and track the solution paths to two regularized logistic regression problems with the l2-norm and the l1-norm penalties: ^ (5) () = arg min log(1 + exp{-yi xi}) + 22 ^ (6) () = arg min log(1 + exp{-yi xi}) + 1 Figure 1 shows the solution paths ( )(t) generated by running Algorithms 1 and 2 on this data using = 0.02 and starting at = 0, i.e. from the non-regularized logistic regression solution. The interesting graphs for our purpose are the ones on the right. They represent the "optimality gap": C(( ) e t ) t = + t J(( ) t ) where the division is done componentwise (and so the five curves in each plot correspond to the five variables we are using). Note that the optimal solution ^ (t ) is uniquely defined by the fact that (2) holds and therefore the "optimality gap" is equal to zero componentwise at ^ (t ). By convexity and regularity of the loss and the penalty, there is a correspondence between small values of e and small distance ( )(t) - ^ (t ) . In our example we observe that the components of e seem to be bounded in a small region around 0 for both paths (note the small scale of the y axis in both plots -- the maximal error is under 10-3). We conclude that on this simple example our method tracks the optimal solution paths well, both for the l1- and l2-regularized problems. The plots on the left show the actual coefficient paths -- the curve in R5 is shown as five coefficient traces in R, each corresponding to one variable, with the non-regularized solution (identical for both problems) on the extreme left. Next, we run our algorithm on the full "spam" data-set, containing p = 57 predic- tors and n = 4601 observations. For both the l1- and l2-penalized paths we used -4 x 10 2.5 2 4 1.5 1 J + (/) 2 0.5 C / 0 0 -0.5 -2 0 10 20 30 40 0 10 20 30 40 -4 x 10 2.5 2 4 1.5 1 J + (/) 2 0.5 C / 0 0 -0.5 -2 0 10 20 30 40 0 10 20 30 40 Figure 1: Solution paths (left) and optimality criterion (right) for l1 penalized logistic re- gression (top) and l2 penalized logistic regression (bottom). These result from running Algorithms 2 and 1, respectively, using = 0.02 and starting from the non-regularized logistic regression solution (i.e. = 0) 0 = 0, max = 50, = 0.02, and the whole path was generated in under 5 minutes using a Matlab implementation on an IBM T-30 Laptop. Like in the small scale example, the "optimality criterion" was uniformly small throughout the two paths, with none of its 57 components exceeding 10-3 at any point. 4 Theoretical closeness result In this section we prove that our algorithm can track the path of true solutions to (1). We show that under regularity conditions on the loss and penalty (which hold for all the candidates we have examined), if we run Algorithm 1 with a specific step size , then we remain within O( 2) of the true path of optimal regularized solutions. Theorem 1 Assume 0 > 0, then for small enough and under regularity conditions on the derivatives of C and J , 0 < c < max - 0 , ( )(c/ ) - ^ (0 + c) = O( 2) So there is a uniform bound O( 2) on the error which does not depend on c. Proof We give the details of the proof in Appendix A of [7]. Here we give a brief review of the main steps. Similar to section 3 we define the "optimality gap": C(( ) (7) ( t ) )j + t = etj J(( ) t ) Also define a "regularity constant" M , which depends on 0 and the first, second and third derivatives of the loss and penalty. The proof is presented as a succession of lemmas: Lemma 2 Let u1 = M p 2, ut = M (ut-1 + p )2, then: et 2 ut This lemma gives a recursive expression bounding the error in the optimality gap (7) as the algorithm proceeds. The proof is based on separate Taylor expansions of the numerator and denominator of the ratio C J in the optimality gap and some tedious algebra. 1-4 p M Lemma 3 If p M 1/4 then u 1 t - p - = O( 2) , t 2M 2M This lemma shows that the recursive bound translates to a uniform O( 2) bound, if is small enough. The proof consists of analytically finding the fixed point of the increasing series ut. Lemma 4 Under regularity conditions on the penalty and loss functions in the neighbor- hood of the solutions to (1), the O( 2) uniform bound of lemma 3 translates to an O( 2) uniform bound on ( )(c/ ) - ^ (0 + c) Finally, this lemma translates the optimality gap bound to an actual closeness result. This is proven via a Lipschitz argument. 4.1 Required regularity conditions Regularity in the loss and the penalty is required in the definition of the regularity constant M and in the translation of the O( 2) bound on the "optimality gap" into one on the distance from the path in lemma 4. The exact derivation of the regularity conditions is highly tech- nical and lengthy. They require us to bound the norm of third derivative "hyper-matrices" for the loss and the penalty as well as the norms of various functions of the gradients and Hessians of both (the boundedness is required only in the neighborhood of the optimal path where our approximate path can venture, obviously). We also need to have 0 > 0 and max < . Refer to Appendix A of [7] for details. Assuming that 0 > 0 and max < these conditions hold for every interesting example we have encountered, including: Ridge regression and the lasso (that is, l2- and l1- regularized squared error loss). l1- and l2-penalized logistic regression. Also Poisson regression and other expo- nential family models. l1- and l2-penalized exponential loss. Note that in our practical examples above we have started from 0 = 0 and our method still worked well. We observe in figure 1 that the tracking algorithm indeed suffers the biggest inaccuracy for the small values of , but manages to "self correct" as increases.

We consider the situation in semi-supervised learning, where the "label sampling" mechanism stochastically depends on the true response (as well as potentially on the features). We suggest a method of moments for estimating this stochastic dependence using the unlabeled data. This is potentially useful for two distinct purposes: a. As an input to a super- vised learning procedure which can be used to "de-bias" its results using labeled data only and b. As a potentially interesting learning task in it- self. We present several examples to illustrate the practical usefulness of our method. 1 Introduction In semi-supervised learning, we assume we have a sample (xi, yi, si)n i=1, of i.i.d. draws from a joint distribution on (X, Y, S), where:1 xi Rp are p-vectors of features. yi is a label, or response (yi R for regression, yi {0, 1} for 2-class classifica- tion). si {0, 1} is a "labeling indicator", that is yi is observed if and only if si = 1, while xi is observed for all i. In this paper we consider the interesting case of semi-supervised learning, where the prob- ability of observing the response depends on the data through the true response, as well as 1Our notation here differs somewhat from many semi-supervised learning papers, where the un- labeled part of the sample is separated from the labeled part and sometimes called "test set". potentially through the features. Our goal is to model this unknown dependence: l(x, y) = P r(S = 1|x, y) (1) Note that the dependence on y (which is unobserved when S = 0) prevents us from using standard supervised modeling approaches to learn l. We show here that we can use the whole data-set (labeled+unlabeled data) to obtain estimates of this probability distribution within a parametric family of distributions, without needing to "impute" the unobserved responses.2 We believe this setup is of significant practical interest. Here are a couple of examples of realistic situations: 1. The problem of learning from positive examples and unlabeled data is of significant interest in document topic learning [4, 6, 8]. Consider a generalization of that problem, where we observe a sample of positive and negative examples and unlabeled data, but we believe that the positive and negative labels are supplied with different probabilities (in the document learning example, positive examples are typically more likely to be labeled than negative ones, which are much more abundant). These probabilities may also not be uniform within each class, and depend on the features as well. Our methods allow us to infer these labeling probabilities by utilizing the unlabeled data. 2. Consider a satisfaction survey, where clients of a company are requested to report their level of satisfaction, but they can choose whether or not they do so. It is reasonable to assume that their willingness to report their satisfaction depends on their actual satisfaction level. Using our methods, we can infer the dependence of the reporting probability on the actual satisfaction by utilizing the unlabeled data, i.e., the customers who declined to respond. Being able to infer the labeling mechanism is important for two distinct reasons. First, it may be useful for "de-biasing" the results of supervised learning, which uses only the labeled examples. The generic approach for achieving this is to use "inverse sampling" weights (i.e. weigh labeled examples by 1/l(x, y)). The us of this for maximum likeli- hood estimation is well established in the literature as a method for correcting sampling bias (of which semi-supervised learning is an example) [10]. We can also use the learned mechanism to post-adjust the probabilities from a probability estimation methods such as logistic regression to attain "unbiasedness" and consistency [11]. Second, understanding the labeling mechanism may be an interesting and useful learning task in itself. Consider, for example, the "satisfaction survey" scenario described above. Understanding the way in which satisfaction affects the customers' willingness to respond to the survey can be used to get a better picture of overall satisfaction and to design better future surveys, regardless of any supervised learning task which models the actual satisfaction. Our approach is described in section 2, and is based on a method of moments. Observe that for every function of the features g(x), we can get an unbiased estimate of its mean n as 1 g(x n i=1 i). We show that if we know the underlying label sampling mechanism l(x, y) we can get a different unbiased estimate of Eg(x), which uses only the labeled examples, weighted by 1/l(x, y). We suggest inferring the unknown function l(x, y) by requiring that we get identical estimates of Eg(x) using both approaches. We illustrate our method's implementation on the California Housing data-set in section 3. In section 4 we review related work in the machine learning and statistics literature, and we conclude with a discussion in section 5. 2The importance of this is that we are required to hypothesize and fit a conditional probability model for l(x, y) only, as opposed to the full probability model for (S, X, Y ) required for, say, EM.

The success of prediction models for business purposes should not be measured by their accuracy only. Their evaluation should also take into account the higher importance of precise prediction for "valuable" customers. We illustrate this idea through the example of churn modelling in telecommunications, where it is obviously much more important to identify potential churn among valuable customers. We discuss, both theoretically and empirically, the optimal use of "customer value" data in the model training, model evaluation and scoring stages. Our main conclusion is that a nontrivial approach of using "decayed" value-weights for training is usually preferable to the two obvious approaches of either using nondecayed customer values as weights or ignoring them.

Margin maximizing properties play an important role in the analysis of classi£- cation models, such as boosting and support vector machines. Margin maximiza- tion is theoretically interesting because it facilitates generalization error analysis, and practically interesting because it presents a clear geometric interpretation of the models being built. We formulate and prove a suf£cient condition for the solutions of regularized loss functions to converge to margin maximizing separa- tors, as the regularization vanishes. This condition covers the hinge loss of SVM, the exponential loss of AdaBoost and logistic regression loss. We also generalize it to multi-class classi£cation problems, and present margin maximizing multi- class versions of logistic regression and support vector machines.

The standard 2-norm SVM is known for its good performance in two- In this paper, we consider the 1-norm SVM. We class classi£cation. argue that the 1-norm SVM may have some advantage over the standard 2-norm SVM, especially when there are redundant noise features. We also propose an ef£cient algorithm that computes the whole solution path of the 1-norm SVM, hence facilitates adaptive selection of the tuning parameter for the 1-norm SVM.

We present and discuss the important business problem of estimating the effect of retention efforts on the Lifetime Value of a customer in the Telecommunications industry. We discuss the components of this problem, in particular customer value and length of service (or tenure) modeling, and present a novel segment-based approach, motivated by the segment-level view marketing analysts usually employ. We then describe how we build on this approach to estimate the effects of retention on Lifetime Value. Our solution has been successfully implemented in Amdocs' Business Insight (BI) platform, and we illustrate its usefulness in real-world scenarios.

Several authors have suggested viewing boosting as a gradient descent search for a good fit in function space. We apply gradient-based boosting methodology to the unsupervised learning problem of density estimation. We show convergence properties of the algorithm and prove that a strength of weak learnability prop- erty applies to this problem as well. We illustrate the potential of this approach through experiments with boosting Bayesian networks to learn density models.

We consider prediction-model evaluation in the context of marketing-campaign planning. In order to evaluate and compare models with specific campaign objectives in mind, we need to concentrate our attention on the appropriate evaluation-criteria. These should portray the model's ability to score accurately and to identify the relevant target population. In this paper we discuss some applicable model-evaluation and selection criteria, their relevance for campaign planning, their robustness under changing population distributions, and their employment when constructing confidence intervals. We illustrate our results with a case study based on our experience from several projects.

Many fraud analysis systems have at their heart a rule-based engine for generating alerts about suspicious behaviors.The rules in the system are usually based on expert knowledge.Automatic rule discovery aims at using past examples of fraudulent and legitimate usage to find new patterns and rules to help distinguish between the two.Some aspects of the problem of finding rules suitable for fraud analysis make this problem unique.Among them are the following: the need to find rules combining both the properties of the customer (e.g., credit rating) and properties of the specific "behavior" which indicates fraud (e.g., number of international calls in one day); and the need for a new definition of accuracy: We need to find rules which do not necessarily classify correctly each individual "usage sample" as either fraudulent or not, but ensure the identification, with a minimum of wasted cost and effort, of most of the fraud "cases" (i.e., defrauded customers).These aspects require a special-purpose rule discovery system.We present as an example a two-stage system based on adaptation of the C4.5 rule generator, with an additional rule selection mechanism.Our experimental results indicate that this route is very promising.