In this paper, we present a method for constructing a feature-engineered random forest by transforming the features of a given data set using a set of diverse and randomized transforms. The transformed features are then used for creating splits at each node of a random forest. In particular, we use sum-product features because of their strong expressive power. This type of on-the-fly feature engineering has significant advantages over traditional random forests because it adds to the diversity of the splits. Such a diversity further helps in variance reduction; over and above the variance reduction ability offered by traditional random forests. We show the advantages of the proposed approach over traditional random forests and other well-established baselines using extensive experimental evaluation.

Feature engineering is a crucial step in the process of predictive modeling. It involves the transformation of given feature space, typically using mathematical functions, with the objective of reducing the modeling error for a given target. However, there is no well-defined basis for performing effective feature engineering. It involves domain knowledge, intuition, and most of all, a lengthy process of trial and error. The human attention involved in overseeing this process significantly influences the cost of model generation. We present a new framework to automate feature engineering. It is based on performance driven exploration of a transformation graph, which systematically and compactly captures the space of given options. A highly efficient exploration strategy is derived through reinforcement learning on past examples.

We present DATASET EVOLVER, an interactive Jupyter notebook-based tool to support data scientists perform feature engineering for classification tasks. It provides users with suggestions on new features to construct, based on automated feature engineering algorithms. Users can navigate the given choices in different ways, validate the impact, and selectively accept the suggestions. DATASET EVOLVER is a pluggable feature engineering framework where several exploration strategies could be added. It currently includes meta-learning based exploration and reinforcement learning based exploration. The suggested features are constructed using well-defined mathematical functions and are easily interpretable. Our system provides a mixed-initiative system of a user being assisted by an automated agent to efficiently and effectively solve the complex problem of feature engineering. It reduces the effort of a data scientist from hours to minutes.

Feature engineering is the task of improving predictive modelling performance on a dataset by transforming its feature space. Existing approaches to automate this process rely on either transformed feature space exploration through evaluation-guided search, or explicit expansion of datasets with all transformed features followed by feature selection. Such approaches incur high computational costs in runtime and/or memory. We present a novel technique, called Learning Feature Engineering (LFE), for automating feature engineering in classification tasks. LFE is based on learning the effectiveness of applying a transformation (e.g., arithmetic or aggregate operators) on numerical features, from past feature engineering experiences. Given a new dataset, LFE recommends a set of useful transformations to be applied on features without relying on model evaluation or explicit feature expansion and selection. Using a collection of datasets, we train a set of neural networks, which aim at predicting the transformation that impacts classification performance positively. Our empirical results show that LFE outperforms other feature engineering approaches for an overwhelming majority (89%) of the datasets from various sources while incurring a substantially lower computational cost.

Outlier detection is the identification of points in a dataset that do not conform to the norm. Outlier detection is highly sensitive to the choice of the detection algorithm and the feature subspace used by the algorithm. Extracting domain-relevant insights from outliers needs systematic exploration of these choices since diverse outlier sets could lead to complementary insights. This challenge is especially acute in an interactive setting, where the choices must be explored in a time-constrained manner. In this work, we present REMIX, the first system to address the problem of outlier detection in an interactive setting. REMIX uses a novel mixed integer programming (MIP) formulation for automatically selecting and executing a diverse set of outlier detectors within a time limit. This formulation incorporates multiple aspects such as (i) an upper limit on the total execution time of detectors (ii) diversity in the space of algorithms and features, and (iii) meta-learning for evaluating the cost and utility of detectors. REMIX provides two distinct ways for the analyst to consume its results: (i) a partitioning of the detectors explored by REMIX into perspectives through low-rank non-negative matrix factorization; each perspective can be easily visualized as an intuitive heatmap of experiments versus outliers, and (ii) an ensembled set of outliers which combines outlier scores from all detectors. We demonstrate the benefits of REMIX through extensive empirical validation on real-world data.

Diabetes is a serious disease affecting a large number of people. Although there is no cure for diabetes, it can be managed. Especially, with advances in sensor technology, lots of data may lead to the improvement of diabetes management, if properly mined. However, there usually exists noise or errors in the observed behavioral data which poses challenges in extracting meaningful knowledge. To overcome this challenge, we learn the latent state which represents the patient's condition. Such states should be inferred from the behavioral data but unknown a priori. In this paper, we propose a novel framework to capture the trajectory of latent states for patients from behavioral data while exploiting their demographic differences and similarities to other patients. We conduct a hypothesis test to illustrate the importance of the demographic data in diabetes management, and validate that each behavioral feature follows an exponential or a Gaussian distribution. Integrating these aspects, we use a Demographic feature restricted hidden Markov model (DfrHMM) to estimate the trajectory of latent states by integrating the demographic and behavioral data. In DfrHMM, the latent state is mainly determined by the previous state and the demographic features in a nonlinear way. Markov Chain Monte Carlo techniques are used for model parameter estimation. Experiments on synthetic and real datasets show that DfrHMM is effective in diabetes management.

In this paper, we introduce autoencoder ensembles for unsupervised outlier detection. One problem with neural networks is that they are sensitive to noise and often require large data sets to work robustly, while increasing data size makes them slow. As a result, there are only a few existing works in the literature on the use of neural networks in outlier detection. This paper shows that neural networks can be a very competitive technique to other existing methods. The basic idea is to randomly vary on the connectivity architecture of the autoencoder to obtain significantly better performance. Furthermore, we combine this technique with an adaptive sampling method to make our approach more efficient and effective. Experimental results comparing the proposed approach with state-of-the-art detectors are presented on several benchmark data sets showing the accuracy of our approach.

