An Occam approximation is an algorithm that takes as input a set of samples of a function and a tolerance $\epsilon$ and produces as output a compact representation of a function that is within $\epsilon$ of the given samples. We show that the existence of an Occam approximation is sufficient to guarantee the probably approximate learnability of classes of functions on the reals even in the presence of arbitrarily large but random additive noise. One consequence of our results is a general technique for the design and analysis of nonlinear filters in digital signal processing.

We present an algorithm and a hardware architecture for block-based motion estimation that involves transforming video sequences from a multibit to a one-bit/pixel representation and then applying conventional motion estimation search strategies. This results in substantial reductions in arithmetic and hardware complexity and reduced power consumption, while maintaining good compression performance. Experimental results and a custom hardware design using a linear array of processing elements are also presented.

Preprocessing of image and video sequences with spatial filtering techniques usually improves the image quality and compressibility. We present a block-based, nonlinear filtering algorithm based on singular value decomposition and compression-based filtering. Experiments show that the proposed filter preserves edge details and can significantly improve the compression performance.

We present a strategy for block-based motion estimation that involves transforming video sequences from a multibit to a one-bit/pixel representation, and then applying conventional motion estimation search strategies. This results in substantial reductions in arithmetic and hardware complexity, and reduced power consumption, while maintaining good compression performance. Experimental results and a custom hardware design are also presented.

Encoding noisy data is a challenging problem in data compression. Recent results show that data compression and filtering are closely related. Exploiting these ideas, we propose a simple technique for vector quantization (VQ) coding of noisy images, based on pre-filtering only the training set prior to codebook design. We find that our technique results in significant improvement in image quality, comparable to that obtained by the computationally more expensive approach of pre-filtering both the training set and the images to be encoded. A preliminary justification of our results from the theory of Occam filtering is also provided.

An Occam filter employs lossy data compression to separate signal from noise. Previously it was shown that Occam filters are useful for filtering random noise from discrete samples of a deterministic and continuous signal. In this paper, we show that Occam filters can also be used to separate two stochastic sources, with the effectiveness of the separation depending on their relative compressibility. We then construct an Occam filter based on singular value decomposition (SVD) and apply it to digital images corrupted with Gaussian noise. We observe that the SVD-based Occam filter outperforms the wavelet-based denoising method of Donoho and Johnstone (1994) and DeVore and Lucier (1992).

Branch prediction is the predominant approach for minimizing the pipeline breaks caused by branch instructions. Traditionally, branch prediction is accomplished in one of two ways, static prediction at compile-time via compiler analysis or dynamic prediction at run-time via special hardware structures. In this paper, we propose a novel technique that aims to combine the strengths of the two approaches-the lower cost of compile-time analysis with the effectiveness of dynamic prediction. Specifically, we propose that the compiler use profile feedback to define a prediction function for each branch and insert a few explicit instructions per branch into the compiled code to compute the prediction function. These instructions are carefully selected to predict the direction of the branch using any information available during run-time. A strength of this approach is that information beyond branch history can be used to make predictions, such as the contents of the architectural registers. To substantiate our proposal, we present an algorithm for selecting the prediction instructions, and demonstrate the performance of the approach against contemporary static and dynamic branch prediction strategies.

Speedup learning seeks to improve the computational efficiency of problem solving with experience. In this paper, we develop a formal framework for learning efficient problem solving from random problems and their solutions. We apply this framework to two different representations of learned knowledge, namely control rules and macro-operators, and prove theorems that identify sufficient conditions for learning in each representation. Our proofs are constructive in that they are accompanied with learning algorithms. Our framework captures both empirical and explanation-based speedup learning in a unified fashion. We illustrate our framework with implementations in two domains: symbolic integration and Eight Puzzle. This work integrates many strands of experimental and theoretical work in machine learning, including empirical learning of control rules, macro-operator learning, Explanation-Based Learning (EBL), and Probably Approximately Correct (PAC) Learning.

We present a fast approximate algorithm for scaling down an image by a factor of two, when the input and output streams are both in the form of 8/spl times/8 discrete cosine transform (DCT) transform blocks, as with JPEG coded images. Roughly speaking, the algorithm requires 80% fewer operations than the naive algorithm of inverting the transform, scaling in the spatial domain, and transforming the resulting image.

The following problem is considered: given a matrix A in ${\bf R}^{m\times n}$, (m rows and n columns), a vector b in ${\bf R}^m$, and $\epsilon > 0$, compute a vector x satisfying $\|Ax - b\|_{2} \leq \epsilon $ if such exists, such that x has the fewest number of non-zero entries over all such vectors. It is shown that the problem is NP-hard, but that the well-known greedy heuristic is good in that it computes a solution with at most $\lceil 18 \operatorname{Opt}(\epsilon/2)\|{\bf A}^{+}\|_{2}^{2} \ln ({\| b \|_{2}/\epsilon})\rceil$ non-zero entries, where $\operatorname{Opt}(\epsilon/2)$ is the optimum number of nonzero entries at error $\epsilon/2$, ${\textbf{A}}$ is the matrix obtained by normalizing each column of A with respect to the $L_{2}$ norm, and $\textbf{A}^{+}$ is its pseudo-inverse.

