Backdoor attacks are an important type of adversarial threat against deep neural network classifiers, wherein test samples from one or more source classes will be (mis)classified to the attacker’s target class when a backdoor pattern is embedded. In this paper, we focus on the post-training backdoor defense scenario commonly considered in the literature, where the defender aims to detect whether a trained classifier was backdoor-attacked without any access to the training set. Many post-training detectors are designed to detect attacks that use either one or a few specific backdoor embedding functions (e.g., patch-replacement or additive attacks). These detectors may fail when the backdoor embedding function used by the attacker (unknown to the defender) is different from the backdoor embedding function assumed by the defender. In contrast, we propose a post-training defense that detects backdoor attacks with arbitrary types of backdoor embeddings, without making any assumptions about the backdoor embedding type. Our detector leverages the influence of the backdoor attack, independent of the backdoor embedding mechanism, on the landscape of the classifier’s outputs prior to the softmax layer. For each class, a maximum margin statistic is estimated. Detection inference is then performed by applying an unsupervised anomaly detector to these statistics. Thus, our detector does not need any legitimate clean samples, and can efficiently detect backdoor attacks with arbitrary numbers of source classes. These advantages over several state-of-the-art methods are demonstrated on four datasets, for three different types of backdoor patterns, and for a variety of attack configurations. Finally, we propose a novel, general approach for backdoor mitigation once a detection is made. The mitigation approach was the runner-up at the first IEEE Trojan Removal Competition. The code is online available.

Data Poisoning (DP) is an effective attack that causes trained classifiers to misclassify their inputs. DP attacks significantly degrade a classifier's accuracy by covertly injecting attack samples into the training set. Broadly applicable to different classifier structures, without strong assumptions about the attacker, anunsupervisedBayesian Information Criterion (BIC)-based mixture model defense against “error generic” DP attacks is herein proposed that: 1) addresses the most challengingembeddedDP scenario wherein, if DP is present, the poisoned samples are ana prioriunknown subset of the training set, and with no clean validation set available; 2) applies a mixture model both to well-fit potentially multi-modal class distributions and to capture poisoned samples within a small subset of the mixture components; 3) jointly identifies poisoned components and samples by minimizing the BIC cost defined over the whole training set, with the identified poisoned data removed prior to classifier training. Our experimental results, for various classifier structures and benchmark datasets, demonstrate the effectiveness of our defense under strong DP attacks, as well as its superiority over other DP defenses.

A backdoor or Trojan attack is an important type of data poisoning attack against deep neural network (DNN) classifiers, wherein the training dataset is poisoned with a small number of samples that each possess the backdoor pattern (usually a pattern that is either imperceptible or innocuous) and which are mislabeled to the attacker’s target class. When trained on a backdoor-poisoned dataset, a DNN behaves normally on most benign test samples but makes incorrect predictions to the target class when the test sample has the backdoor pattern incorporated (i.e., contains a backdoor trigger). Here we focus on image classification tasks and show that supervised training may build stronger association between the backdoor pattern and the associated target class than that between normal features and the true class of origin. By contrast, self-supervised representation learning ignores the labels of samples and learns a feature embedding based on images’ semantic content. Using a feature embedding found by self-supervised representation learning, a data cleansing method, which combines sample filtering and relabeling, is developed. Experiments on CIFAR-10 benchmark datasets show that our method achieves state-of-the-art performance in mitigating backdoor attacks.

Backdoor (Trojan) attacks are emerging threats against deep neural networks (DNN). A DNN being attacked will predict to an attacker-desired target class whenever a test sample from any source class is embedded with a backdoor pattern, while correctly classifying clean (attack-free) test samples. Existing backdoor defenses have shown success in detecting whether a DNN is attacked and in reverse-engineering the backdoor pattern in a "post-training" scenario: the defender has access to the DNN to be inspected and a small, clean dataset collected independently, but has no access to the (possibly poisoned) training set of the DNN. However, these defenses neither catch culprits in the act of triggering the backdoor mapping, nor mitigate the backdoor attack at test-time. In this paper, we propose an "in-flight" unsupervised defense against backdoor attacks on image classification that 1) detects use of a backdoor trigger at test-time; and 2) infers the class of origin (source class) for a detected trigger example. The effectiveness of our defense is demonstrated experimentally for a wide variety of DNN architectures, datasets, and backdoor attack configurations.

Backdoor attacks (BA) are an emerging threat to deep neural network classifiers. A classifier being attacked will predict to the attacker’s target class when a test sample from a source class is embedded with the backdoor pattern (BP). Recently, the first BA against point cloud (PC) classifiers was proposed, creating new threats to many important applications including autonomous driving. Such PC BAs are not detectable by existing BA defenses due to their special BP embedding mechanism. In this paper, we propose a reverse-engineering defense that infers whether a PC classifier is backdoor attacked, without access to its training set or to any clean classifiers for reference. The effectiveness of our defense is demonstrated on the benchmark ModeNet40 dataset for PCs.

With wide deployment of deep neural network (DNN) classifiers, there is great potential for harm from adversarial learning attacks. Recently, a special type of data poisoning (DP) attack, known as a backdoor (or Trojan), was proposed. These attacks do not seek to degrade classification accuracy, but rather to have the classifier learn to classify to a target class$t^{\ast }$whenever the backdoor pattern is present in a test example originally from a source class$s^{\ast }$. Launching backdoor attacks does not require knowledge of the classifier or its training process—only the ability to poison the training set with exemplars containing a backdoor pattern (labeled with the target class). Defenses against backdoors can be deployed before/during training, post-training, or at test time. Here, we address post-training detection in DNN image classifiers, seldom considered in existing works, whereinthe defender does not have access to the poisoned training set, but only to the trained classifier itself, as well as to clean (unpoisoned) examples from the classification domain. This scenario is of great interest because e.g., a classifier may be the basis of a phone app that will be shared with many users. Detection may thus reveal a widespread attack. We propose a purely unsupervised anomaly detection (AD) defense against imperceptible backdoor attacks that: 1) detects whether the trained DNN has been backdoor-attacked; 2) infers the source and target classes in a detected attack; 3) estimates the backdoor pattern itself. Our AD approach involves learning (via suitable cost function minimization) the minimum size/norm perturbation (putative backdoor) required to induce the classifier to misclassify (most) examples from class$s$to class$t$, for all$(s,t)$pairs. Our hypothesis is that nonattacked pairs require large perturbations, while the attacked pair$(s^{\ast }, t^{\ast })$requires much smaller ones. This is convincingly borne out experimentally. We identify a variety of plausible cost functions and devise a novel, robust hypothesis testing approach to perform detection inference. We test our approach, in comparison with the state-of-the-art methods, for several backdoor patterns, attack settings and mechanisms, and data sets and demonstrate its favorability. Our defense essentially requires setting a single hyperparameter (the detection threshold), which can e.g., be chosen to fix the system’s false positive rate.

Backdoor attacks (BAs) are an emerging form of adversarial attack typically against deep neural network image classifiers. The attacker aims to have the classifier learn to classify to a target class when test images from one or more source classes contain a backdoor pattern, while maintaining high accuracy on all clean test images. Reverse-Engineering-based Defenses (REDs) against BAs do not require access to the training set but only to an independent clean dataset. Unfortunately, most existing REDs rely on an unrealistic assumption that all classes except the target class are source classes of the attack. REDs that do not rely on this assumption often require a large set of clean images and heavy computation. In this paper, we propose a Lagrangian-based RED (L-RED) that does not require knowledge of the number of source classes (or whether an attack is present). Our defense requires very few clean images to effectively detect BAs and is computationally efficient. Notably, we detect 56 out of 60 BAs using only two clean images per class in our experiments on CIFAR-10.

Vulnerability of 3D point cloud (PC) classifiers has become a grave concern due to the popularity of 3D sensors in safety-critical applications. Existing adversarial attacks against 3D PC classifiers are all test-time evasion (TTE) attacks that aim to induce test-time misclassifications using knowledge of the classifier. But since the victim classifier is usually not accessible to the attacker, the threat is largely diminished in practice, as PC TTEs typically have poor transferability. Here, we propose the first backdoor attack (BA) against PC classifiers. Originally proposed for images, BAs poison the victim classifier’s training set so that the classifier learns to decide to the attacker’s target class whenever the attacker’s backdoor pattern is present in a given input sample. Significantly, BAs do not require knowledge of the victim classifier. Different from image BAs, we propose to insert a cluster of points into a PC as a robust backdoor pattern customized for 3D PCs. Such clusters are also consistent with a physical attack (i.e., with a captured object in a scene). We optimize the cluster’s location using an independently trained surrogate classifier and choose the cluster’s local geometry to evade possible PC preprocessing and PC anomaly detectors (ADs). Experimentally, our BA achieves a uniformly high success rate (≥ 87%) and shows evasiveness against state-of-the-art PC ADs. Code is available at https://github.com/zhenxianglance/PCBA.