The detection of malicious behavior, that is, judging if a host/domain is malicious or benign (i.e., negative or positive labels), is complicated by the issue of imbalanced label distributions, as well as the limited amount of ground truth available to train supervised models or build rules. To tackle these challenges, we propose a novel framework to learn cost-sensitive models on both network hosts and external domains simultaneously, based on a bipartite connectivity graph constructed between them. We also explicitly incorporate behavioral features of the hosts computed from the network data as well as lexical and reputational features computed for the external domains into the proposed framework. Specifically, we model the predicted labels, measure the misclassification errors by the Hamming distance between the predicted and true labels, incorporate different costs for different misclassification types (i.e., false negative or false positive), and constrain connected nodes to share the same labels in high probability. The proposed framework is then formulated as an optimization problem, which minimizes the total cost, that is, the misclassification costs multiplied by the misclassification errors. As the Hamming distance function is non-differentiable, we introduce a continuous loss function to approximate it with performance guaranteed. We develop an effective algorithm with good convergence property via Stochastic Gradient Descent technique. Experimental results on both synthetic and a real network dataset collected from an enterprise demonstrate the effectiveness of the proposed framework.

Data augmentation is the process of generating samples by transforming training data, with the target of improving the accuracy and robustness of classifiers. In this paper, we propose a new automatic and adaptive algorithm for choosing the transformations of the samples used in data augmentation. Specifically, for each sample, our main idea is to seek a small transformation that yields maximal classification loss on the transformed sample. We employ a trust-region optimization strategy, which consists of solving a sequence of linear programs. Our data augmentation scheme is then integrated into a Stochastic Gradient Descent algorithm for training deep neural networks. We perform experiments on two datasets, and show that that the proposed scheme outperforms random data augmentation algorithms in terms of accuracy and robustness, while yielding comparable or superior results with respect to existing selective sampling approaches.

Graphs or networks provide a powerful abstraction to view and analyze relationships among different entities present in a dataset. However, much of the data of interest to analysts and data scientists resides in non-graph forms such as relational databases, JSON, XML, CSV and text. The effort and skill required in identifying and extracting the relevant graph representation from data is often the prohibitive and limits a wider adoption of graph-based analysis of non-graph data. In this paper, we demonstrate our system calledGraphViewer, for accelerated graph-based exploration and analysis. It automatically discovers relevant graphs implicit within a given non-graph dataset using a set of novel rule-based and data-driven techniques, and optimizes their extraction and storage. It computes several node and graph level metrics and detects anomalous entities in data. Finally, it summarizes the results to support interpretation by a human analyst. While the system automates the computationally intensive aspects of the process, it is engineered to leverage human domain expertise and instincts to fine tune the data exploration process.

We consider a budgeted variant of the problem of learning from expert advice with N experts. Each queried expert incurs a cost and there is a given budget B on the total cost of experts that can be queried in any prediction round. We provide an online learning algorithm for this setting with regret after T prediction rounds bounded by O(sqrt(C log(N)T/B)), where C is the total cost of all experts. We complement this upper bound with a nearly matching lower bound Omega(sqrt(CT/B)) on the regret of any algorithm for this problem. We also provide experimental validation of our algorithm.

A Data Scientist typically performs a number of tedious and time-consuming steps to derive insight from a raw data set. The process usually starts with data ingestion, cleaning, and transformation (e.g. outlier removal, missing value imputation), then proceeds to model building, and finally a presentation of predictions that align with the end-users objectives and preferences. It is a long, complex, and sometimes artful process requiring substantial time and effort, especially because of the combinatorial explosion in choices of algorithms (and platforms), their parameters, and their compositions. Tools that can help automate steps in this process have the potential to accelerate the time-to-delivery of useful results, expand the reach of data science to non-experts, and offer a more systematic exploration of the available options. This work presents a step towards this goal.

An important problem in large-scale sensor mining is that of selecting relevant sensors for prediction purposes. Selecting small subsets of sensors, also referred to as active sensors, often leads to lower operational costs, and it reduces the noise and information overload for prediction. Existing sensor selection and prediction models either select a set of sensors a priori, or they use adaptive algorithms to determine the most relevant sensors for prediction. Sensor data sets often show dynamically varying patterns, because of which it is suboptimal to select a fixed subset of active sensors. To address this problem, we develop a novel dynamic prediction model that uses the notion of hidden system states to dynamically select a varying subset of sensors. These hidden system states are automatically learned by our model in a data-driven manner. The proposed algorithm can rapidly switch between different sets of active sensors when the model detects the (periodic or intermittent) change in the system state. We derive the dynamic sensor selection strategy by minimizing the error rates in tracking and predicting sensor readings over time. We introduce the notion of state-stacked sparseness to select a subset of the most critical sensors as a function of evolving system state. We present experimental results on two real sensor datasets, corresponding to oil drilling rig sensors and intensive care unit (ICU) sensors, and demonstrate the superiority of our approach with respect to other models.

A vast ocean of data is collected every day, and numerous applications call for the extraction of actionable insights from data. One important task is to detect untrustworthy information because such information usually indicates critical, unusual, or suspicious activities. In this paper, we study the important problem of detecting untrustworthy information from a novel perspective of correlating and comparing multiple sources that describe the same set of items. Different from existing work, we recognize the importance of time dimension in modeling the commonalities among multiple sources. We represent dynamic multi-source data as tensors and develop a joint non-negative tensor factorization approach to capture the common patterns across sources. We then conduct a comparison between source input and common patterns to identify inconsistencies as an indicator of untrustworthiness. An incremental factorization approach is developed to improve the computational efficiency on dynamically arriving data. We also propose a method to handle data sparseness. Experiments are conducted on hotel rating, network traffic flow, and weather forecast data that are collected from multiple sources. Results demonstrate the advantages of the proposed approach in detecting inconsistent and untrustworthy information.

