Solving complex visual tasks such as “Who invented the musical instrument on the right?” involves a composition of skills: understanding space, recognizing instruments, and also retrieving prior knowledge. Recent work shows promise by decomposing such tasks using a large language model (LLM) into an executable program that invokes specialized vision models. However, generated programs are error-prone: they omit necessary steps, include spurious ones, and are unable to recover when the specialized models give incor-rect outputs. Moreover, they require loading multiple models, incurring high latency and computation costs. We propose Visual Program Distillation (VPD), an instruction tuning framework that produces a vision-language model (VLM) ca-pable of solving complex visual tasks with a single forward pass. VPD distills the reasoning ability of LLMs by using them to sample multiple candidate programs, which are then executed and verified to identify a correct one. It translates each correct program into a language description of the reasoning steps, which are then distilled into a VLM. Exten-sive experiments show that VPD improves the VLM's ability to count, understand spatial relations, and reason compositionally. Our VPD-trained PaLI-X outperforms all prior VLMs, achieving state-of-the-art performance across complex vision tasks, including MMBench, OK-VQA, A-OKVQA, TallyQA, POPE, and Hateful Memes. An evaluation with human annotators also confirms that VPD improves model response factuality and consistency. Finally, experiments on content moderation demonstrate that VPD is also helpful for adaptation to real-world applications with limited data.

The application of computer vision methods to nuanced, subjective concepts is growing. While crowdsourcing has served the vision community well for most objective tasks (such as labeling a "zebra"), it now falters on tasks where there is substantial subjectivity in the concept (such as identifying "gourmet tuna"). However, empowering any user to develop a classifier for their concept is technically difficult: users are neither machine learning experts nor have the patience to label thousands of examples. In reaction, we introduce the problem of Agile Modeling: the process of turning any subjective visual concept into a computer vision model through real-time user-in-the-loop interactions. We instantiate an Agile Modeling prototype for image classification and show through a user study (N=14) that users can create classifiers with minimal effort in under 30 minutes. We compare this user driven process with the traditional crowdsourcing paradigm and find that the crowd’s notion often differs from that of the user’s, especially as the concepts become more subjective. Finally, we scale our experiments with simulations of users training classifiers for ImageNet21k categories to further demonstrate the efficacy of the approach.

We present a new approach for graph based semi-supervised learning based on a multi-component extension to the Gaussian MRF model. This approach models the observations on the vertices as jointly Gaussian with an inverse covariance matrix that is a weighted linear combination of multiple matrices. Building on randomized matrix trace estimation and fast Laplacian solvers, we develop fast and efficient algorithms for computing the best-fit (maximum likelihood) model and the predicted labels using gradient descent. Our model is considerably simpler, with just tens of parameters, and a single hyperparameter, in contrast with state-of-the-art approaches using deep learning techniques. Our experiments on benchmark citation networks show that the best-fit model estimated by our algorithm leads to significant improvements on all datasets compared to baseline models. Further, our performance compares favorably with several state-of-the-art methods on these datasets, and is comparable with the best performances.

Image classification models take image pixels as input and predict labels in a predefined taxonomy. While contextual information (e.g. text surrounding an image) can provide valuable orthogonal signals to improve classification, the typical setting in literature assumes the unavailability of text and thus focuses on models that rely purely on pixels. In this work, we also focus on the setting where only pixels are available in the input. However, we demonstrate that if we predict textual information from pixels, we can subsequently use the predicted text to train models that improve overall performance. We propose a framework that consists of two main components: (1) a phrase generator that maps image pixels to a contextual phrase, and (2) a multimodal model that uses textual features from the phrase generator and visual features from the image pixels to produce labels in the output taxonomy. The phrase generator is trained using web-based query-image pairs to incorporate contextual information associated with each image and has a large output space. We evaluate our framework on diverse benchmark datasets (specifically, the WebVision dataset for evaluating multi-class classification and OpenImages dataset for evaluating multi-label classification), demonstrating performance improvements over approaches based exclusively on pixels and showcasing benefits in prediction interpretability. We additionally present results to demonstrate that our framework provides improvements in few-shot learning of minimally labeled concepts. We further demonstrate the unique benefits of the multimodal nature of our framework by utilizing intermediate image/text co-embeddings to perform baseline zero-shot learning on the ImageNet dataset.