Backdoor data poisoning attacks add mislabeled examples to the training set, with an embedded backdoor pattern, so that the classifier learns to classify to a target class whenever the backdoor pattern is present in a test sample. Here, we address posttraining detection of scene-plausible perceptible backdoors, a type of backdoor attack that can be relatively easily fashioned, particularly against DNN image classifiers. A post-training defender does not have access to the potentially poisoned training set, only to the trained classifier, as well as some unpoisoned examples that need not be training samples. Without the poisoned training set, the only information about a backdoor pattern is encoded in the DNN's trained weights. This detection scenario is of great import considering legacy and proprietary systems, cell phone apps, as well as training outsourcing, where the user of the classifier will not have access to the entire training set. We identify two important properties of scene-plausible perceptible backdoor patterns, spatial invariance and robustness, based on which we propose a novel detector using the maximum achievable misclassification fraction (MAMF) statistic. We detect whether the trained DNN has been backdoor-attacked and infer the source and target classes. Our detector outperforms existing detectors and, coupled with an imperceptible backdoor detector, helps achieve posttraining detection of most evasive backdoors of interest.

Deep learning models have consistently outperformed traditional machine learning models in various classification tasks, including image classification. As such, they have become increasingly prevalent in many real world applications including those where security is of great concern. Such popularity, however, may attract attackers to exploit the vulnerabilities of the deployed deep learning models and launch attacks against security-sensitive applications. In this paper, we focus on a specific type of data poisoning attack, which we refer to as a \em backdoor injection attack. The main goal of the adversary performing such attack is to generate and inject a backdoor into a deep learning model that can be triggered to recognize certain embedded patterns with a target label of the attacker's choice. Additionally, a backdoor injection attack should occur in a stealthy manner, without undermining the efficacy of the victim model. Specifically, we propose two approaches for generating a backdoor that is hardly perceptible yet effective in poisoning the model. We consider two attack settings, with backdoor injection carried out either before model training or during model updating. We carry out extensive experimental evaluations under various assumptions on the adversary model, and demonstrate that such attacks can be effective and achieve a high attack success rate (above 90%) at a small cost of model accuracy loss with a small injection rate, even under the weakest assumption wherein the adversary has no knowledge either of the original training data or the classifier model.

Recently, a special type of data poisoning (DP) attack against deep neural network (DNN) classifiers, known as a backdoor, was proposed. These attacks do not seek to degrade classification accuracy, but rather to have the classifier learn to classify to a target class whenever the backdoor pattern is present in a test example. Here, we address the challenging post-training detection of backdoor attacks in DNN image classifiers, wherein the defender does not have access to the poisoned training set, but only to the trained classifier itself, as well as to clean (unpoisoned) examples from the classification domain. We propose a defense against imperceptible backdoor attacks based on perturbation optimization and novel, robust detection inference. Our method detects whether the trained DNN has been backdoor-attacked and infers the source and target classes involved in an attack. It outperforms alternative defenses for several backdoor patterns, data sets, and attack settings.

Computing systems have been facing severe technology challenges in recent years with regard to power consumption, circuit reliability, and high performance. For many years, the issues of power consumption and performance have been addressed with the use of technology scaling.However, as Dennard’s scaling tends toward an end, it has become difficult to further improve the performance under the same power constraints. In addition to power, reliability also becomes a critical issue when the feature size of the complementary metal-oxide–semiconductor (CMOS) technology is reduced below 7 nm. Thus, ensuring the complete accuracy of the signal has become increasingly challenging in recent years.

With wide deployment of machine learning (ML)-based systems for a variety of applications including medical, military, automotive, genomic, multimedia, and social networking, there is great potential for damage from adversarial learning (AL) attacks. In this article, we provide a contemporary survey of AL, focused particularly on defenses against attacks on deep neural network classifiers. After introducing relevant terminology and the goals and range of possible knowledge of both attackers and defenders, we survey recent work on test-time evasion (TTE), data poisoning (DP), backdoor DP, and reverse engineering (RE) attacks and particularly defenses against the same. In so doing, we distinguish robust classification from anomaly detection (AD), unsupervised from supervised, and statistical hypothesis-based defenses from ones that do not have an explicit null (no attack) hypothesis. We also consider several scenarios for detecting backdoors. We provide a technical assessment for reviewed works, including identifying any issues/limitations, required hyperparameters, needed computational complexity, as well as the performance measures evaluated and the obtained quality. We then delve deeper, providing novel insights that challenge conventional AL wisdom and that target unresolved issues, including: robust classification versus AD as a defense strategy; the belief that attack success increases with attack strength, which ignores susceptibility to AD; small perturbations for TTE attacks: a fallacy or a requirement; validity of the universal assumption that a TTE attacker knows the ground-truth class for the example to be attacked; black, gray, or white-box attacks as the standard for defense evaluation; and susceptibility of query-based RE to an AD defense. We also discuss attacks on the privacy of training data. We then present benchmark comparisons of several defenses against TTE, RE, and backdoor DP attacks on images. The article concludes with a discussion of continuing research directions, including the supreme challenge of detecting attacks whose goal is not to alter classification decisions, but rather simply to embed, without detection, “fake news” or other false content.

Machine labeling of image content as private or public is a notoriously difficult problem, with the usual image processing challenges compounded by the highly personal, subjective, and contextual nature of access control decision making. In general, a user's privacy expectation for a given image is consequential to specific contents therein and the presence of sensitive content somewhere in the image is sufficient to warrant a private label. In this work, we extend the problem of determining a single privacy label for a given image to jointly inferring a privacy label and detecting the specific areas of sensitive content within a privately labeled image. We propose a stochastic spatial attribution model which exploits sophisticated (deep neural net derived) image features over randomly selected image patches, as well as image saliency quantification. We validate our detected private regions through extensive user study experiments. This effort to achieve spatial attribution of private image content helps to lay a foundation for warning mechanisms which may serve to aid both social media sites and their users.

For lossy image compression systems, we develop an algorithm, iterative refinement, to improve the decoder's reconstruction compared to standard decoding techniques. Specifically, we propose a recurrent neural network approach for nonlinear, iterative decoding. Our decoder, which works with any encoder, employs self-connected memory units that make use of causal and non-causal spatial context information to progressively reduce reconstruction error over a fixed number of steps. We experiment with variants of our estimator and find that iterative refinement consistently creates lower distortion images of higher perceptual quality compared to other approaches. Specifically, on the Kodak Lossless True Color Image Suite, we observe as much as a 0.871 decibel (dB) gain over JPEG, a 1.095 dB gain over JPEG 2000, and a 0.971 dB gain over a competitive neural model.

This paper addresses detection of a reverse engineering (RE) attack targeting a deep neural network (DNN) image classifier; by querying, RE's aim is to discover the classifier's decision rule. RE can enable test-time evasion attacks, which require knowledge of the classifier. Recently, we proposed a quite effective approach (ADA) to detect test-time evasion attacks. In this paper, we extend ADA to detect RE attacks (ADA-RE). We demonstrate our method is successful in detecting "stealthy" RE attacks before they learn enough to launch effective test-time evasion attacks.

A significant threat to the recent, wide deployment of machine learning-based systems, including deep neural networks (DNNs), is adversarial learning attacks. The main focus here is on evasion attacks against DNN-based classifiers at test time. While much work has focused on devising attacks that make small perturbations to a test pattern (e.g., an image) that induce a change in the classifier's decision, until recently there has been a relative paucity of work defending against such attacks. Some works robustify the classifier to make correct decisions on perturbed patterns. This is an important objective for some applications and for natural adversary scenarios. However, we analyze the possible digital evasion attack mechanisms and show that in some important cases, when the pattern (image) has been attacked, correctly classifying it has no utility---when the image to be attacked is (even arbitrarily) selected from the attacker's cache and when the sole recipient of the classifier's decision is the attacker. Moreover, in some application domains and scenarios, it is highly actionable to detect the attack irrespective of correctly classifying in the face of it (with classification still performed if no attack is detected). We hypothesize that adversarial perturbations are machine detectable even if they are small. We propose a purely unsupervised anomaly detector (AD) that, unlike previous works, (1) models the joint density of a deep layer using highly suitable null hypothesis density models (matched in particular to the nonnegative support for rectified linear unit (ReLU) layers); (2) exploits multiple DNN layers; and (3) leverages a source and destination class concept, source class uncertainty, the class confusion matrix, and DNN weight information in constructing a novel decision statistic grounded in the Kullback-Leibler divergence. Tested on MNIST and CIFAR image databases under three prominent attack strategies, our approach outperforms previous detection methods, achieving strong receiver operating characteristic area under the curve detection accuracy on two attacks and better accuracy than recently reported for a variety of methods on the strongest (CW) attack. We also evaluate a fully white box attack on our system and demonstrate that our method can be leveraged to strong effect in detecting reverse engineering attacks. Finally, we evaluate other important performance measures such as classification accuracy versus true detection rate and multiple measures versus attack strength.

In an effort to support users' decision making process in regards to shared and co-managed online images, in this paper we present a novel model to early detect images which may be subject to possible conflicting access control decisions. We present a group-based stochastic model able to identify potential privacy conflicts among multiple stakeholders of an image. We discuss experiments on a dataset of over 3000 online images, and compare our results with several baselines. Our approach outperforms all baselines, even the strong ones based on a Convolutional Neural Network architecture.