Exploratory data analysis (EDA) is the process of discovering im-portant characteristics of a dataset or finding data-driven insights in the corresponding domain. EDA is a human intensive process involving data management, analytic flow deployment and model creation, and data visualization and interpretation. It involves ex-tensive use of analyst time, effort, and skill in data processing as well as domain expertise. In this paper, we introduce READ, a mixed initiative system for accelerating exploratory data analysis. The key idea behind READ is to decompose the exploration pro-cess into components that can be independently specified and auto-mated. These components can be defined, reused or extended using simple choice points that are expressed using inference rules, plan-ning logic, and reactive user interfaces and visualization. READ uses a formal specification of the analytic process for automated model space enumeration, workflow composition, deployment, and model validation and clustering. READ aims to reduce the time re-quired for exploration and understanding of a dataset from days to minutes. 1.

In data mining applications such as crowdsourcing and privacy-preserving data mining, one may wish to obtain consolidated predictions out of multiple models without access to features of the data. Besides, multiple models usually carry complementary predictive information, model combination can potentially provide more robust and accurate predictions by correcting independent errors from individual models. Various methods have been proposed to combine predictions such that the final predictions are maximally agreed upon by multiple base models. Though this maximum consensus principle has been shown to be successful, simply maximizing consensus can lead to less discriminative predictions and overfit the inevitable noise due to imperfect base models. We argue that proper regularization for model combination approaches is needed to alleviate such overfitting effect. Specifically, we analyze the hypothesis spaces of several model combination methods and identify the trade-off between model consensus and generalization ability. We propose a novel model called Regularized Consensus Maximization (RCM), which is formulated as an optimization problem to combine the maximum consensus and large margin principles. We theoretically show that RCM has a smaller upper bound on generalization error compared to the version without regularization. Experiments show that the proposed algorithm outperforms a wide spectrum of state-of-the-art model combination methods on 11 tasks.

We investigate the DHCP churn impact on network characterization by analyzing 18 months of DHCP, DNS, Firewall Alert, and Netflow data collected from an enterprise network of 30,000 clients. We find that DHCP churn has clear impact on network metrics.

This work rigorously explores the design of cluster-preserving compression schemes for high-dimensional data. We focus on the K-means algorithm and identify conditions under which running the algorithm on the compressed data yields the same clustering outcome as on the original. The compression is performed using single and multi-bit minimum mean square error quantization schemes as well as a given clustering assignment of the original data. We provide theoretical guarantees on post-quantization cluster preservation under certain conditions on the cluster structure, and propose an additional data transformation that can ensure cluster preservation unconditionally; this transformation is invertible and thus induces virtually no distortion on the compressed data. In addition, we provide an efficient scheme for multi-bit allocation, per cluster and data dimension, which enables a trade-off between high compression efficiency and low data distortion. Our experimental studies highlight that the suggested scheme accurately preserved the clusters formed in all cases, while incurring minimal distortion on the data shapes. Our results can find many applications, e.g., in a) clustering, analysis and distribution of massive datasets, where the proposed data compression can boost performance while providing provable guarantees on the clustering result, as well as, in b) cloud computing services, as the optional transformation provides a data-hiding functionality in addition to preserving the K-means clustering outcome.

In this paper, we propose to conduct anomaly detection across multiple sources to identify objects that have inconsistent behavior across these sources. We assume that a set of objects can be described from various perspectives (multiple information sources). The underlying clustering structure of normal objects is usually shared by multiple sources. However, anomalous objects belong to different clusters when considering different aspects. For example, there exist movies that are expected to be liked by kids by genre, but are liked by grown-ups based on user viewing history. To identify such objects, we propose to compute the distance between different eigen decomposition results of the same object with respect to different sources as its anomalous score. We also give interpretations from the perspectives of constrained spectral clustering and random walks over graph. Experimental results on several UCI as well as DBLP and Movie Lens datasets demonstrate the effectiveness of the proposed approach.

Network operators are continuously confronted with malicious events, such as port scans, denial-of-service attacks, and spreading of worms. Due to the detrimental effects caused by these anomalies, it is critical to detect them promptly and effectively. There have been numerous softwares, algorithms, or rules developed to conduct anomaly detection over traffic data. However, each of them only has limited descriptions of the anomalies, and thus suffers from high false positive/false negative rates. In contrast, the combination of multiple atomic detectors can provide a more powerful anomaly capturing capability when the base detectors complement each other. In this paper, we propose to infer a discriminative model by reaching consensus among multiple atomic anomaly detectors in an unsupervised manner when there are very few or even no known anomalous events for training. The proposed algorithm produces a perevent based non-trivial weighted combination of the atomic detectors by iteratively maximizing the probabilistic consensus among the output of the base detectors applied to different traffic records. The resulting model is different and not obtainable using Bayesian model averaging or weighted voting. Through experimental results on three network anomaly detection datasets, we show that the combined detector improves over the base detectors by 10% to 20% in accuracy.

Multimedia stream mining applications require the identification of several different attributes in data content, and hence rely on a set of cascaded statistical classifiers to filter and process the data dynamically. In this paper, we introduce a novel methodology for configuring such cascaded classifier topologies, specifically binary classifier trees, in resource-constrained, distributed stream mining systems. Instead of traditional load shedding, our approach configures classifiers with optimized operating points after jointly considering the misclassification cost of each end-to-end class of interest in the tree, the resource constraints for every classifier, and the confidence level of each data object that is classified. The proposed approach allows for both intelligent load shedding as well as data replication based on available resources dynamically. We evaluate the algorithm on a sports video concept detection application and identify huge cost savings over load shedding alone. Additionally, we propose several distributed algorithms that enable each classifier in the tree to reconfigure itself based on local information exchange. We analyze the associated tradeoffs between convergence time, information overhead, and the cost efficiency of results achieved by each classifier for each of these algorithms.

The emergence of large-field radio telescopes has generated the need to process huge amounts of data “on the fly” in order to avoid substantial costs in storage and signal processing. In this paper, we describe a streaming software approach to radio astronomy, and in particular, show how the IBM-developed stream computing architecture System S enables seamless “on the fly” radio astronomy imaging. This approach overcomes pertinent issues of memory limitation and latencies related to data processing, and it allows autonomous processor allocation to tasks as the need arises.

