Archives for 2000

Today I read a paper titled “Finite-resolution hidden surface removal”

The abstract is:
We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in Real^3 and p sample points (“pixels”) in the xy-plane, determine the first triangle directly behind each pixel.

Our algorithm constructs the sampled visibility map of the triangles with respect to the pixels, which is the subset of the trapezoids in a trapezoidal decomposition of the analytic visibility map that contain at least one pixel.

The sampled visibility map adapts to local changes in image complexity, and its complexity is bounded both by the number of pixels and by the complexity of the analytic visibility map.

Our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + p), where t is the output size and e is any positive constant.

This is nearly optimal in the worst case and compares favorably with the best output-sensitive algorithms for both ray casting and analytic hidden surface removal.

In the special case where the pixels form a regular grid, a sweepline variant of our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + t log p), which is usually sublinear in the number of pixels..

Today I read a paper titled “Practical algorithms for on-line sampling”

The abstract is:
One of the core applications of machine learning to knowledge discovery consists on building a function (a hypothesis) from a given amount of data (for instance a decision tree or a neural network) such that we can use it afterwards to predict new instances of the data.

In this paper, we focus on a particular situation where we assume that the hypothesis we want to use for prediction is very simple, and thus, the hypotheses class is of feasible size.

We study the problem of how to determine which of the hypotheses in the class is almost the best one.

We present two on-line sampling algorithms for selecting hypotheses, give theoretical bounds on the number of necessary examples, and analize them exprimentally.

We compare them with the simple batch sampling approach commonly used and show that in most of the situations our algorithms use much fewer number of examples.

Today I read a paper titled “KnightCap: A chess program that learns by combining TD(lambda) with game-tree search”

The abstract is:
In this paper we present TDLeaf(lambda), a variation on the TD(lambda) algorithm that enables it to be used in conjunction with game-tree search.

We present some experiments in which our chess program “KnightCap” used TDLeaf(lambda) to learn its evaluation function while playing on the Free Internet Chess Server (FICS, fics.onenet.net).

The main success we report is that KnightCap improved from a 1650 rating to a 2150 rating in just 308 games and 3 days of play.

As a reference, a rating of 1650 corresponds to about level B human play (on a scale from E (1000) to A (1800)), while 2150 is human master level.

We discuss some of the reasons for this success, principle among them being the use of on-line, rather than self-play.

Today I read a paper titled “The importance of quantum decoherence in brain processes”

The abstract is:
Based on a calculation of neural decoherence rates, we argue that that the degrees of freedom of the human brain that relate to cognitive processes should be thought of as a classical rather than quantum system, i.e., that there is nothing fundamentally wrong with the current classical approach to neural network simulations.

We find that the decoherence timescales ~10^{-13}-10^{-20} seconds are typically much shorter than the relevant dynamical timescales (~0.001-0.1 seconds), both for regular neuron firing and for kink-like polarization excitations in microtubules.

This conclusion disagrees with suggestions by Penrose and others that the brain acts as a quantum computer, and that quantum coherence is related to consciousness in a fundamental way.

Today I read a paper titled “Relating Complexity to Practical Performance in Parsing with Wide-Coverage Unification Grammars”

The abstract is:
The paper demonstrates that exponential complexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar.

The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complexity theory can more accurately predict the practical behaviour of such parsers..

Today I read a paper titled “Image Compression with Iterated Function Systems, Finite Automata and Zerotrees: Grand Unification”

The abstract is:
Fractal image compression, Culik’s image compression and zerotree prediction coding of wavelet image decomposition coefficients succeed only because typical images being compressed possess a significant degree of self-similarity.

Besides the common concept, these methods turn out to be even more tightly related, to the point of algorithmical reducibility of one technique to another.

The goal of the present paper is to demonstrate these relations.

The paper offers a plain-term interpretation of Culik’s image compression, in regular image processing terms, without resorting to finite state machines and similar lofty language.

The interpretation is shown to be algorithmically related to an IFS fractal image compression method: an IFS can be exactly transformed into Culik’s image code.

Using this transformation, we will prove that in a self-similar (part of an) image any zero wavelet coefficient is the root of a zerotree, or its branch.

The paper discusses the zerotree coding of (wavelet/projection) coefficients as a common predictor/corrector, applied vertically through different layers of a multiresolutional decomposition, rather than within the same view.

This interpretation leads to an insight into the evolution of image compression techniques: from a causal single-layer prediction, to non-causal same-view predictions (wavelet decomposition among others) and to a causal cross-layer prediction (zero-trees, Culik’s method).

Today I read a paper titled “A High Quality Text-To-Speech System Composed of Multiple Neural Networks”

The abstract is:
While neural networks have been employed to handle several different text-to-speech tasks, ours is the first system to use neural networks throughout, for both linguistic and acoustic processing.

We divide the text-to-speech task into three subtasks, a linguistic module mapping from text to a linguistic representation, an acoustic module mapping from the linguistic representation to speech, and a video module mapping from the linguistic representation to animated images.

The linguistic module employs a letter-to-sound neural network and a postlexical neural network.

The acoustic module employs a duration neural network and a phonetic neural network.

The visual neural network is employed in parallel to the acoustic module to drive a talking head.

The use of neural networks that can be retrained on the characteristics of different voices and languages affords our system a degree of adaptability and naturalness heretofore unavailable.

Today I read a paper titled “Integration Of Visual Inter-word Constraints And Linguistic Knowledge In Degraded Text Recognition”

The abstract is:
Degraded text recognition is a difficult task.

Given a noisy text image, a word recognizer can be applied to generate several candidates for each word image.

High-level knowledge sources can then be used to select a decision from the candidate set for each word image.

In this paper, we propose that visual inter-word constraints can be used to facilitate candidate selection.

Visual inter-word constraints provide a way to link word images inside the text page, and to interpret them systematically..

Today I read a paper titled “A characterization of the set of fixed points of the Quicksort transformation”

The abstract is:
The limiting distribution \mu of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T — unique, that is, subject to the constraints of zero mean and finite variance.

We show that a distribution is a fixed point of T if and only if it is the convolution of \mu with a Cauchy distribution of arbitrary center and scale.

In particular, therefore, \mu is the unique fixed point of T having zero mean.