Estimation of a generating partition is critical for symbolization of measurements from discrete-time dynamical systems, where a sequence of symbols from a (finite-cardinality) alphabet may uniquely specify the underlying time series. Such symbolization is useful for computing measures (e.g., Kolmogorov-Sinai entropy) to identify or characterize the (possibly unknown) dynamical system. It is also useful for time series classification and anomaly detection. The seminal work of Hirata, Judd, and Kilminster ( 2004 ) derives a novel objective function, akin to a clustering objective, that measures the discrepancy between a set of reconstruction values and the points from the time series. They cast estimation of a generating partition via the minimization of their objective function. Unfortunately, their proposed algorithm is nonconvergent, with no guarantee of finding even locally optimal solutions with respect to their objective. The difficulty is a heuristic nearest neighbor symbol assignment step. Alternatively, we develop a novel, locally optimal algorithm for their objective. We apply iterative nearest-neighbor symbol assignments with guaranteed discrepancy descent, by which joint, locally optimal symbolization of the entire time series is achieved. While most previous approaches frame generating partition estimation as a state-space partitioning problem, we recognize that minimizing the Hirata et al. ( 2004 ) objective function does not induce an explicit partitioning of the state space, but rather the space consisting of the entire time series (effectively, clustering in a (countably) infinite-dimensional space). Our approach also amounts to a novel type of sliding block lossy source coding. Improvement, with respect to several measures, is demonstrated over popular methods for symbolizing chaotic maps. We also apply our approach to time-series anomaly detection, considering both chaotic maps and failure application in a polycrystalline alloy material.

While non-negative blind source separation (nBSS) has found many successful applications in science and engineering, model order selection, determining the number of sources, remains a critical yet unresolved problem. Various model order selection methods have been proposed and applied to real-world data sets but with limited success, with both order over- and under-estimation reported. By studying existing schemes, we have found that the unsatisfactory results are mainly due to invalid assumptions, model oversimplification, subjective thresholding, and/or to assumptions made solely for mathematical convenience. Building on our earlier work that reformulated model order selection for nBSS with more realistic assumptions and models, we report a newly and formally revised model order selection criterion rooted in the minimum description length (MDL) principle. Adopting widely invoked assumptions for achieving a unique nBSS solution, we consider the mixing matrix as consisting of deterministic unknowns, with the source signals following a multivariate Dirichlet distribution. We derive a computationally efficient, stochastic algorithm to obtain approximate maximum-likelihood estimates of model parameters and apply Monte Carlo integration to determine the description length. Our modeling and estimation strategy exploits the characteristic geometry of the data simplex in nBSS. We validate our nBSS-MDL criterion through extensive simulation studies and on four real-world data sets, demonstrating its strong performance and general applicability to nBSS. The proposed nBSS-MDL criterion consistently detects the true number of sources, in all of our case studies.

In a variety of Network-based Intrusion Detection System (NIDS) applications, one desires to detect groups of unknown attack (e.g., botnet) packet-flows, with a group potentially manifesting its a typicality (relative to a known reference “normal”/null model) on a low-dimensional subset of the full measured set of features used by the IDS. What makes this anomaly detection problem quite challenging is that it is a priori unknown which (possibly sparse) subset of features jointly characterizes a particular application, especially one that has not been seen before, which thus represents an unknown behavioral class (zero-day threat). Moreover, nowadays botnets have become evasive, evolving their behavior to avoid signature-based IDSes. In this work, we apply a novel active learning (AL) framework for botnet detection, facilitating detection of unknown botnets (assuming no ground truth examples of same). We propose a new anomaly-based feature set that captures the informative features and exploits the sequence of packet directions in a given flow. Experiments on real world network traffic data, including several common Zeus botnet instances, demonstrate the advantage of our proposed features and AL system.

We address machine prediction of an individual's label (private or public) for a given image. This problem is difficult due to user subjectivity and inadequate labeled examples to train individual, personalized models. It is also time and space consuming to train a classifier for each user. We propose a Group-Based Personalized Model for image privacy classification in online social media sites, which learns a set of archetypical privacy models (groups), and associates a given user with one of these groups. Our system can be used to provide accurate ``early warnings'' with respect to a user's privacy awareness level.

Many classification tasks require both labeling objects and determining label associations for parts of each object. Example applications include labeling segments of images or determining relevant parts of a text document when the training labels are available only at the image or document level. This task is usually referred to as multi-instance (MI) learning, where the learner typically receives a collection of labeled (or sometimes unlabeled) bags, each containing several segments (instances). We propose a semisupervised MI learning method for multilabel classification. Most MI learning methods treat instances in each bag as independent and identically distributed samples. However, in many practical applications, instances are related to each other and should not be considered independent. Our model discovers a latent low-dimensional space that captures structure within each bag. Further, unlike many other MI learning methods, which are primarily developed for binary classification, we model multiple classes jointly, thus also capturing possible dependencies between different classes. We develop our model within a semisupervised framework, which leverages both labeled and, typically, a larger set of unlabeled bags for training. We develop several efficient inference methods for our model. We first introduce a Markov chain Monte Carlo method for inference, which can handle arbitrary relations between bag labels and instance labels, including the standard hard-max MI assumption. We also develop an extension of our model that uses stochastic variational Bayes methods for inference, and thus scales better to massive data sets. Experiments show that our approach outperforms several MI learning and standard classification methods on both bag-level and instance-level label prediction. All code for replicating our experiments is available from https://github.com/hsoleimani/MLTM .

We investigate semisupervised learning (SL) and pool-based active learning (AL) of a classifier for domains with label-scarce (LS) and unknown categories, i.e., defined categories for which there are initially no labeled examples. This scenario manifests, e.g., when a category is rare, or expensive to label. There are several learning issues when there are unknown categories: 1) it is a priori unknown which subset of (possibly many) measured features are needed to discriminate unknown from common classes and 2) label scarcity suggests that overtraining is a concern. Our classifier exploits the inductive bias that an unknown class consists of the subset of the unlabeled pool's samples that are atypical (relative to the common classes) with respect to certain key (albeit a priori unknown) features and feature interactions. Accordingly, we treat negative log- p -values on raw features as nonnegatively weighted derived feature inputs to our class posterior, with zero weights identifying irrelevant features. Through a hierarchical class posterior, our model accommodates multiple common classes, multiple LS classes, and unknown classes. For learning, we propose a novel semisupervised objective customized for the LS/unknown category scenarios. While several works minimize class decision uncertainty on unlabeled samples, we instead preserve this uncertainty [maximum entropy (maxEnt)] to avoid overtraining. Our experiments on a variety of UCI Machine learning (ML) domains show: 1) the use of p -value features coupled with weight constraints leads to sparse solutions and gives significant improvement over the use of raw features and 2) for LS SL and AL, unlabeled samples are helpful, and should be used to preserve decision uncertainty (maxEnt), rather than to minimize it, especially during the early stages of AL. Our AL system, leveraging a novel sample-selection scheme, discovers unknown classes and discriminates LS classes from common ones, with sparing use of oracle labeling.

Extracting parts of a text document relevant to a class label is a critical information retrieval task. We propose a semi-supervised multi-label topic model for jointly achieving document and sentence-level class inferences. Under our model, each sentence is associated with only a subset of the document's labels (including possibly none of them), with the label set of the document the union of the labels of all of its sentences. For training, we use both labeled documents, and, typically, a larger set of unlabeled documents. Our model, in a semisupervised fashion, discovers the topics present, learns associations between topics and class labels, predicts labels for new (or unlabeled) documents, and determines label associations for each sentence in every document. For learning, our model does not require any ground-truth labels on sentences. We develop a Hamiltonian Monte Carlo based algorithm for efficiently sampling from the joint label distribution over all sentences, a very high-dimensional discrete space. Our experiments show that our approach outperforms several benchmark methods with respect to both document and sentence-level classification, as well as test set log-likelihood. All code for replicating our experiments is available from https://github.com/hsoleimani/MLTM.

We propose a mixture of class-conditioned topic models for classifying text documents using both labeled and unlabeled training documents in a semi-supervised fashion. Most topic models incorporate documents' class labels by generating them after generating the word space. In these models, the training class labels have relatively small effect on the estimated topics, as the likelihood function is mostly dominated by the word space, whose size dwarfs a single class label per document. In this paper, we propose to increase the influence of class labels on model parameters by generating the word space in each document conditioned on the class label. We show that our specific generative process improves classification performance while maintaining the ability of the model to discover topics from the word space. Within our framework, we also provide a principled mechanism to control the contribution of the class labels and the word space to the likelihood function. Experimental results show that our approach achieves better classification performance compared to some standard semi-supervised and supervised topic models. We provide the required code to replicate our experiments at https://github.com/hsoleimani/MCCTM.

Dynamic time warping (DTW) is a fundamental technique in time series analysis for comparing one curve to another using a flexible time-warping function. However, it was designed to compare a single pair of curves. In many applications, such as in metabolomics and image series analysis, alignment is simultaneously needed for multiple pairs. Because the underlying warping functions are often related, independent application of DTW to each pair is a sub-optimal solution. Yet, it is largely unknown how to efficiently conduct a joint alignment with all warping functions simultaneously considered, since any given warping function is constrained by the others and dynamic programming cannot be applied. In this paper, we show that the joint alignment problem can be transformed into a network flow problem and thus can be exactly and efficiently solved by the max flow algorithm, with a guarantee of global optimality. We name the proposed approach graphical time warping (GTW), emphasizing the graphical nature of the solution and that the dependency structure of the warping functions can be represented by a graph. Modifications of DTW, such as windowing and weighting, are readily derivable within GTW. We also discuss optimal tuning of parameters and hyperparameters in GTW. We illustrate the power of GTW using both synthetic data and a real case study of an astrocyte calcium movie.