With the rapid growth of stored and streaming multimedia, there is an increasing need for classifying, filtering and retrieving content possessing specific features/attributes of interest. Complex features in multimedia content can be scalably identified by deploying networks of binary classifiers across distributed processing infrastructures. In this paper, we focus on building optimal topologies (chains) of networked classifiers, and present algorithms for classifier ordering and configuration, to tradeoff accuracy of the feature identification versus the incurred filtering delay. We reduce the problem of classifier topology construction to the pipeline-ordering problem, and design a solution that orders classifiers based on the underlying data characteristics, system resource constraints as well as the performance and complexity characteristics of each classifier. We also determine utility bounds on the performance of this algorithm. We then extend the algorithm to dynamically configure individual classifiers jointly with the topology construction.

In this tutorial, we will present the fundamental principles of large-scale adaptive multimedia stream mining, describe state-of-the-art in terms of systems and algorithms, and include recent theoretical and experimental results. We will also discuss how we can construct different cooperative and non-cooperative games to model, analyze, optimize, and shape these applications in different system or connectivity scenarios and under various constraints.

Abstract Stream processing applications are used to ingest, process, and analyze continuous data streams from heterogeneous sources of live and stored data, generating streams of output results. These applications are, in many cases, complex, large‐scale, low‐latency, and distributed in nature. In this paper, we describe the design principles and architectural underpinnings for stream processing applications. These principles are distilled from our experience in building real‐world applications both for internal use as well as with customers from several industrial and academic domains. We provide principles, guidelines, as well as appropriate implementation examples to highlight the different aspects of stream processing application design and development. Copyright © 2010 John Wiley & Sons, Ltd.

We consider the problem of estimating the direction of arrival (DOA) of multiple waves incident on a single tripole sensor. Using the physical properties of the electric and magnetic fields, we show that we can disambiguate the DOA of multiple simultaneously incident waves using a set of time sampled 3D measurements from the single sensor. This is different from the traditional approach that uses arrays of antennas to estimate DOA. We use the unitary matrix pencil method to estimate the frequencies of the waves, and use a least squares solver to estimate the amplitude and phase coefficients. We combine these to compute the DOA and evaluate the approach using simulations. We show that the method is very effective at estimating DOA for different numbers of incident waves, and different noise levels.

In this paper, we propose a distributed solution to the problem of configuring classifier trees in distributed stream mining systems. The configuration involves selecting appropriate false-alarm detection tradeoffs for each classifier to minimize end-to-end penalty in terms of misclassification cost. In the proposed solution, individual classifiers select their operating points (i.e., actions) to maximize a local utility function. The utility may be purely local to the current classifier, corresponding to a myopic strategy, or may include the impact of the classifier actions on successive classifiers in the tree, corresponding to a foresighted strategy. We analytically show that actions determined by the foresighted strategies can improve the end-to-end performance of the classifier tree and derive an associated probability bound. We then evaluate our solutions on an application for hierarchical sports scene classification. By comparing centralized, myopic and foresighted solutions, we show that foresighted strategies result in better performance than myopic strategies, and also asymptotically approach the centralized optimal solution.

We consider the problem of configuring classifier trees in distributed stream mining system. The configuration involves selecting appropriate false-alarm detection tradeoffs for each classifier to minimize end-to-end penalty in terms of misclassification cost. We model this as a tree configuration game and design solutions, where individual classifiers select their operating points to maximize a local utility. We derive appropriate misclassification cost coefficients for intermediate classifiers, and determine the information that needs to be exchanged across classifiers, in order to successfully design the game. We analytically show that there is a unique pure strategy Nash equilibrium in operating points, which guarantees a convergence of the proposed approach. We evaluate the performance of our algorithm on an application for sports scene classification, and compare against centralized solutions. We show that our algorithm results in better performance than the centralized solution on average. Moreover, the algorithm approaches the optimal solution asymptotically with increasing number of actions per classifier.

This work examines under what conditions compression methodologies can retain the outcome of clustering operations. We focus on the popular k-means clustering algorithm and we demonstrate how a properly constructed compression scheme based on post-clustering quantization is capable of maintaining the global cluster structure. Our analytical derivations indicate that a 1-bit moment preserving quantizer per cluster is sufficient to retain the original data clusters. Merits of the proposed compression technique include: a) reduced storage requirements with clustering guarantees, b) data privacy on the original values, and c) shape preservation for data visualization purposes. We evaluate quantization scheme on various high-dimensional datasets, including 1-dimensional and 2-dimensional time-series (shape datasets) and demonstrate the cluster preservation property. We also compare with previously proposed simplification techniques in the time-series area and show significant improvements both on the clustering and shape preservation of the compressed datasets.

We propose a new approach for resource-adaptive semantic concept detection on image streams. We build concept detectors using an ensemble learning method called random subspace bagging, and deploy them on a set of distributed processing nodes. We focus on the optimal placement of ensemble classifiers across nodes, and selection of the number of base models for each classifier, to maximize classification performance while adapting to resource constraints. Based on a utility metric defined in terms of misclassification probabilities, we formulate this resource adaptation problem using two approaches. The first corresponds to a Multiple-Choice-Multiple-Knapsack problem solved by integer programming, while the second involves formulation as a load-balancing problem solved by linear programming. The performance of these approaches is evaluated on an application that detects 10 semantic concepts on real image streams. We show that the load-balancing approach outperforms the knapsack approach, with over 60% reduction in misclassification penalty under tight resource constraints.

Large-scale multimedia semantic concept detection requires realtime identification of a set of concepts in streaming video or large image datasets. The potentially high data volumes of multimedia content, and high complexity associated with individual concept detectors, have hindered the practical deployment of many current solutions. In this paper, we present a summary of our work in building systems and applications for resource adaptive semantic concept detection in multimedia using large-scale distributed stream mining systems. We construct such concept detection applications as a hierarchical topology of individual concept detectors, and deploy them on distributed processing infrastructure. We then focus on dynamically configuring individual concept detectors to meet system imposed resource constraints while minimizing a penalty defined in terms of the misclassification cost. We present multiple centralized and distributed algorithms for this configuration, and describe the implemented application and system. We also verify through simulations that significant improvement in terms of accuracy of classification can be achieved through our approach.

