Archives for 2003

Today I read a paper titled “Assisted Video Sequences Indexing : Motion Analysis Based on Interest Points”

The abstract is:
This work deals with content-based video indexing.

Our viewpoint is semi-automatic analysis of compressed video.

We consider the possible applications of motion analysis and moving object detection : assisting moving object indexing, summarising videos, and allowing image and motion queries.

We propose an approach based on interest points.

As first results, we test and compare the stability of different types of interest point detectors in compressed sequences.

Today I read a paper titled “About the finding of independent vertices of a graph”

The abstract is:
We examine the Maximum Independent Set Problem in an undirected graph.

The main result is that this problem can be considered as the solving the same problem in a subclass of the weighted normal twin-orthogonal graphs.

The problem is formulated which is dual to the problem above.

It is shown that, for trivial twin-orthogonal graphs, any of its maximal independent set is also maximum one.

Today I read a paper titled “Self-Organizing Machine Translation: Example-Driven Induction of Transfer Functions”

The abstract is:
With the advent of faster computers, the notion of doing machine translation from a huge stored database of translation examples is no longer unreasonable.

This paper describes an attempt to merge the Example-Based Machine Translation (EBMT) approach with psycholinguistic principles.

A new formalism for context- free grammars, called *marker-normal form*, is demonstrated and used to describe language data in a way compatible with psycholinguistic theories.

By embedding this formalism in a standard multivariate optimization framework, a system can be built that infers correct transfer functions for a set of bilingual sentence pairs and then uses those functions to translate novel sentences.

The validity of this line of reasoning has been tested in the development of a system called METLA-1.

This system has been used to infer English->French and English->Urdu transfer functions from small corpora.

The results of those experiments are examined, both in engineering terms as well as in more linguistic terms.

In general, the results of these experiments were psycho- logically and linguistically well-grounded while still achieving a respectable level of success when compared against a similar prototype using Hidden Markov Models..

Today I read a paper titled “Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model”

The abstract is:
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise.

This results in a polynomial-time algorithm for the case of parity functions that depend on only the first O(log n log log n) bits of input.

This is the first known instance of an efficient noise-tolerant algorithm for a concept class that is provably not learnable in the Statistical Query model of Kearns.

Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.

In coding-theory terms, what we give is a poly(n)-time algorithm for decoding linear k by n codes in the presence of random noise for the case of k = c log n loglog n for some c > 0.

(The case of k = O(log n) is trivial since one can just individually check each of the 2^k possible messages and choose the one that yields the closest codeword.) A natural extension of the statistical query model is to allow queries about statistical properties that involve t-tuples of examples (as opposed to single examples).

The second result of this paper is to show that any class of functions learnable (strongly or weakly) with t-wise queries for t = O(log n) is also weakly learnable with standard unary queries.

Hence this natural extension to the statistical query model does not increase the set of weakly learnable functions.

Today I read a paper titled “Coin-Moving Puzzles”

The abstract is:
We introduce a new family of one-player games, involving the movement of coins from one configuration to another.

Moves are restricted so that a coin can be placed only in a position that is adjacent to at least two other coins.

The goal of this paper is to specify exactly which of these games are solvable.

By introducing the notion of a constant number of extra coins, we give tight theorems characterizing solvable puzzles on the square grid and equilateral-triangle grid.

These existence results are supplemented by polynomial-time algorithms for finding a solution..

Today I read a paper titled “Perfect simulation from the Quicksort limit distribution”

The abstract is:
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation.

We give an algorithm for perfect random variate generation from this distribution.

Today I read a paper titled “Data Security Equals Graph Connectivity”

The abstract is:
To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table.

This paper investigates four levels of data security of a two-dimensional table concerning the effectiveness of this practice.

These four levels of data security protect the information contained in, respectively, individual cells, individual rows and columns, several rows or columns as a whole, and a table as a whole.

The paper presents efficient algorithms and NP-completeness results for testing and achieving these four levels of data security.

All these complexity results are obtained by means of fundamental equivalences between the four levels of data security of a table and four types of connectivity of a graph constructed from that table.