We propose an algorithm for detecting patterns exhibited by anomalous clusters in high dimensional discrete data. Unlike most anomaly detection (AD) methods, which detect individual anomalies, our proposed method detects groups (clusters) of anomalies; i.e., sets of points which collectively exhibit abnormal patterns. In many applications, this can lead to a better understanding of the nature of the atypical behavior and to identifying the sources of the anomalies. Moreover, we consider the case where the atypical patterns exhibit on only a small (salient) subset of the very high dimensional feature space. Individual AD techniques and techniques that detect anomalies using all the features typically fail to detect such anomalies, but our method can detect such instances collectively, discover the shared anomalous patterns exhibited by them, and identify the subsets of salient features. In this paper, we focus on detecting anomalous topics in a batch of text documents, developing our algorithm based on topic models. Results of our experiments show that our method can accurately detect anomalous topics and salient features (words) under each such topic in a synthetic data set and two real-world text corpora and achieves better performance compared to both standard group AD and individual AD techniques. All required code to reproduce our experiments is available from https://github.com/hsoleimani/ATD.

Crowdsourcing allows instant recruitment of workers on the web to annotate image, webpage, or document databases. However, worker unreliability prevents taking a worker's responses at “face value”. Thus, responses from multiple workers are typically aggregated to more reliably infer ground-truth answers. We study two approaches for crowd aggregation on multicategory answer spaces: stochastic modeling-based and deterministic objective function-based. Our stochastic model for answer generation plausibly captures the interplay between worker skills, intentions, and task difficulties and captures a broad range of worker types. Our deterministic objective-based approach aims to maximize the average aggregate confidence of weighted plurality crowd decision making. In both approaches, we explicitly model the skill and intention of individual workers, which is exploited for improved crowd aggregation. Our methods are applicable in both unsupervised and semi-supervised settings, and also when the batch of tasks is heterogeneous, i.e., from multiple domains, with task-dependent answer spaces. As observed experimentally, the proposed methods can defeat “tyranny of the masses”, i.e., they are especially advantageous when there is an (a priori unknown) minority of skilled workers amongst a large crowd of unskilled (and malicious) workers.

We propose a parsimonious topic model for text corpora. In related models such as Latent Dirichlet Allocation (LDA), all words are modeled topic-specifically, even though many words occur with similar frequencies across different topics. Our modeling determines salient words for each topic, which have topic-specific probabilities, with the rest explained by a universal shared model. Further, in LDA all topics are in principle present in every document. By contrast, our model gives sparse topic representation, determining the (small) subset of relevant topics for each document. We derive a Bayesian Information Criterion (BIC), balancing model complexity and goodness of fit. Here, interestingly, we identify an effective sample size and corresponding penalty specific to each parameter type in our model. We minimize BIC to jointly determine our entire model-the topic-specific words, document-specific topics, all model parameter values, and the total number of topics-in a wholly unsupervised fashion. Results on three text corpora and an image dataset show that our model achieves higher test set likelihood and better agreement with ground-truth class labels, compared to LDA and to a model designed to incorporate sparsity.

A new method for semisupervised learning from pairwise sample (must- and cannot-link) constraints is introduced. It addresses an important limitation of many existing methods, whose solutions do not achieve effective propagation of the constraint information to unconstrained samples. We overcome this limitation by constraining the solution to comport with a smooth (soft) class partition of the feature space, which necessarily entails constraint propagation and generalization to unconstrained samples. This is achieved via a parameterized mean-field approximation to the posterior distribution over component assignments, with the parameterization chosen to match the representation power of the chosen (generative) mixture density family. Unlike many existing methods, our method flexibly models classes using a variable number of components, which allows it to learn complex class boundaries. Also, unlike most of the methods, ours estimates the number of latent classes present in the data. Experiments on synthetic data and data sets from the UC Irvine machine learning repository show that, overall, our method achieves significant improvements in classification performance compared with the existing methods.

We consider multi-view classification for the challenging scenario where, for some views, there are no labeled training examples. Several discriminative approaches have been recently proposed for special instances of this problem. Here, alternatively, we propose a generative semi-supervised mixture model across all views which, via marginalization, flexibly performs exact class inference, given any subset of available views. The proposed model is an extension of semi-supervised mixtures to a multi-view setting, as well as a semi-supervised extension of mixtures of factors analyzers (MFA)[1]. A novel EM algorithm with a computationally efficient E-step is derived for learning our multi-view model. Specialization of this formulation to the standard MFA problem also gives a reduced complexity E-step, compared to the original EM algorithm proposed for MFA. Our multi-view method is experimentally demonstrated on digit recognition using audio and lip video views, achieving competitive results with alternative, discriminative approaches.

Schema matching and value mapping across two information sources, such as databases, are critical information aggregation tasks. Before data can be integrated from multiple tables, the columns and values within the tables must be matched. The complexities of both these problems grow quickly with the number of attributes to be matched and due to multiple semantics of data values. Traditional research has mostly tackled schema matching and value mapping independently, and for categorical (discrete-valued) attributes. We propose novel methods that leverage value mappings to enhance schema matching in the presence of opaque column names for schemas consisting of both continuous and discrete-valued attributes. An additional source of complexity is that a discrete-valued attribute in one schema could in fact be a quantized, encoded version of a continuous-valued attribute in the other schema. In our approach, which can tackle both “onto” and bijective schema matching, the fitness objective for matching a pair of attributes from two schemas exploits the statistical distribution over values within the two attributes. Suitable fitness objectives are based on Euclidean-distance and the data log-likelihood, both of which are applied in our experimental study. A heuristic local descent optimization strategy that uses two-opt switching to optimize attribute matches, while simultaneously embedding value mappings, is applied for our matching methods. Our experiments show that the proposed techniques matched mixed continuous and discrete-valued attribute schemas with high accuracy and, thus, should be a useful addition to a framework of (semi) automated tools for data alignment.

We introduce new inductive, generative semisupervised mixtures with more finely grained class label generation mechanisms than in previous work. Our models combine advantages of semisupervised mixtures, which achieve label extrapolation over a component, and nearest-neighbor (NN)/nearest-prototype (NP) classification, which achieve accurate classification in the vicinity of labeled samples or prototypes. For our NN-based method, we propose a novel two-stage stochastic data generation, with all samples first generated using a standard finite mixture and then all class labels generated, conditioned on the samples and their components of origin. This mechanism entails an underlying Markov random field, specific to each mixture component or cluster. We invoke the pseudo-likelihood formulation, which forms the basis for an approximate generalized expectation-maximization model learning algorithm. Our NP-based model overcomes a problem with the NN-based model that manifests at very low labeled fractions. Both models are advantageous when within-component class proportions are not constant over the feature space region “owned by” a component. The practicality of this scenario is borne out by experiments on UC Irvine data sets, which demonstrate significant gains in classification accuracy over previous semisupervised mixtures and also overall gains, over KNN classification. Moreover, for very small labeled fractions, our methods overall outperform supervised linear and nonlinear kernel support vector machines.

Echo state networks (ESNs) are a novel form of recurrent neural networks (RNNs) that provide an efficient and powerful computational model approximating nonlinear dynamical systems. A unique feature of an ESN is that a large number of neurons (the "reservoir") are used, whose synaptic connections are generated randomly, with only the connections from the reservoir to the output modified by learning. Why a large randomly generated fixed RNN gives such excellent performance in approximating nonlinear systems is still not well understood. In this brief, we apply random matrix theory to examine the properties of random reservoirs in ESNs under different topologies (sparse or fully connected) and connection weights (Bernoulli or Gaussian). We quantify the asymptotic gap between the scaling factor bounds for the necessary and sufficient conditions previously proposed for the echo state property. We then show that the state transition mapping is contractive with high probability when only the necessary condition is satisfied, which corroborates and thus analytically explains the observation that in practice one obtains echo states when the spectral radius of the reservoir weight matrix is smaller than 1.

Flow classification by application type is motivated by on-line anomaly detection, off-line network planning, and on-line enforcement of terms-of-use policies by public ISPs or by administrators of private-enterprise networks. Both signature matching and a variety of feature-based pattern recognition methods have been applied to address this problem. In this paper, we propose a TCP flow classifier that employs neither packet header information that is protocol-specific (including port numbers) nor packet-payload information. Techniques based on the former are readily evadable, while detailed yet scalable inspection of packet payloads is difficult to achieve, may violate privacy laws, and is defeated by data encryption. Our classifier is tested on two contemporary publicly available datasets recorded in similar networking contexts. We consider the often encountered scenario where ground-truth labels, necessary for supervised classifier training, are unavailable for a domain where flow classification needs to be applied. In this case, one must "port over" a classifier trained on one domain to make decisions on another. We address issues in reconciling differences in class definitions between the two domains. We also demonstrate by our results that domain differences in the class-conditional feature distributions, which will exist in practice, can lead to substantial losses in classification accuracy on the new domain. Finally, we also propose and evaluate a hypothesis testing approach to detect port spoofing by exploiting confusion matrix statistics.