When labeled examples are limited and difficult to obtain, transfer learning employs knowledge from a source domain to improve learning accuracy in the target domain. However, the assumption made by existing approaches, that the marginal and conditional probabilities are directly related between source and target domains, has limited applicability in either the original space or its linear transformations. To solve this problem, we propose an adaptive kernel approach that maps the marginal distribution of targetdomain and source-domain data into a common kernel space, and utilize a sample selection strategy to draw conditional probabilities between the two domains closer. We formally show that under the kernel-mapping space, the difference in distributions between the two domains is bounded; and the prediction error of the proposed approach can also be bounded. Experimental results demonstrate that the proposed method outperforms both traditional inductive classifiers and the state-of-the-art boosting-based transfer algorithms on most domains, including text categorization and web page ratings. In particular, it can achieve around 10 % higher accuracy than other approaches for the text categorization problem. The source code and datasets are available from the authors.

We introduce Zen, a new resource allocation framework that assigns application components to node clusters to achieve high availability for partial-fault tolerant (PFT) applications. These applications have the characteristic that under partial failures, they can still produce useful output though the output quality may be reduced. Thus, the primary goal of resource allocation for PFT applications is to prevent, delay, or minimize the impact of failures on the application output quality. This paper is the first to approach this resource allocation problem from a theoretical perspective, and obtains a series of results regarding component assignments that provide the highest service availability under the constraints imposed by the application data flow graph and the hosting clusters. We show that (1) even simple versions of this resource allocation problem are NP-Hard, (2) a 2-approximate polynomial-time algorithm works for tree topologies, and (3) a simple greedy component placement performs well in practice for general application topologies. We implement a system prototype to study the application availability achieved by Zen compared to failure-oblivious placement, replication, and Zen+replication. Our experimental results show that three PFT applications achieve significant data output quality and availability benefits using Zen.

Real-time multimedia semantic concept detection requires instant identification of a set of concepts in streaming video or images. However, the potentially high data volumes of multimedia content, and high complexity associated with individual concept detectors, have hindered its practical deployment. In this paper, we present a new online concept detection system deployed on top of a distributed stream mining system. It uses a tree-topology of classifiers that are constructed on a semantic hierarchy of concepts of interest. We introduce a novel methodology for configuring such cascaded classifier topologies under constraints on the available resources. In our approach, we configure individual classifiers with optimized operating points after jointly and explicitly considering the misclassification cost of each end-to-end class of interest in the tree, the system imposed resource constraints, and the confidence level of each object that is classified. We describe the implemented application, system, and optimization algorithms, and verify that significant improvement in terms of accuracy of classification can be achieved through our approach.

Stream mining applications require the identification of several different attributes in data content and hence rely on a distributed set of cascaded statistical classifiers to filter and process the data dynamically. In this letter, we introduce a novel methodology for configuring cascaded classifier topologies, specifically binary classifier trees, with optimized operating points after jointly considering the misclassification cost of each end-to-end class of interest in the tree, the resource constraints for every classifier, and the confidence level of each data object that is classified. By configuring multiple operating points per classifier, we enable not only intelligent load shedding when resources are scarce but also intelligent replication of low confidence data across multiple edges when excess resources are available. Using a classifier tree constructed from support vector machine-based sports image classifiers, we verify huge cost savings and discuss how different classifier placements and costs can influence the gains obtained by various algorithms.

Available resources in peer-to-peer (P2P) systems depend strongly on resource contributions made by individual peers. Empirical data shows that in the absence of incentives, a majority of the participating peers do not contribute resources. Modeling interactions between individual peers is often difficult as the number of peers in the system can be very large, and the relationships among them can be very complex. In this paper, we propose a new solution for P2P systems, where peers upload and download content to and from the contributing peers based on agreed-upon/determined sharing rates. We propose a P2P solution that deters free-riders by imposing constraints on participating peers; specifically, a peer is allowed access to new content only as long as its own content contribution exceeds an adaptively set threshold. The constraints are enforced either by a central authority (e.g., a tracker) or by a decentralized coalition of peers in a swarm, social network, etc. We derive optimal upload policies for the peers given their estimated future download requirements and their previous contribution (credit) to the other peers. Our results show considerable improvement in the cost-benefit tradeoff for peers that deploy such an optimal policy as compared to heuristic upload policies. We also propose mechanisms based on which the coalition of peers can provide incentives or penalties to participating peers to adjust their policies such that the availability of content and/or number of peers contributing content is maximized.

We design algorithms for optimally configuring, in terms of model complexity as well as operating point, a cascade of exclusive classifiers on distributed systems, given underlying resource constraints. Under rate-dependent constraints we design a Viterbi-like strategy to determine the optimal solution with significantly lower computational complexity than an exhaustive search. We illustrate the performance of this strategy on a cascade of classifiers for a speaker verification task, and highlight performance gains over using a single classifier.

Peer-to-peer collaboration paradigms fundamentally change the passive way wireless stations currently adapt their transmission strategies to match available resources, by enabling them to proactively influence system dynamics through exchange of information and resources. In this paper, we focus on delay-sensitive multimedia transmission among multiple peers over wireless multi-hop enterprise mesh networks. We propose a distributed and efficient framework for resource exchanges that enables peers to collaboratively distribute available wireless resources among themselves based on their quality of service requirements, the underlying channel conditions, and network topology. The resource exchanges are enabled by the scalable coding of the video content and the design of cross-layer optimization strategies, which allow efficient adaptation to varying channel conditions and available resources. We compare our designed low complexity distributed resource exchange algorithms against an optimal centralized resource management scheme and show how their performance varies with the level of collaboration among the peers. We measure system utility in terms of the multimedia quality and show that collaborative approaches achieve ~50% improvement over non-collaborative approaches. Additionally, our distributed algorithms perform within 10% system utility of a centralized optimal resource management scheme. Finally, we observe 2-5 dB improvement in decoded PSNR for each peer due to the deployed cross-layer strategy