Graph-based algorithms are among the most successful paradigms for solving semi-supervised learning tasks. Recent work on graph convolutional networks and neural graph learning methods has successfully combined the expressiveness of neural networks with graph structures. We propose a technique that, when applied to these methods, achieves state-of-the-art results on semi-supervised learning datasets. Traditional graph-based algorithms, such as label propagation, were designed with the underlying assumption that the label of a node can be imputed from that of the neighboring nodes. However, real-world graphs are either noisy or have edges that do not correspond to label agreement. To address this, we propose Graph Agreement Models (GAM), which introduces an auxiliary model that predicts the probability of two nodes sharing the same label as a learned function of their features. The agreement model is used when training a node classification model by encouraging agreement only for the pairs of nodes it deems likely to have the same label, thus guiding its parameters to better local optima. The classification and agreement models are trained jointly in a co-training fashion. Moreover, GAM can also be applied to any semi-supervised classification problem, by inducing a graph whenever one is not provided. We demonstrate that our method achieves a relative improvement of up to 72% for various node classification models, and obtains state-of-the-art results on multiple established datasets.

Time series analysis is commonly used when monitoring data centers, networks, weather, and even human patients. In most cases, the raw time series data is massive, from millions to billions of data points, and yet interactive analyses require low (e.g., sub-second) latency. Aperture transforms raw time series data, during ingest, into compact summarized representations that it can use to efficiently answer queries at runtime. Aperture handles a range of complex queries, from correlating hundreds of lengthy time series to predicting anomalies in the data. Aperture achieves much of its high performance by executing queries on data summaries, while providing a bound on the information lost when transforming data. By doing so, Aperture can reduce query latency as well as the data that needs to be stored and analyzed to answer a query. Our experiments on real data show that Aperture can provide one to four orders of magnitude lower query response time, while incurring only 10% ingest time overhead and less than 20% error in accuracy.

Hadoop and its variants have been widely used for processing large scale analytics tasks in a cluster environment. However, use of a commodity cluster for analytics tasks needs to be reconsidered based on two key observations: (1) in recent years, large memory, multicore machines have become more affordable; and (2) recent studies show that most analytics tasks in practice are smaller than 100 GB. Thus, replacing a commodity cluster with a large memory, multicore machine can enable in-memory analytics at an affordable cost. However= programming on a big-memory, multicore machine is a challenge. Multi-threaded programming is notoriously difficult. Further, the memory design of most large memory servers follows non-uniform memory access (NUMA) architecture. While NUMA-aware programming often leads to high efficiency in analytics tasks, it is usually done in an ad hoc manner.

We consider the problem of lossy estimation of an arbitrary smooth function of correlated data in a stream. In this problem, a user sequentially observes correlated random variables and wants to construct an estimate of the specified function so that the mean squared estimation error is small. Techniques from high resolution quantization theory are applied and expanded for this problem, and the optimal distortion-rate exponent for companding quantization is determined. In the process, connections are established to sufficient statistics and to sensitivity matrices, as introduced by Linder et al. in the context of companding quantization under non-difference distortion measures. These results are applied to several example statistical functions, including the sample mean, sample variance, and the p-th order statistic.

We propose a sequence of universal denoisers motivated by the goal of extending the notion of twice-universality from universal data compression theory to the sliding window denoising setting. Given a sequence lengthnand a denoiser, thekth-order regret of the latter is the maximum excess expected denoising loss relative to sliding window denoisers with window length 2k+1, where, for a given clean sequence, the expectation is over all channel realizations and the maximum is over all clean sequences of lengthn. We define the twice-universality penalty of a denoiser as its excesskth-order regret when compared to a bound on thekth-order regret of the denoising algorithm DUDE with parameterk, and we are interested in denoisers with a negligible penalty for allksimultaneously. We consider a class of denoisers that apply one of a number of constituent denoisers based on minimizing an estimated denoising loss and establish a formal relationship between the error in the estimated denoising loss and the twice-universality penalty of the resulting denoiser. Given a sequence of window parameterskn, increasing innsufficiently fast, we use this approach to construct and analyze a specific sequence of denoisers that achieves a much smaller twice-universality penalty forkknthan the sequence of DUDE denoisers with parameterkn.