We have recently introduced new generative semi supervised mixtures with more fine-grained class label generation mechanisms than previous methods. Our models combine advantages of semi supervised mixtures, which achieve label extrapolation over a component, and nearest-neighbor (NN)/nearest-prototype (NP) classification, which achieves accurate classification in the vicinity of labeled samples. Our models are advantageous when within-component class proportions are not constant over the feature space region "owned by'' a component. In this paper, we develop an active learning extension of our fine-grained labeling methods. We propose two new uncertainty sampling methods in comparison with traditional entropy-based uncertainty sampling. Our experiments on a number of UC Irvine data sets show that the proposed active learning methods improve classification accuracy more than standard entropy-based active learning. The proposed methods are particularly advantageous when the labeled percentage is small. We also extend our semi supervised method to allow variable weighting on labeled and unlabeled data likelihood terms. This approach is shown to outperform previous weighting schemes.

Schema matching and value mapping across two heterogeneous information sources are critical tasks in applications involving data integration, data warehousing, and federation of databases. Before data can be integrated from multiple tables, the columns and the values appearing in the tables must be matched. The complexity of the problem grows quickly with the number of data attributes/columns to be matched and due to multiple semantics of data values. Traditional research has tackled schema matching and value mapping independently. We propose a novel method that optimizes embedded value mappings to enhance schema matching in the presence of opaque data values and column names. In this approach, the fitness objective for matching a pair of attributes from two schemas depends on the value mapping function for each of the two attributes. Suitable fitness objectives include the euclidean distance measure, which we use in our experimental study, as well as relative (cross) entropy. We propose a heuristic local descent optimization strategy that uses sorting and two-opt switching to jointly optimize value mappings and attribute matches. Our experiments show that our proposed technique outperforms earlier uninterpreted schema matching methods, and thus, should form a useful addition to a suite of (semi) automated tools for resolving structural heterogeneity.

Feature selection for classification in high-dimensional spaces can improve generalization, reduce classifier complexity, and identify important, discriminating feature "markers." For support vector machine (SVM) classification, a widely used technique is recursive feature elimination (RFE). We demonstrate that RFE is not consistent with margin maximization, central to the SVM learning approach. We thus propose explicit margin-based feature elimination (MFE) for SVMs and demonstrate both improved margin and improved generalization, compared with RFE. Moreover, for the case of a nonlinear kernel, we show that RFE assumes that the squared weight vector 2-norm is strictly decreasing as features are eliminated. We demonstrate this is not true for the Gaussian kernel and, consequently, RFE may give poor results in this case. MFE for nonlinear kernels gives better margin and generalization. We also present an extension which achieves further margin gains, by optimizing only two degrees of freedom--the hyperplane's intercept and its squared 2-norm--with the weight vector orientation fixed. We finally introduce an extension that allows margin slackness. We compare against several alternatives, including RFE and a linear programming method that embeds feature selection within the classifier design. On high-dimensional gene microarray data sets, University of California at Irvine (UCI) repository data sets, and Alzheimer's disease brain image data, MFE methods give promising results.

MOTIVATION: In both genome-wide association studies (GWAS) and pathway analysis, the modest sample size relative to the number of genetic markers presents formidable computational, statistical and methodological challenges for accurately identifying markers/interactions and for building phenotype-predictive models. RESULTS: We address these objectives via maximum entropy conditional probability modeling (MECPM), coupled with a novel model structure search. Unlike neural networks and support vector machines (SVMs), MECPM makes explicit and is determined by the interactions that confer phenotype-predictive power. Our method identifies both a marker subset and the multiple k-way interactions between these markers. Additional key aspects are: (i) evaluation of a select subset of up to five-way interactions while retaining relatively low complexity; (ii) flexible single nucleotide polymorphism (SNP) coding (dominant, recessive) within each interaction; (iii) no mathematical interaction form assumed; (iv) model structure and order selection based on the Bayesian Information Criterion, which fairly compares interactions at different orders and automatically sets the experiment-wide significance level; (v) MECPM directly yields a phenotype-predictive model. MECPM was compared with a panel of methods on datasets with up to 1000 SNPs and up to eight embedded penetrance function (i.e. ground-truth) interactions, including a five-way, involving less than 20 SNPs. MECPM achieved improved sensitivity and specificity for detecting both ground-truth markers and interactions, compared with previous methods. AVAILABILITY: http://www.cbil.ece.vt.edu/ResearchOngoingSNP.htm

Many ensemble classification systems apply supervised learning to design a function for combining classifier decisions, which requires common labeled training samples across the classifier ensemble. Without such data, fixed rules (voting, Bayes rule) are usually applied. [1] alternatively proposed a transductive constraint-based learning strategy to learn how to fuse decisions even without labeled examples. There, decisions on test samples were chosen to satisfy constraints measured by each local classifier. There are two main limitations of that work. First, feasibility of the constraints was not guaranteed. Second, heuristic learning was applied. Here we overcome both problems via a transductive extension of maximum entropy/improved iterative scaling for aggregation in distributed classification. This method is shown to achieve improved decision accuracy over the earlier transductive approach on a number of UC Irvine data sets.

BACKGROUND: The main limitations of most existing clustering methods used in genomic data analysis include heuristic or random algorithm initialization, the potential of finding poor local optima, the lack of cluster number detection, an inability to incorporate prior/expert knowledge, black-box and non-adaptive designs, in addition to the curse of dimensionality and the discernment of uninformative, uninteresting cluster structure associated with confounding variables. RESULTS: In an effort to partially address these limitations, we develop the VIsual Statistical Data Analyzer (VISDA) for cluster modeling, visualization, and discovery in genomic data. VISDA performs progressive, coarse-to-fine (divisive) hierarchical clustering and visualization, supported by hierarchical mixture modeling, supervised/unsupervised informative gene selection, supervised/unsupervised data visualization, and user/prior knowledge guidance, to discover hidden clusters within complex, high-dimensional genomic data. The hierarchical visualization and clustering scheme of VISDA uses multiple local visualization subspaces (one at each node of the hierarchy) and consequent subspace data modeling to reveal both global and local cluster structures in a "divide and conquer" scenario. Multiple projection methods, each sensitive to a distinct type of clustering tendency, are used for data visualization, which increases the likelihood that cluster structures of interest are revealed. Initialization of the full dimensional model is based on first learning models with user/prior knowledge guidance on data projected into the low-dimensional visualization spaces. Model order selection for the high dimensional data is accomplished by Bayesian theoretic criteria and user justification applied via the hierarchy of low-dimensional visualization subspaces. Based on its complementary building blocks and flexible functionality, VISDA is generally applicable for gene clustering, sample clustering, and phenotype clustering (wherein phenotype labels for samples are known), albeit with minor algorithm modifications customized to each of these tasks. CONCLUSION: VISDA achieved robust and superior clustering accuracy, compared with several benchmark clustering schemes. The model order selection scheme in VISDA was shown to be effective for high dimensional genomic data clustering. On muscular dystrophy data and muscle regeneration data, VISDA identified biologically relevant co-expressed gene clusters. VISDA also captured the pathological relationships among different phenotypes revealed at the molecular level, through phenotype clustering on muscular dystrophy data and multi-category cancer data.

We consider ensemble classification for the case where there is no common labeled training data for jointly designing the individual classifiers and the function that aggregates their decisions. This problem, which we call distributed ensemble classification, applies when individual classifiers operate (perhaps remotely) on different sensing modalities and when combining proprietary or legacy classifiers. The conventional wisdom in this case is to apply fixed rules of combination such as voting methods or rules for aggregating probabilities. Alternatively, we take a transductive approach, optimizing the combining rule for an objective function measured on the unlabeled batch of test data. We propose maximum likelihood (ML) objectives that are shown to yield well-known forms of probabilistic aggregation, albeit with iterative, expectation-maximization-based adjustment to account for mismatch between class priors used by individual classifiers and those reflected in the new data batch. These methods are extensions, for the ensemble case, of the work of Saerens, Latinne, and Decaestecker (2002). We also propose an information-theoretic method that generally outperforms the ML methods, better handles classifier redundancies, and addresses some scenarios where the ML methods are not applicable. This method also well handles the case of missing classes in the test batch. On UC Irvine benchmark data, all our methods give improvements in classification accuracy over the use of fixed rules when there is prior mismatch.

Though supervised and unsupervised analyses of genomic data have been intensively studied in recent years, little effort has been made to discover the structural information contained in the data. In this work, we propose a stability analysis guided supervised clustering and visualization method aiming to discover the hierarchical structure in gene expression data, which we call the "tree of phenotypes". We applied the method on two multiclass gene expression microarray data sets and presented the biological plausibility of the learned trees. We also tested the multiclass classifiers built on the learned trees and demonstrated their good classification performance

Mining traffic to identify the dominant flows sent over a given link, over a specified time interval, is a valuable capability with applications to traffic auditing, simulation, visualization, as well as anomaly detection. Recently, Estan advanced a comprehensive data mining structure tailored for networking data-a parsimonious, multidimensional flow hierarchy, along with an algorithm for its construction. While they primarily targeted offline auditing, use in interactive traffic visualization and anomaly/attack detection will require real-time data mining. We suggest several improvements to Estan's algorithm that substantially reduce the computational complexity of multidimensional flow mining. We also propose computational and memory-efficient approaches for unidimensional clustering of the IP address spaces. For baseline implementations, evaluated on the New Zealand (NZIX) trace data, our method reduced CPU execution times of the Estan method by a factor of more than eight. We also develop a methodology for anomaly/attack detection based on flow mining, demonstrating the usefulness of this approach on traces from the Slammer and Code Red worms and the MIT Lincoln Laboratories DDoS data