Existing wireless networks provide dynamically varying resources with only limited support for the quality of service required by the bandwidth-intense, loss-tolerant and delay-sensitive multimedia applications. This variability of resources does not significantly impact delay insensitive data transmission (e.g., file transfers), but has considerable consequences for multimedia applications. Recently, the research focus has been to adapt existing algorithms and protocols at the lower layers of the protocol stack to better support multimedia transmission applications and conversely, to modify application layer solutions to cope with the varying wireless networks resources. In this paper, we show that significant improvements in wireless multimedia performance can be obtained by deploying a joint application-layer adaptive packetization and prioritized scheduling and MAC-layer retransmission strategy. We deploy a state-of-the-art wavelet coder for the compression of the video data that enables on-the-fly adaptation to changing channel conditions and inherent prioritization of the video bitstream. We pose the cross-layer problem as a distortion minimization given delay constraints and derive analytical solutions by modifying existing joint source-channel coding theory aimed at fulfilling rate, rather than delay, constraints. We also propose real-time algorithms that explicitly consider the available information about previously transmitted packets. The obtained results show significant improvements in terms of video quality as opposed to ad-hoc optimizations currently deployed, while the complexity associated with performing this optimization in real time, i.e., at transmission time, is limited

We develop algorithms to provide Quality of Service (QoS) support for prioritized, bandwidth-adaptive and fair media streaming using a multimedia server cluster. We formulate the underlying related problems of prioritized client admission control, redirection to appropriate streaming server, adaptive client quality control, and server load-balancing as one combined optimization. This optimization corresponds to solving a Multiple Choice Multiple Knapsack Problem, which is in general NP hard. By partitioning this optimization into two separate related optimizations we can design several low- complexity algorithms to provide exact and approximate solutions. We select a log-linear utility function that maintains differentiability and captures the video quality to measure the derived client and system benefit. We provide bounds on the performance of these algorithms, and examine the system time evolution in terms of the number of clients supported and QoS provided to each client, over realistic simulation scenarios.

State-of-the-art speaker verification systems are built around the likelihood ratio test, using Gaussian mixture models (GMM) for likelihood functions, a universal background model (UBM) for alternative speaker representation, and a form of Bayesian adaptation to derive speaker models from the UBM. This work tackles optimal quantizer design of the speech cepstral features (MFCCs) for such systems. The problem is posed as the minimization of loss of log-likelihood ratio between the quantized and unquantized speech features. First we show that the conventional mean squared error (MSE) quantizer for the top-scoring UBM Gaussian is optimal under practical assumptions. Then we derive the optimal bit allocation strategy across the dimensions of the feature vectors. Finally we demonstrate the validity of the approach against various quantization and bit allocation schemes by running experiments on the appropriately modified IBM speaker verification system. Experimental results on the HUB4 corpora show negligible impact on verification performance for bit rates as low as less than 1 bit per dimension on average in contrast to 32 bits per dimension in the original system

We introduce a CPU-adaptive algorithm for spectrum estimation on streaming data. Our approach combines a fast and intelligent load-shedding scheme with a closed form incremental spectrum computation, which adapts gracefully to the available computational resources.

Networks of classifiers are capturing the attention of system and algorithmic researchers because they offer improved accuracy over single model classifiers, can be distributed over a network of servers for improved scalability, and can be adapted to available system resources. This work provides a principled approach for the optimized allocation of system resources across a networked chain of classifiers. We begin with an illustrative example of how complex classification tasks can be decomposed into a network of binary classifiers. We formally define a global performance metric by recursively collapsing the chain of classifiers into one combined classifier. The performance metric trades off the end-to-end probabilities of detection and false alarm, both of which depend on the resources allocated to each individual classifier. We formulate the optimization problem and present optimal resource allocation results for both simulated and state-of-the-art classifier chains operating on telephony data.

In this paper, we consider the problem of real-time multimedia transmission among several peers (users). The peers use a heterogeneous wireless multi-hop mesh network for the delivery of these high-bandwidth streams. One of the main challenges of the considered problem is the division of the scarce wireless resources among the various peers. To address this problem, we propose an efficient, distributed and collaborative framework for wireless resource exchanges that enables peers to divide available wireless resources among themselves based on their quality of service (QoS) requirements, the underlying channel conditions and network topology. The scalable coding of the video content and decomposition of video flows into various sub-flows (priorities) allow peers to transfer the video at different quality levels, depending on the network load. Users collaboratively decide which of their sub-flows to admit, and which paths these sub-flows should be transmitted on in order to maximize a system defined utility. Our results show that with user collaboration, these distributed algorithms provide system and user performance comparable to a centralized exhaustive implementation.

Joint optimization strategies across various layers of the protocol stack have recently been proposed for improving the performance of real-time video transmission over wireless networks. In this paper, we propose a new, low complexity system for determining the optimal cross-layer strategies for wireless multimedia transmission based on classification and machine learning techniques. We first determine offline the optimal cross-layer strategy for various video sequences and channel conditions (training data). Subsequently, we extract relevant and easy to compute content features, encoder-specific parameters, and channel resources from the training data, and train a statistical classifier based on these optimal results. At run-time, we predict using the classifier the optimal cross-layer compression and transmission strategy using these simple, on-the-fly computed features. Hence, we consider the complex problem of finding the optimal cross-layer strategy during the training phase only, and rely at transmission-time on low-complexity classification techniques. We illustrate the proposed classification-based system by performing MAC-application layer optimizations for video transmission over 802.11a wireless LANs. Specifically, we predict the optimal MAC retry limits for the various video packets and compare our results against both optimal and conventionally used ad-hoc cross-layer solutions. Our results indicate that considerable improvements can be obtained through the proposed cross-layer techniques relying on classification as opposed to optimized ad-hoc solutions. The improvements are especially important at high packet-loss rates (5% and higher), where deploying a judicious mixture of strategies at the various layers becomes essential. Furthermore, our proposed classification-based system can be easily modified to include other layers from the OSI stack during the cross-layer optimization