Occam filters are a general technique for filtering random noise via data compression. Previously it was established that these filters converge in a learning theoretic sense, with convergence bounds that depended on the probability distribution of the noise variable. The paper presents a convergence bound for uniformly sampled signals that is independent of the probability distribution of the noise variable, barring some minimal assumptions. It also examines an application of Occam filters to remove random noise from digital video, thereby enabling improved nearly lossless compression.>

We present a novel non-linear filtering technique for random noise, based on the principle that random noise is hard to compress. In contrast to spectral filters, the proposed technique does not require a priori knowledge of the noise and signal characteristics. We demonstrate the technique by filtering additive random noise using a compression algorithm based on piecewise linear approximation. A single chip design of the filtering algorithm is also presented. It includes two multiplier-accumulator units, an adder, registers, and a short look-up table. The proposed implementation allows an output sample to be generated every four cycles on average.>

We present a non-linear filtering technique for digital video to enable improved nearly lossless compression. In contrast to preprocessing techniques, our technique uses the compression algorithm for both filtering and compression in one step, by exploiting the property that random noise is hard to compress.>

Occam approximationis an algorithm that takes as . .input a set of samples of a function and a tolerance 6, and produces as output a compact representation of a

The authors explore compression using an optimal algorithm for the approximation of waveforms with piecewise linear functions. They describe a modification of the algorithm that is provably good, but simple enough for the associated hardware implementation to be presentable.>

A general technique is suggested for reducing random noise from signals using data compression in conjunction with the principle of Occam's Razor. Not only are classical spectral filters realisable as a particular instance of the technique, but more powerful nonlinear filters fall within its scope.>

This paper presents algorithms that construct approximations to sets and functions on the reals, from randomly chosen sample points. The model that is analyzed is a generalization of the paradigm of probably approximate learning proposed by Valiant. Previously, necessary and sufficient conditions for learning sets were established for the case when the class of sampling distributions is finite, and for the case when the class of sampling distributions is the set of all possible distributions. Here, sufficient conditions are obtained for learning sets and functions over general classes of sampling distributions. The results for functions are with respect to general metrics for measuring the distance between two functions.

Probably approximate learning is the inference of a set (also called a concept) from a small number of sample points, under the probabilistic measure of success proposed in [L. G. Valiant, Proc. ACM Symposium on Theory of Computing, 1984, pp. 436–445]. Within this model, necessary and sufficient conditions are identified for efficient learning of a class of concepts defined on the strings of the binary alphabet. These results are with respect to both time and information complexity measures and are in terms of the asymptotic behaviour of the Vapnik–Chervonenkis dimension of the class. Corresponding results are also obtained for the case when the error in the learning process is to be one-sided, in that the inferred concept is required to be a subset of the concept to be learned. The scope of the learning model is then widened to include the inference of functions. The Vapnik–Chervonenkis dimension is also extended to obtain a measure called the “generalized dimension” of a class of functions. Using this measure, necessary and sufficient conditions for efficient learning of classes of functions are identified. These results are obtained for functions defined on the strings of the binary alphabet as well as for functions defined on the continuous domain of the real numbers.

We consider the problem of computing a piecewise linear approximation to the intersection of a pair of tensor product B-spline surfaces in 3-space. The problem is rather central in solid modeling. We present a fast and robust divide-and-conquer algorithm for the problem, that is a generalization of the bisection algorithm for computing the roots of non-linear equations. The algorithm is guaranteed to solve a “nearby” problem, and our analysis proves that its expected run-time is linear in the worst-case size of the output. To our knowledge, this is the first such analysis, resulting in the first provably efficient algorithm for the problem.

This paper concerns the problem of assembling composite objects. We study the problem on two fronts; Firstly we study the complexity of deciding the existence of an assembly sequence and show that this is PSPACE-hard in general. Secondly we define a new measure of complexity, one that attempts to measure the minimum number of hands required to assemble a given composite. We analyze various classes of composite objects with respect to this measure.

This paper concerns the use of ray sensors to detect the orientation of polygonal and polyhedral objects moving on a belt or slide. The problem is abstracted to the computational domain and the following results obtained. For polygons of n vertices, n sensors are sufficient and (n/2) necessary. For convex polyhedra of n vertices, (6n) sensors are sufficient and (n/4) necessary. Non-convex polyhedra cannot be effectively handled with such sensors.

This paper deals with the learnability of Boolean functions. An intuitively appealing notion of dimensionality is developed and used to identify the most general class of Boolean function families that are learnable from polynomially many positive examples with one-sided error. It is then argued that although bounded DNF expressions lie outside this class, they must have efficient learning algorithms as they are well suited for expressing many human concepts. A framework that permits efficient learning of bounded DNF functions is identified.

This paper concerns the design of parts orienters - the dual to the motion planning problem. Two particular paradigms are considered and their abstractions to the computational domain lead to interesting problems in graph pebbling and function composition on finite sets. Polynomial time algorithms are developed for the abstracted problems.