We describe a hierarchical traffic shaper-scheduler, hierarchical SDRR (HSDRR), for flows of variable-length packets that is low-complexity (scales with the number of queues). That is, HSDRR can be used channelize the output link of a router to satisfy service-level agreements (token bucket constraints) struck at network-to-network boundaries. HSDRR is a hybrid round-robin/time-stamp scheduler (S. Ramabhadran and J. Pasquale, 2003) that employs shaped deficit round-robin (SDRR) (S. Jiwasurat and G. Kesidis, 2004) scheduling in the first stage and shaped virtual clock (SVC) (D. Stiliadis and A. Varma, 1997) in the second and final stage.

Most prior work on semisupervised clustering/mixture modeling with given class constraints assumes the number of classes is known, with each learned cluster assumed to be a class and, hence, subject to the given instance-level constraints. When the number of classes is incorrectly assumed and/or when the "one-cluster-per-class" assumption is not valid, the use of constraint information in these methods may actually be deleterious to learning the ground-truth data groups. We extend semisupervised learning with constraints (1) to allow allocation of multiple mixture components to individual classes and (2) to estimate both the number of components/clusters and, leveraging the constraint information, the number of classes present in the data. For several real-world data sets, our method is shown to estimate correctly the number of classes and to give a favorable comparison with the recent mixture modeling approach of N. Shental et al. (see NIPS, 2003).

The goal of semisupervised clustering/mixture modeling is to learn the underlying groups comprising a given data set when there is also some form of instance-level supervision available, usually in the form of labels or pairwise sample constraints. Most prior work with constraints assumes the number of classes is known, with each learned cluster assumed to be a class and, hence, subject to the given class constraints. When the number of classes is unknown or when the one-cluster-per-class assumption is not valid, the use of constraints may actually be deleterious to learning the ground-truth data groups. We address this by (1) allowing allocation of multiple mixture components to individual classes and (2) estimating both the number of components and the number of classes. We also address new class discovery, with components void of constraints treated as putative unknown classes. For both real-world and synthetic data, our method is shown to accurately estimate the number of classes and to give favorable comparison with the recent approach of Shental, Bar-Hillel, Hertz, and Weinshall (2003).

We address the longstanding problem of learning and model selection in finite mixtures. A common approach is to generate solutions of varying number of components - via the expectation-maximization (EM) algorithm - and then select the best model in the sense of a cost such as the Bayesian information criterion (BIC). A recent alternative uses component-wise EM (CEM) and, further, integrates model selection within CEM. Both approaches are susceptible to finding poor solutions, the first due to the initialization sensitivity of EM and the second due to the sequential (greedy) nature of CEM. Deterministic annealing for clustering (DA) and mixture modeling (DAEM) provide potential for avoiding local optima. However, these methods do not encompass model selection. We propose a new technique with positive attributes of all these methods: it integrates learning and model selection, performs batch optimization over components, and has the character of DA, with the optimization performed over a sequence of decreasing temperatures. Unlike standard DA, with the partition entropy reduced as the temperature is lowered, our approach reduces the entropy of binary random variables that express whether each component is active or inactive. At low temperature, the method achieves explicit model order selection. Experiments demonstrate the favorable performance of our method, compared with several alternatives. We also give an interesting stochastic generative model interpretation for our method.

A common joint source-channel (JSC) decoder structure for predictively encoded sources involves first forming a JSC decoding estimate of the prediction residual and then feeding this estimate to a standard predictive decoding (synthesis) filter. In this paper, we demonstrate that in a JSC decoding context, use of this standard filter is suboptimal. In place of the standard filter, we choose the synthesis filter coefficients to give a least-squares (LS) estimate of the original source, based on given training data. For first-order differential pulse-code modulation, this yields as much as 0.65-dB gain in reconstructing first-order Gauss-Markov sources. More gains are achieved with modest additional complexity by increasing the filter order. While performance can also be enhanced by increasing the source's Markov model order and/or the decoder's lookup table memory, complexity grows exponentially in these parameters. For both predictive and nonpredictive coding, our LS approach offers a strategy for increasing the estimation accuracy of JSC decoders while retaining manageable complexity.

Several authors have addressed learning a classifier given a mixed labeled/unlabeled training set. These works assume each unlabeled sample originates from one of the (known) classes. Here, we consider the scenario in which unlabeled points may belong either to known/predefined or to heretofore undiscovered classes. There are several practical situations where such data may arise. We propose a novel statistical mixture model which views as observed data not only the feature vector and the class label, but also the fact of label presence/absence for each point. Two types of mixture components are posited to explain label presence/absence. "Predefined" components generate both labeled and unlabeled points and assume labels are missing at random. "Non-predefined" components only generate unlabeled points-thus, in localized regions, they capture data subsets that are exclusively unlabeled. Such subsets may represent an outlier distribution, or new classes. The components' predefined/non-predefined natures are data-driven, learned along with the other parameters via an algorithm based on expectation-maximization (EM). There are three natural applications: (1) robust classifier design, given a mixed training set with outliers; (2) classification with rejections; (3) identification of the unlabeled points (and their representative components) that originate from unknown classes, i.e. new class discovery. We evaluate our method and alternative approaches on both synthetic and real-world data sets.

Several authors have shown that, when labeled data are scarce, improved classifiers can be built by augmenting the training set with a large set of unlabeled examples and then performing suitable learning. These works assume each unlabeled sample originates from one of the (known) classes. Here, we assume each unlabeled sample comes from either a known or from a heretofore undiscovered class. We propose a novel mixture model which treats as observed data not only the feature vector and the class label, but also the fact of label presence/absence for each sample. Two types of mixture components are posited. "Predefined" components generate data from known classes and assume class labels are missing at random. "Nonpredefined" components only generate unlabeled data-i.e., they capture exclusively unlabeled subsets, consistent with an outlier distribution or new classes. The predefined/nonpredefined natures are data-driven, learned along with the other parameters via an extension of the EM algorithm. Our modeling framework addresses problems involving both the known,and unknown classes: (1) robust classifier design, (2) classification with rejections, and (3) identification of the unlabeled samples (and their components) from unknown classes. Case 3 is a step toward new class discovery. Experiments are reported for each application, including topic discovery for the Reuters domain. Experiments also demonstrate the value of label presence/absence data in learning accurate mixtures.

Mean-field annealing (MFA) is widely used for optimization tasks involving the determination of a set of discrete-valued assignment variables. One way of deriving MFA is via maximum entropy (ME), where one seeks the joint distribution over the (random) assignments subject to an average level of cost. MFA is obtained by assuming the individual assignments are independent. Here we propose an MFA extension for problems defined on the pixel sites of an image. Rather than introducing variables for individual sites, we represent label choices for an entire image row (or column). We then make the less restrictive assumption of independent row (rather than pixel) labelings. While it is not possible to explicitly evaluate the row labeling distribution, we can, via a Forward/Backward algorithm, explicitly evaluate sums over this distribution, to obtain a posteriori probabilities at individual sites. It turns out that the site probabilities, in turn, determine (updated) row labeling probabilities. Thus, the Forward/Backward algorithm forms the basis of an iteration, applied to the rows(columns) of the image, that yields optimized a posteriori site probabilities. This iterative method descends in the ME Lagrangian/free energy. Our method was applied to segmentation of synthetic, noise-corrupted Markov random field images. It achieved substantial reduction in misclassification rates, compared with both ICM and standard MFA.

We develop an iterative, hillclimbing-based assignment algorithm for the approximate solution of discrete-parameter cost minimization problems defined on the pixel sites of an image. While the method is applicable to a number of problems including encoding, decoding, and segmentation, this article focuses on entropy-constrained encoding. For typical statistical image models, the globally optimal solution requires an intractable exhaustive search, while standard greedy methods, though tractable in computation, may be quite suboptimal. Alternatively, our method is guaranteed to perform no worse (and typically performs significantly better) than greedy encoding, yet with manageable increases in complexity. The new approach uses dynamic programming as a local optimization "step," repeatedly applied to the rows (or columns) of the image, until convergence. For a DCT framework, with entropy-constrained TCQ applied to the coefficient sources, the new method gains as much as 0.8 dB over standard greedy encoding.

We address the choice of encoder for conditional entropy-constrained trellis-coded quantization (CECTCQ), applied to image transform coefficients. The optimal CECTCQ encoder requires an (utterly intractable) exhaustive search and the standard method of greedy, sequential encoding of the coefficient "sources" is suboptimal. Alternatively, we suggest a locally optimal encoding algorithm, guaranteed to improve performance over greedy encoding, and yet with manageable increases in encoding complexity. This method uses dynamic programming as a local optimization encoding "step", repeatedly applied until convergence. Simulations demonstrate up to 1.5 dB gain over greedy CECTCQ encoding of block-transformed images.