The concepts and techniques that have dominated wired multimedia communications are not well suited for dynamic wireless environments. In recent years, research focus has been to adapt existing algorithms and protocols to the rapidly varying resources of wireless networks. For instance, packetization strategies are solely designed based on application layer information. While this design provides adequate support for multimedia applications over the Internet, it results often in poor performance in crowded wireless networks, when the interference is high or when the stations are mobile. In this paper, we show that by deploying a cross-layer aware packetization strategy, which explicitly considers the deployed compression techniques and content characteristics at the application layer as well as the protection methods at the lower layers for different channel conditions, significant improvements in multimedia performance can be obtained.

In this paper we present multimedia adaptation strategies for live video streams, at the streaming server, where we switch among several versions of the coded multimedia to match the available network bandwidth accurately, and meet client delay constraints. We estimate information about the available network bandwidth, at the server, by monitoring the application buffer and then decide to adaptively switch up or switch down the transmitted bit-rate. We use a piecewise linear model for the network bandwidth to estimate the current and future server buffer drain delay, and derive the transmission rate to minimize client buffer starvation. We implement these strategies in an enterprise streaming system and verify the performance, in terms of the network fidelity and received video quality, using both real as well as simulated network traces.

This paper describes the enterprise multimedia streaming problem and highlights its requirements and specific issues. These issues are grouped into three broad areas: infrastructure, streaming and applications. This paper also presents an overview of current research in several diverse areas that is relevant to solutions for enterprise streaming, and highlight directions for further development. Thus, it is easy to generate interest in designing novel solutions and applications for enterprise streaming.

Cross protocol layer optimizations have been recently proposed for improving the performance of real-time video transmission over 802.11 WLANs. However, performing such cross-layer optimizations is difficult since the video data and channel characteristics are time-varying, and analytically deriving the relationships between quality and channel characteristics given delay and power constraints is difficult. Furthermore, these relationships are often non-linear and non-deterministic (only worst or average case values can be determined). Complex Lagrangian or multi-objective optimization problems are thus often faced. In this paper, we propose a novel framework for solving cross MAC-application layer optimization problems. More specifically, we employ classification techniques to find an optimized cross-layer strategy for wireless multimedia transmission. Our solution deploys both content- and channel-related features to select a joint application-MAC strategy from the different strategies available at the various layers. Preliminary results indicate that considerable improvements can be obtained through the proposed cross-layer techniques relying on classification as opposed to ad-hoc solutions. The improvements are especially important at high packet-loss rates (5% and higher), where deploying a judicious mixture of strategies at the various layers becomes essential.

We present a framework for the systematic analysis of video encoding complexity, measured in terms of the number of motion estimation (ME) computations, that we illustrate on motion compensated wavelet video coding schemes. We demonstrate the graceful complexity scalability of these schemes through the modification of the spatiotemporal decomposition structure and the ME parameters, and the use of spatiotemporal prediction. We generate a wide range of rate-distortion-complexity (R-D-C) operating points for different sequences, by modifying these options. Using our analytical framework we derive closed form expressions for the number of ME computations for these different coding modes and show that they accurately capture the computational complexity independent of the underlying content characteristics. Our framework for complexity analysis can be combined with rate-distortion modeling to determine the encoding structure and parameters for optimal R-D-C tradeoffs.

The paper presents a new framework for adaptive temporal filtering in wavelet interframe codecs, called unconstrained motion compensated temporal filtering (UMCTF). This framework allows flexible and efficient temporal filtering by combining the best features of motion compensation, used in predictive coding, with the advantages of interframe scalable wavelet video coding schemes. UMCTF provides higher coding efficiency, improved visual quality and flexibility of temporal and spatial scalability, higher coding efficiency and lower decoding delay than conventional MCTF schemes. Furthermore, UMCTF can also be employed in alternative open-loop scalable coding frameworks using DCT for the texture coding.

Unconstrained motion compensated temporal filtering (UMCTF) is a very general and flexible framework for temporal filtering. It allows the selection of many different filters as well as decomposition structures to allow easy adaptation to video content, bandwidth variations, complexity requirements, and in conjunction with embedded coding can provide spatio-temporal-SNR scalability. In this paper we demonstrate the content-adaptive filter selection provided within the UMCTF framework. We show improvements in coding efficiency as well as in decoded visual quality using content-adaptive filters, at different granularities.

Packet delay jitter and loss due to network congestion pose significant challenges for designing and deploying delay sensitive multimedia applications over the best effort packet switched networks such as the Internet. Recent studies indicate that using multiple descriptions coding (MDC) in conjunction with path or server diversity can mitigate these effects. However, the proposed MDC coding and streaming techniques are based on non-scalable coding techniques. A key disadvantages of these techniques is that they can only improve the error resilience of the transmitted video, but are not able to address two other important challenges associated with the robust transmission of video over unreliable networks: adaptation to bandwidth variations and receiving device characteristics. In this paper, we present a new paradigm, referred to as multiple description scalable coding (MDSC), that is able to address all the previously mentioned challenges by combining the advantages of scalable coding and MDC. This framework enables tradeoffs between throughput, redundancy and complexity at transmission time, unlike previous non-scalable MDC schemes. Furthermore, we also propose a novel MDSC scheme based on motion compensated temporal filtering (MCTF), denominated multiple description motion compensated temporal filtering (MD-MCTF). We use the inherent ability of current MCTF schemes, using the lifting implementation of temporal filtering. We show how tradeoffs between throughput, redundancy and complexity can easily be achieved by adaptively partitioning the video into several descriptions after MCTF. Based on our simulations using different network conditions, the proposed MD-MCTF framework outperforms existing MDC schemes over a variety of network conditions.