We study the binary deletion channel where each input bit is independently deleted according to a fixed probability. We relate the conditional probability distribution of the output of the deletion channel given the input to the hidden pattern matching problem. This yields a new characterization of the mutual information between the input and output of the deletion channel. Through this characterization we are able to comment on the the deletion channel capacity, in particular for deletion probabilities approaching 0 and 1.

Data centers are growing in size and complexity driven by trends such as cloud computing and on-line services. Such large data centers pose several challenges for system management. Key among them is anomaly detection which is required to monitor and analyze metrics across several thousands servers and across multiple layers of abstractions to detect anomalous system behavior. In practice, multiple anomaly detection tools are used to continuously raise alarms across multiple metrics and servers. These alarms include both true positives and false alarms. Administrators and management tools act on these alarms for diagnosis and deeper root cause analysis and take appropriate management actions to mitigate the anomalous behaviors. Given the scale and scope of the system, the administrators and management tools are overwhelmed with the large number of alarms at any given instant, many of which are false alarms. It is therefore necessary to prioritize and rank these alarms, so as to take timely actions that maintain the service level agreements for the data center. Existing techniques for such ranking are ad-hoc and not scalable. We propose ranking windows of monitored metrics based on their probability of occurrence. We explain how these probabilities can be computed based either on the false positive rates for which the accompanying anomaly detectors were designed, or, when available, on the probability models underlying the false positive rates. In the simplest case, the ranking procedure reduces to computing the Z-score of the observed measurements and computing a statistic from a window of Z-scores to use as a basis for ranking. The proposed techniques are reliable, lightweight and easy to deploy in the modern data center. We have validated these techniques on synthetic data containing injected anomalies and on data acquired from production data centers.

Online anomaly detection is an important step in data center management, requiring light-weight techniques that provide sufficient accuracy for subsequent diagnosis and management actions. This paper presents statistical techniques based on the Tukey and Relative Entropy statistics, and applies them to data collected from a production environment and to data captured from a testbed for multi-tier web applications running on server class machines. The proposed techniques are lightweight and improve over standard Gaussian assumptions in terms of performance.

We propose a new sequence of universal denoisers motivated by the goal of extending the notion of twice-universality from universal data compression theory to the sliding window denoising setting. Given a sequence length n and a denoiser, we define the twice-universality penalty of the denoiser as the worst case excess expected denoising loss relative to sliding window denoisers with window length k above and beyond the worst case excess loss of DUDE with parameter k. Given a sequence of window parameters kn, increasing in n sufficiently fast, we use loss estimators to construct a sequence of denoisers that achieves a much smaller twice-universality penalty for knthan the sequence of DUDEs with parameter kn.

We consider the problem of computing functions of data streams while employing limited memory in a standard information-theoretic framework. A streaming system with memory constraint has to observe a collection of sources X1, X2,...,Xmsequentially, store synopses of the sources in memory, and compute a function of the sources based on the synopses. We establish a correspondence between this problem and a functional source coding problem in cascade/line networks. For the general functional source coding problem in cascade networks, we derive inner and outer bounds, and for distributions satisfying certain properties, we characterize the achievable rate-region exactly for the computation of any function. As a result of the correspondence we established, this result also characterizes the minimum amount of memory required to compute the function in a streaming system. We briefly discuss the implications of this result for the problem of distinct value computation.