The growth of digital cellular telephony has created demand for rich multimedia services similar to what we have come to expect of wire-line communications. The applications are far reaching such as video conferencing, emergency medical consultation and directions to m-commerce, remote site surveying and embedded navigational systems. Global standards bodies such as 3GPP, ETSI, ARIB and ITU-T have converged upon the next generation infrastructure capable of providing broadband services to mobile devices in the form of packet switched WCDMA. The focus of our research is on error resilient coding earmarked to reach data rates ranging from 144 Kbps to 2 Mbps on the uplink with the aim of substantial performance improvements. Toward this end we present a two-fold approach, focusing on error-resilient video coding and smart antennae for robust transmission. An accurate simulation of the end-to-end system was implemented using SPW, with performance measured in terms of PSNR and bit error rates.

We propose a new learning method for discrete space statistical classifiers. Similar to Chow and Liu (1968) and Cheeseman (1983), we cast classification/inference within the more general framework of estimating the joint probability mass function (p.m.f.) for the (feature vector, class label) pair. Cheeseman's proposal to build the maximum entropy (ME) joint p.m.f. consistent with general lower-order probability constraints is in principle powerful, allowing general dependencies between features. However, enormous learning complexity has severely limited the use of this approach. Alternative models such as Bayesian networks (BNs) require explicit determination of conditional independencies. These may be difficult to assess given limited data. Here we propose an approximate ME method, which, like previous methods, incorporates general constraints while retaining quite tractable learning. The new method restricts joint p.m.f. support during learning to a small subset of the full feature space. Classification gains are realized over dependence trees, tree-augmented naive Bayes networks, BNs trained by the Kutato algorithm, and multilayer perceptrons. Extensions to more general inference problems are indicated. We also propose a novel exact inference method when there are several missing features.

Joint source-channel decoding based on residual source redundancy is an effective paradigm for error-resilient data compression. While previous work only considered fixed-rate systems, the extension of these techniques for variable-length encoded data was independently proposed by the authors and by Demir and Sayood (see Proc. Data Comp. Conf., Snowbird, UT, p.139-48, 1998). We describe and compare the performance of a computationally complex exact maximum a posteriori (MAP) decoder, its efficient approximation, an alternative approximate decoder, and an improved version of this decoder are suggested. Moreover, we evaluate several source and channel coding configurations. The results show that our approximate MAP technique outperforms other approximate methods and provides substantial error protection to variable-length encoded data.

We propose a new method for learning a general statistical inference engine, operating on discrete and mixed discrete/continuous feature spaces. Such a model allows inference on any of the discrete features, given values for the remaining features. Applications are, e.g., to medical diagnosis with multiple possible diseases, fault diagnosis, information retrieval, and imputation in databases. Bayesian networks (BN's) are versatile tools that possess this inference capability. However, BN's require explicit specification of conditional independencies, which may be difficult to assess given limited data. Alternatively, Cheeseman proposed finding the maximum entropy (ME) joint probability mass function (pmf) consistent with arbitrary lower order probability constraints. This approach is in principle powerful and does not require explicit expression of conditional independence. However, until now, the huge learning complexity has severely limited the use of this approach. Here we propose an approximate ME method, which also encodes arbitrary low-order constraints but while retaining quite tractable learning. Our method uses a restriction of joint pmf support (during learning) to a subset of the feature space. Results on the University of California-Irvine repository reveal performance gains over several BN approaches and over multilayer perceptrons.

Summary form only given. We develop improved joint source-channel (JSC) methods for decoding variable length encoded data based on residual source redundancy. Until very recently, all JSC methods based on residual redundancy assumed fixed length codewords. Recently, a practically realizable system which performed best over a significant range of channel conditions consisting of inner binary convolutional (BC) (bit-level) decoding, followed by outer (symbol-level) approximate maximum a posteriori (MAP) JSC decoding was suggested. Here we suggest two ways of improving on this method. First, a straightforward improvement is realized by using soft/probabilistic bit decisions output by the BC decoder, rather than hard decisions. Second, the JSC decoder can itself generate soft/probabilistic output, at the symbol level. The exact VLC minimum mean-squared error (MMSE) decoder has large complexity, similar to the exact MAP method, because the number of states increases with time. Thus we suggest an approximate MMSE method. In this approximate scheme, we first form a reduced directed graph, using the same MAP state reduction procedure as used for approximate MAP JSC decoding. Next, we rearrange the remaining states to form an (equivalent) directed graph. We then apply the forward/backward algorithm and a state merging procedure to this reduced graph to get approximate a posteriori probabilities, used for MMSE estimation.

We develop new rules for combining estimates obtained from each classifier in an ensemble. A variety of combination techniques have been previously suggested, including averaging probability estimates, as well as hard voting schemes. We introduce a critic associated with each classifier, whose objective is to predict the classifier's errors. Since the critic only tackles a two-class problem, its predictions are generally more reliable than those of the classifier, and thus can be used as the basis for our suggested improved combination rules. While previous techniques are only effective when the individual classifier error rate is p<0.5, the new approach is successful, as proved under an independence assumption, even when this condition is violated-in particular, so long as p+q<1, with q the critic's error rate. More generally, critic-driven combining achieves consistent, substantial performance improvement over alternative methods, on a number of benchmark data sets.

Joint source-channel decoding based on residual source redundancy is an effective paradigm for error-resilient data compression. While previous work only considered fixed rate systems, the extension of these techniques for variable-length encoded data was previously independently proposed by the authors, Park and Miller (see Proc. of Conf. on Info. Sciences and Systems, Princeton, N.J., 1998) and by Demir and Sayood (see Proc. of the Data Compression Conf., Snowbird, U.T., p.139-48, 1998). In this paper, we describe and compare the performance of a computationally complex exact maximum a posteriori (MAP) decoder, its efficient approximation, an alternative approximate MAP decoder, and an improved version of this decoder suggested here. Moreover, we evaluate several source and channel coding configurations. Our results show that the approximate MAP technique from Park et al. outperforms other approximate methods and provides substantial error protection to variable-length encoded data.

In this work, we propose neural network inversion of a backward predictor as a technique for multi-step prediction of dynamic time series. It may be difficult to train a large network to capture the correlation that exists in some dynamic time series represented by small data sets. The new approach combines an estimate obtained from a forward predictor with an estimate obtained by inverting a backward predictor to more efficiently capture the correlation and to achieve more accurate predictions. Inversion allows us to make causal use of prediction backward in time. Also a new regularization method is developed to make neural network inversion less ill-posed. Experimental results on two benchmark time series demonstrate the new approach's significant improvement over standard forward prediction, given comparable complexity.

We propose a new method for learning discrete space statistical classifiers. We cast classification/inference within the more general framework of estimating the joint probability mass function (PMF) for the (feature vector, class label) pair. The proposal of Cheeseman (1983) to construct the maximum entropy (ME) joint PMF consistent with general lower order probability constraints has been severely limited by its huge learning complexity. Alternatives such as Bayesian networks require explicit specification of conditional independencies. Here we reconsider the ME problem, propose an approximate method which encodes arbitrary low order constraints, while retaining quite tractable learning. The new method approximates the joint feature PMF during learning on a sub-grid of the full feature space. Extensions to more general inference problems are indicated.

A new learning algorithm is proposed for piecewise regression modeling. It employs the technique of deterministic annealing to design space partition regression functions. While the performance of traditional space partition regression functions such as CART and MARS is limited by a simple tree-structured partition and by a hierarchical approach for design, the deterministic annealing algorithm enables the joint optimization of a more powerful piecewise structure based on a Voronoi partition. The new method is demonstrated to achieve consistent performance improvements over regular CART as well as over its extension to allow arbitrary hyperplane boundaries. Comparison tests, on several benchmark data sets from the regression literature, are provided.

The transmission of video over time-varying wireless communication channels can benefit from the use of joint source-channel (JSC) coding methods. We survey relevant research in JSC code design and discuss how this work can be used for video compression and transmission. A main focus is the use of estimation-based techniques to take advantage of the residual redundancy present at the output of the source encoder. As noted in previous work, the combination of the source encoder and channel can often be modeled as a hidden Markov model. This statistical framework is the basis for state estimation and minimum mean-square error estimation procedures for JSC decoding, and it can also be used to develop channel state and channel parameter estimation methods. We discuss these approaches, along with work that also incorporates modulation, channel coding, and rate allocation within the JSC design. The integration of these methods into video compression standards is considered.

Joint source-channel (JSC) decoding based on residual source redundancy is a technique for providing channel robustness to quantized data. Previous work assumed a model equivalent to viewing the encoder/noisy channel tandem as a discrete hidden Markov model (HMM) with transmitted indices the hidden states. We generalize this HMM-based (1-D) approach for images, using the more powerful hidden Markov mesh random field (HMMRF) model. While previous state estimation methods for HMMRFs base estimates on only a causal subset of the observed data, our new method uses both causal and anticausal subsets. For JSC-based image decoding, the new method provides significant benefits over several competing techniques.

The partitioning in hierarchical trees (SPIHT) algorithm for wavelet-based image coding, suggested by Said and Pearlman (1996), achieves excellent rate-distortion efficiency while retaining an attractive embedded code property useful for progressive transmission. In the present work we investigate several alternative set partitioning coding strategies in an effort to improve upon SPIHT. The general thrust of our research aims at increasing the size of the sets for which coefficient significance information is efficiently transmitted. While we suggest several novel coding ideas for achieving this objective, the resulting method is not found to provide a performance advantage over SPIHT. Some explanation for this observed performance is then provided.

We show that the decision function of a radial basis function (RBF) classifier is equivalent in form to the Bayes-optimal discriminant associated with a special kind of mixture-based statistical model. The relevant mixture model is a type of mixture-of-experts model for which class labels, like continuous-valued features, are assumed to have been generated randomly, conditional on the mixture component of origin. The new interpretation shows that RBF classifiers effectively assume a probability model, which, moreover, is easily determined given the designed RBF. This interpretation also suggests a statistical learning objective as an alternative to standard methods for designing the RBF-equivalent models. The statistical objective is especially useful for incorporating unlabeled data to enhance learning. Finally, it is observed that any new data to classify are simply additional unlabeled data. Thus, we suggest a combined learning and use paradigm, to be invoked whenever there are new data to classify.

In previous work on source coding over noisy channels it was recognized that when the source has memory, there is typically "residual redundancy" between the discrete symbols produced by the encoder, which can be capitalized upon by the decoder to improve the overall quantizer performance. Sayood and Borkenhagen (1991) and Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, p.186-93, 1994) proposed "detectors" at the decoder which optimize suitable criteria in order to estimate the sequence of transmitted symbols. Phamdo and Farvardin also proposed an instantaneous approximate minimum mean-squared error (IAMMSE) decoder. These methods provide a performance advantage over conventional systems, but the maximum a posteriori (MAP) structure is suboptimal, while the IAMMSE decoder makes limited use of the redundancy. Alternatively, combining aspects of both approaches, we propose a sequence-based approximate MMSE (SAMMSE) decoder. For a Markovian sequence of encoder-produced symbols and a discrete memoryless channel, we approximate the expected distortion at the decoder under the constraint of fixed decoder complexity. For this simplified cost, the optimal decoder computes expected values based on a discrete hidden Markov model, using the wellknown forward/backward (F/B) algorithm. Performance gains for this scheme are demonstrated over previous techniques in quantizing Gauss-Markov sources over a range of noisy channel conditions. Moreover, a constrained delay version is also suggested.