Motion compensated temporal filtering (MCTF) is used in wavelet video coding schemes to remove temporal redundancy. Current extensions to MCTF use bi-directional filtering and multiple reference frames to improve the coding performance significantly. However, these extensions lead to an additional cost of coding extra sets of motion vectors. In this paper we propose the use of temporal prediction to reduce the bits needed to code motion vectors. We describe several temporal prediction methods, and highlight the advantages of each scheme. We also use MV prediction during motion estimation, i.e. change the search center and the search range based on the temporal prediction, and describe the tradeoffs to be made between rate, distortion, and complexity. We perform several experiments to illustrate the gains of using temporal prediction, and identify the content dependent nature of such results.

This paper presents a new framework for adaptive temporal filtering in wavelet interframe codecs, called the unconstrained motion compensated temporal filtering (UMCTF). This framework allows flexible and efficient temporal filtering by combining the best features of motion compensation, used in predictive coding, with the advantages of interframe scalable wavelet video coding schemes. UMCTF provides higher coding efficiency, improved visual quality and flexibility of temporal and spatial scalability, higher coding efficiency and tower decoding delay than conventional MCTF schemes. Furthermore, UMCTF can also be employed in alternative open-loop scalable coding frameworks using DCT for the texture coding.

Unconstrained motion compensated temporal filtering (UMCTF) is a very general and flexible framework for temporal filtering. It allows the selection of many different filters as well as decomposition structures to allow easy adaptation to video content, bandwidth variations, complexity requirements, and in conjunction with embedded coding can provide spatio-temporal-SNR scalability. In this paper we demonstrate the content-adaptive filter selection provided within the UMCTF framework. We show improvements in coding efficiency as well as in decoded visual quality using content-adaptive filters, at different granularities.

Motion compensated wavelet (MC-Wavelet) video coding provides high coding efficiency and robustness along with spatio-temporal-SNR-complexity scalability. Such schemes use a multi-resolution motion compensated temporal filtering (MCTF) decomposition along with the spatial wavelet transform to remove video redundancy. These multi-resolution transforms partition the spatio-temporal sequence-volume into regions corresponding to desired spatial and temporal resolutions. In this paper, we present a novel method for reducing the motion estimation complexity in MC wavelet coders by selecting adaptively different spatio-temporal decomposition structures and temporal motion vector prediction schemes. We present results to highlight the reduction in encoder complexity.

We introduce an efficient statistical modeling technique called mixture of principal components (MPC). This model is a linear extension to the traditional principal component analysis (PCA) and uses a mixture of eigenspaces to capture data variations. We use the model to capture face appearance variations due to pose and lighting changes. We show that this more efficient modeling leads to improved face recognition performance.

Many user-end applications require an estimate of the quality of coded video or images without having access to the original, i.e. a no-reference quality metric. Furthermore, in many such applications, the compressed video bitstream is also not available. The paper describes methods for using the statistical properties of the coded video data to estimate the quantization error caused by compression without accessing either the original pictures or the bitstream. A commonly used quality metric, the peak signal-to-noise ratio (PSNR) is subsequently computed from the estimated quantization error. Since quantization error is the most significant loss incurred during typical coding schemes, the estimated PSNR, or any PSNR-based quality metric may be used to gauge the overall quality of the pictures.

We introduce model-based schemes for error concealment of networked video. We build appearance models for specific objects in the scene and use these models to replenish any lost information. Due to the models being designed specifically for the object, they are able to capture the statistical variations in the object appearance more effectively, thereby leading to better error-concealment performance. We examine statistical modeling techniques from the literature and introduce a new efficient and accurate linear model for data representation, called the mixture of principal components (MPC), and use these models for error concealment. We simulate lossy network conditions and show that these model-based concealment schemes outperform traditional concealment schemes across a variety of loss probabilities and bit rates for the coded video.

There are many mode decisions in the video coding process that are used to optimize the performance in terms of the bit rate, the speed and the quality of the decoded video. We describe a classification based scheme for making mode decisions in the video coding process. We then illustrate the performance of the scheme using I/P frame selection as an example. The performance of our scheme is measured in terms of both the bit rate and the computation complexity, across different kinds of sequences, and the results are very encouraging.

There are several parts of the video-encoding process that can be optimized for high quality, high compression ratio, and fast encoding speed. We focus on some of these encoder optimization issues. We first study motion estimation, a computationally intensive part of encoding, and propose efficient algorithms based on exploiting spatially correlated motion information. We extend our motion estimation algorithms to find motion vectors for sub-parts of a block, as allowed for in the H.263 and MPEG-4 standards, and propose an efficient two-tier decision strategy for the one-four motion-vector decision. We introduce a new measure of block similarity that can improve the inter-intra mode decision significantly. Furthermore, for certain motion-estimation strategies, this new measure can also improve the bit rate resulting from a better motion estimation. Another issue that we address is the estimation of delta motion vectors in the H.263 and MPEG-4 standards. We have implemented these optimizations in a H.263 framework and the results are encouraging.

A video encoder has to make many mode decisions in order to achieve the goal of a low bit rate, high quality, and fast implementation. We propose a general classification based approach to making such mode decisions accurately and efficiently. We first illustrate the approach using the Intra-Inter coding mode decision. We then focus on the decision to skip or code a frame for rate control of video over networks. Using the classification used approach we show improvement in the rate-distortion sense. We then extend the work to scalable video coding in choosing between scalability modes and examine the performance of our approach over error prone networks, using simulated packet losses.

We propose a simple two-state Markov modulated AR process to model the traffic created by a variable bit rate video coder. This model performs better than currently proposed models, especially for video coded with a variable group-of-pictures (GOP) structure.