We study the concentration of denoiser loss estimators, with application to the selection of denoiser parameters for a given observed sequence (in particular, the window size k of the DUDE algorithm) via minimization of the estimated loss. We show that for a loss estimator proposed earlier, it is not possible to derive strong concentration results for certain pathological input sequences. By modifying the estimator slightly we obtain a loss estimator for which the DUDE's estimated loss strongly concentrates around the true loss provided kM2k= o(n), where M is the size of the alphabet and n the sequence length. We also show that for certain channels, it is possible to estimate the best k using a combination of the two loss estimators. Moreover, for non-pathological sequences and k = o(n¿), we derive concentration results for the original loss estimator and all channels.

As clustering methods are often sensitive to parameter tuning, obtaining stability in clustering results is an important task. In this work, we aim at improving clustering stability by attempting to diminish the influence of algorithmic inconsistencies and enhance the signal that comes from the data. We propose a mechanism that takes m clusterings as input and outputs m clusterings of comparable quality, which are in higher agreement with each other. We call our method the Clustering Agreement Process (CAP). To preserve the clustering quality, CAP uses the same optimization procedure as used in clustering. In particular, we study the stability problem of randomized clustering methods (which usually produce different results at each run). We focus on methods that are based on inference in a combinatorial Markov Random Field (or Comraf, for short) of a simple topology. We instantiate CAP as inference within a more complex, bipartite Comraf. We test the resulting system on four datasets, three of which are medium-sized text collections, while the fourth is a large-scale user/movie dataset. First, in all the four cases, our system significantly improves the clustering stability measured in terms of the macro-averaged Jaccard index. Second, in all the four cases our system managed to significantly improve clustering quality as well, achieving the state-of-the-art results. Third, our system significantly improves stability of consensus clustering built on top of the randomized clustering solutions.

In the spirit of results on universal compression, we compare the performance of universal denoisers on discrete memoryless channels to that of the best performance obtained by an omniscient kth-order sliding-window denoiser, namely, one that is tuned to the transmitted noiseless sequence. We show that the additional loss incurred in the worst case by any universal denoiser on a length- n sequence grows at least like Omega(ck/radicn) , where c is a constant depending on the channel parameters and the loss function. This shows that for fixed k the additional loss incurred by the Discrete Universal Denoiser (DUDE) is no larger than a constant multiplicative factor of the best possible. Furthermore, we compare universal denoisers to denoisers that are aware of the distribution of the transmitted noiseless sequence. We show that, even for this weaker target loss, for any universal denoiser there exists some distribution for the noiseless sequence corresponding to a sequence of independent and identically distributed (i.i.d.) random variables whose optimum expected loss is lower than that incurred by the universal denoiser by Omega(1/radicn).

We present a framework for considering the problem of compressing large collections of similar sequences. In this framework, an unknown individual sequence is modified several times independently to obtain the collection of sequences to be compressed. For certain collections generated by context-dependent bit flips of the individual sequencepsilas bits, and for those generated by simple edit operations on the individual sequence, we derive universal compression algorithms that compress the collection of sequences almost as well as an optimal compressor that has knowledge of the underlying individual sequence and the modifying processes.

In many applications, an uncompressed source stream is systematically encoded by a channel code (which ignores the source redundancy) for transmission over a discrete memoryless channel. The decoder knows the channel and the code but does not know the source statistics. This paper proposes several universal channel decoders that take advantage of the source redundancy without requiring prior knowledge of its statistics.

The Gale-Berlekamp (in short, GB) code is the dual code of the binary product code in which the horizontal and vertical constituent codes are both the parity code. It is shown that the problem of deciding whether there is a codeword of the GB code within a prescribed distance from a given received word, is NP-complete. The problem remains hard (in a well-defined sense) even if the decoder is allowed unlimited preprocessing that depends only on the code length. While the intractability of maximum-likelihood decoding (MLD) for specific codes has already been shown by Bruck and Naor, Lobstein, and Guruswami and Vardy, the result herein seems to be the first that shows hardness for a "natural" code (in particular, without any tailoring of the definition or the parameters of the code to suit the hardness proof). In contrast, it is also shown that, with respect to any memoryless binary-symmetric channel (BSC) with crossover probability less than 1/2, MLD can be implemented in linear time for all error events except for a portion that occurs with vanishing probability.