A new and effective design method is presented for statistical regression functions that belong to the class of mixture models. The class includes the hierarchical mixture of experts (HME) and the normalized radial basis functions (NRBF). Design algorithms based on the maximum likelihood (ML) approach, which emphasize a probabilistic description of the model, have attracted much interest in HME and NRBF models. However, their design objective is mismatched to the original squared-error regression cost and the algorithms are easily trapped by poor local minima on the cost surface. In this paper, we propose an extension of the deterministic annealing (DA) method for the design of mixture-based regression models. We construct a probabilistic framework, but unlike the ML method, we directly optimize the squared-error regression cost, while avoiding poor local minima. Experimental results show that the DA method outperforms standard design methods for both HME and NRBF regression models.

Recently, we developed a sequence-based minimum mean-squared error (MMSE) estimator for decoding quantized data transmitted over noisy channels. The method effectively views the encoder and noisy channel tandem as a discrete hidden Markov model (HMM), with transmitted indices the unknown states and received indices the observable symbols. Here, we extend this 1D approach to images, using a Markov mesh random field to model the encoded image. Our decoder is based on an approximate forward/backward algorithm for calculating pixel "label probabilities" in Markov meshes which may also have application to image labeling and segmentation. For a DPCM-based image coding system and a high error-rate channel, the new decoder obtains significant performance gains, both objective and visually discernable, over the standard decoder, as well as over several other competing techniques.

A new algorithm is developed for realizing optimal maximum a posteriori (MAP) estimates of the hidden states associated with a hidden Markov model, given a sequence of observed symbols. The standard MAP algorithm of Bahl et al., requires direct calculation of the a posteriori probabilities using the forward/backward algorithm, with each state estimate based on the entire observation sequence. For decoding applications, this implies huge, practically infinite delay. The new algorithm finds the optimal MAP estimate without directly computing the a posteriori probabilities and is a variable delay method that typically achieves a small average delay. The method is applied, in comparison with known techniques, to the problem of source decoding over noisy channels.

In vector quantization, one approximates an input random vector, Y, by choosing from a finite set of values known as the codebook. We consider a more general problem where one may not have direct access to Y but only to some statistically related random vector X. We observe X and would like to generate an approximation to Y from a codebook of candidate vectors. This operation, called generalized vector quantization (GVQ), is essentially that of quantized estimation. An important special case of GVQ is the problem of noisy source coding wherein a quantized approximation of a vector, Y, is obtained from observation of its noise-corrupted version, X. The optimal GVQ encoder has high complexity. We overcome the complexity barrier by optimizing a structurally-constrained encoder. This challenging optimization task is solved via a probabilistic approach, based on deterministic annealing, which overcomes problems of shallow local minima that trap simpler descent methods. We demonstrate the successful application of our method to the coding of noisy sources.

We address unsupervised learning subject to structural constraints, with particular emphasis placed on clustering with an imposed decision tree structure. Most known methods are greedy, optimizing one node of the tree at a time to minimize a local cost. By constrast, we develop a joint optimization method, derived based on information-theoretic principles and closely related to known methods in statistical physics. The approach is inspired by the deterministic annealing algorithm for unstructured data clustering, which was based on maximum entropy inference. The new approach is founded on the principle of minimum cross-entropy, using informative priors to approximate the unstructured clustering solution while imposing the structural constraint. The resulting method incorporates supervised learning principles applied in an unsupervised problem setting. In our approach, the tree “grows” by a sequence of bifurcations that occur while optimizing an effective free energy cost at decreasing temperature scales. Thus, estimates of the tree size and structure are naturally obtained at each temperature in the process. Examples demonstrate considerable improvement over known methods.

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.

The authors address the variable rate tree-structured vector quantizer design problem, wherein the rate is measured by the quantizer's entropy. For this problem, tree pruning via the generalized Breiman-Friedman-Olshen-Stone (1980) algorithm obtains solutions which are optimal over the restricted solution space consisting of all pruned trees derivable from an initial tree. However, the restrictions imposed on such solutions have several implications. In addition to depending on the tree initialization, growing and pruning solutions result in tree-structured vector quantizers which use a sub-optimal encoding rule. To remedy the latter problem, they consider a "tree-constrained" version of entropy-constrained vector quantizer design. This leads to an optimal tree-structured encoding rule for the leaves. In practice, though, improvements obtained in this fashion are limited by the tree initialization, as well as by the sub-optimal encoding performed at non-leaf nodes. To address these problems, they develop a joint optimization method which is inspired by the deterministic annealing algorithm for data clustering, and which extends their previous work on tree-structured vector quantization. The method is based on the principle of minimum cross entropy, using informative priors to approximate the unstructured solution while imposing the structural constraint. As in the original deterministic annealing method, the number of distinct codevectors (and hence the tree) grows by a sequence of bifurcations in the process, which occur as solutions of a free energy minimization. Their method obtains performance gains over growing and pruning methods for variable rate quantization of Gauss-Markov and Gaussian mixture sources.>

The deterministic annealing algorithm for data clustering is extended to address the trellis quantizer design problem. The approach is derived within information theory and probability theory, using the principle of maximum entropy to induce a distribution over all possible path encodings of the training set. The resulting method is intimately connected to estimation procedures on Markov chains. Performance gains over known methods are obtained for memoryless, multimodal scalar sources as well as for the vector Gaussian and Laplacian sources. The method is also suggested for an estimation problem in hidden Markov models. For a Gaussian mixture state example, this approach achieves a greater likelihood value than the best result of standard Baum-Welch re-estimation, based on numerous initializations within the data.>

The authors present a new approach to combined source-channel vector quantization. The method, derived within information theory and probability theory, utilizes deterministic annealing to avoid some local minima that trap conventional descent algorithms such as the generalized Lloyd algorithm. The resulting vector quantizers satisfy the necessary conditions for local optimality for the noisy channel case. They tested the method against several versions of the noisy channel generalized Lloyd algorithm on stationary, first order Gauss-Markov sources with a binary symmetric channel. The method outperformed other methods under all test conditions, with the gains over noisy channel GLA growing with the codebook size. The quantizers designed using deterministic annealing are also shown to behave robustly under channel mismatch conditions. As a comparison with a separate source-channel system, over a large range of test channel conditions, the method outperformed a bandwidth-equivalent system incorporating a Hamming code. Also, for severe channel conditions, the method produces solutions with explicit error control coding.>

A new structure permits improved solutions which approximate the exhaustive-search multistage solution. A deterministic annealing design method capitalizing on this structure is formulated within the framework of information theory. The sequential search constraint is included as a prior, and the principal of minimum cross entropy is invoked. The method obtains improvement over both the standard sequential design and joint optimization approaches.>

A new approach to the combined source-channel vector quantizer design problem is presented. The method utilizes deterministic annealing to avoid local minima that trap conventional descent algorithms. The temperature is used to control the fuzziness of the encoder and decoder association probabilities. In the low temperature limit, the method reduces to a descent method that is an analog of the generalized Lloyd algorithm (GLA) for noisy channels. Thus, in this sense, it is a generalization of noisy channel GLA (NC-GLA). Simulations were performed in order to compare the approach with several versions of NC-GLA. The method outperformed the other methods under all test conditions. Moreover, the gains over other methods grow with the codebook size.>