The Gale-Berlekamp (in short, GB) code is the dual code of the binary product code in which the horizontal and vertical constituent codes are both the parity code. It is shown that the problem of deciding whether there is a codeword of the GB code within a prescribed distance from a given received word, is NP-complete. The problem remains hard (in a well-defined sense) even if the decoder is allowed unlimited preprocessing that depends only on the code length. While the intractability of maximum-likelihood decoding for specific codes has already been shown by Bruck and Naor and Lobstein, the result herein seems to be the first that shows hardness for familiar (or "natural") codes. In contrast, it is also shown that, with respect to any memoryless binary symmetric channel with crossover probability less than 1/2, maximum-likelihood decoding can be implemented in linear time for all error events except for a portion that occurs with vanishing probability.

Following recent work by Weissman et al, in the spirit of results on universal compression, we compare the performance of universal denoisers on discrete memoryless channels to that of the best k-th order omniscient denoiser, namely one that is tuned to the transmitted noiseless sequence. We show that the additional loss incurred in the worst case by any denoiser on a length-n sequence grows like Omega(ck/radicn), where c > 1 is a constant depending on the channel parameters and the loss function. This shows that for fixed k, the additional loss incurred by the discrete universal denoiser (DUDE) is no larger than a constant multiplicative factor of the best possible

Building on [1], [5], we model probability distributions from data using the high profile distribution. We show that the high profile distribution is majorized by the empirical frequency distribution, that the support of high profile distributions can be mixed, namely the distribution can have both discrete and continuous components, and obtain the high profile distribution for certain profiles. We then experimentally compare the high profile distribution with certain estimators that have been studied in statistics literature for the species estimation problem.

We determine the entropy rate of patterns of certain random processes including all finite-entropy stationary processes. For independent and identically distributed (i.i.d.) processes, we also bound the speed at which the per-symbol pattern entropy converges to this rate, and show that patterns satisfy an asymptotic equipartition property. To derive some of these results we upper bound the probability that the nth variable in a random process differs from all preceding ones.

Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.

This paper describes the channel decoding of systematically encoded unknown redundant sources. The redundancy of the data is known at the decoder and the channel decoder incorporates the statistics of the data to enhance the performance. The practical decoders are designed which takes the advantage of the source redundancy of systematically encoded for transmission over a discrete memoryless channel (DMC). The performance is achieved by operating discrete universal denoiser (DUDE) and the experiments involving Reed-Solomon codes show that DUDE-enhanced decoding is very effective at high rates.

We consider the problem of modeling a distribution whose alphabet size is large relative to the amount of observed data. It is well known that conventional maximum-likelihood estimates do not perform well in that regime. Instead, we find the distribution maximizing the probability of the data's pattern. We derive an efficient algorithm for approximating this distribution. Simulations show that the computed distribution models the data well and yields general estimators that evaluate various data attributes as well as specific estimators designed especially for these tasks

We determine the entropy rate of patterns of i.i.d. strings and show that they satisfy an asymptotic equipartition property. We prove that for discrete distributions the entropy rate of patterns equals that of the distribution, and that for distributions with continuous probability q, the entropy rate of patterns equals that of a modified distribution where the continuous probability is assigned to a new discrete element. One implication of these results is that for discrete distributions the conditional entropy rate of the sequence when its pattern is known is zero. We address only distributions with finite entropy.

We establish a further connection between one-way communication where a sender conveys information to a receiver who has related information, and error-correction coding where a sender attempts to communicate reliably over a noisy channel. Using this connection we obtain three results on the two problems. We derive an often-tight lower bound on the number of bits required for one-way communication based on the largest code for the corresponding error-correction problem. We construct an error-correcting code whose minimum distance properties are similar to those of Bose-Chaudhuri-Hocquenghem (BCH) codes based on a one-way communication protocol for set reconciliation. Finally, we prove that one-way communication is suboptimal for a large class of Hamming-distance problems.