The science papers I've read

Today I read a paper titled “Robustness of Regional Matching Scheme over Global Matching Scheme”

The abstract is:
The paper has established and verified the theory prevailing widely among image and pattern recognition specialists that the bottom-up indirect regional matching process is the more stable and the more robust than the global matching process against concentrated types of noise represented by clutter, outlier or occlusion in the imagery.

We have demonstrated this by analyzing the effect of concentrated noise on a typical decision making process of a simplified two candidate voting model where our theorem establishes the lower bounds to a critical breakdown point of election (or decision) result by the bottom-up matching process are greater than the exact bound of the global matching process implying that the former regional process is capable of accommodating a higher level of noise than the latter global process before the result of decision overturns.

We present a convincing experimental verification supporting not only the theory by a white-black flag recognition problem in the presence of localized noise but also the validity of the conjecture by a facial recognition problem that the theorem remains valid for other decision making processes involving an important dimension-reducing transform such as principal component analysis or a Gabor transform.

Today I read a paper titled “On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs”

The abstract is:
Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move.

Moreover, the players have common interests: at each node, all the players get the same payoff.

We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game..

Today I read a paper titled “Kalman filter control in the reinforcement learning framework”

The abstract is:
There is a growing interest in using Kalman-filter models in brain modelling.

In turn, it is of considerable importance to make Kalman-filters amenable for reinforcement learning.

In the usual formulation of optimal control it is computed off-line by solving a backward recursion.

In this technical note we show that slight modification of the linear-quadratic-Gaussian Kalman-filter model allows the on-line estimation of optimal control and makes the bridge to reinforcement learning.

Moreover, the learning rule for value estimation assumes a Hebbian form weighted by the error of the value estimation.

Today I read a paper titled “When being Weak is Brave: Privacy in Recommender Systems”

The abstract is:
We explore the conflict between personalization and privacy that arises from the existence of weak ties.

A weak tie is an unexpected connection that provides serendipitous recommendations.

However, information about weak ties could be used in conjunction with other sources of data to uncover identities and reveal other personal information.

In this article, we use a graph-theoretic model to study the benefit and risk from weak ties.

Today I read a paper titled “Detecting Race Conditions in Parallel Programs that Use Semaphores”

The abstract is:
We address the problem of detecting race conditions in programs that use semaphores for synchronization.

Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores.

We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs.

For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed.

The first algorithm determines in O(n) time whether a race condition exists between any two given operations.

The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations.

The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.

Today I read a paper titled “On the Sum-of-Squares Algorithm for Bin Packing”

The abstract is:
In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, along with several new variants.

$SS$ is applicable to any instance of bin packing in which the bin capacity $B$ and item sizes $s(a)$ are integral (or can be scaled to be so), and runs in time $O(nB)$.

It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, $SS$ also has sublinear expected waste.

For any discrete distribution where the optimal expected waste is bounded, $SS$ has expected waste at most $O(\log n)$.

In addition, we discuss several interesting variants on $SS$, including a randomized $O(nB\log B)$-time on-line algorithm $SS^*$, based on $SS$, whose expected behavior is essentially optimal for all discrete distributions.

Algorithm $SS^*$ also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution $F$, just what is the growth rate for the optimal expected waste.

This article is a greatly expanded version of the conference paper \cite{sumsq2000}.

Today I read a paper titled “Fast Hands-free Writing by Gaze Direction”

The abstract is:
We describe a method for text entry based on inverse arithmetic coding that relies on gaze direction and which is faster and more accurate than using an on-screen keyboard.

These benefits are derived from two innovations: the writing task is matched to the capabilities of the eye, and a language model is used to make predictable words and phrases easier to write.

Today I read a paper titled “Some Advances in Transformation-Based Part of Speech Tagging”

The abstract is:
Most recent research in trainable part of speech taggers has explored stochastic tagging.

While these taggers obtain high accuracy, linguistic information is captured indirectly, typically in tens of thousands of lexical and contextual probabilities.

In [Brill92], a trainable rule-based tagger was described that obtained performance comparable to that of stochastic taggers, but captured relevant linguistic information in a small number of simple non-stochastic rules.

In this paper, we describe a number of extensions to this rule-based tagger.

First, we describe a method for expressing lexical relations in tagging that are not captured by stochastic taggers.

Next, we show a rule-based approach to tagging unknown words.

Finally, we show how the tagger can be extended into a k-best tagger, where multiple tags can be assigned to words in some cases of uncertainty..

Today I read a paper titled “Generalized Cores”

The abstract is:
Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks.

In the paper a generalization of the notion of core of a graph based on vertex property function is presented.

It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m \max (\Delta, \log n))$ time.

Today I read a paper titled “Fuzzy Approaches to Abductive Inference”

The abstract is:
This paper proposes two kinds of fuzzy abductive inference in the framework of fuzzy rule base.

The abductive inference processes described here depend on the semantic of the rule.

We distinguish two classes of interpretation of a fuzzy rule, certainty generation rules and possible generation rules.

In this paper we present the architecture of abductive inference in the first class of interpretation.

We give two kinds of problem that we can resolve by using the proposed models of inference.

Today I read a paper titled “Searching for Spaceships”

The abstract is:
We describe software that searches for spaceships in Conway’s Game of Life and related two-dimensional cellular automata.

Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state.

Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.

Today I read a paper titled “Cluster Computing: A High-Performance Contender”

The abstract is:
When you first heard people speak of Piles of PCs, the first thing that came to mind may have been a cluttered computer room with processors, monitors, and snarls of cables all around.

Collections of computers have undoubtedly become more sophisticated than in the early days of shared drives and modem connections.

No matter what you call them, Clusters of Workstations (COW), Networks of Workstations (NOW), Workstation Clusters (WCs), Clusters of PCs (CoPs), clusters of computers are now filling the processing niche once occupied by more powerful stand-alone machines.

This article discusses the need for cluster computing technology, Technologies, Components, and Applications, Supercluster Systems and Issues, The Need for a New Task Force, and Cluster Computing Educational Resources.

Today I read a paper titled “Sorting with a forklift”

The abstract is:
A fork stack is a generalised stack which allows pushes and pops of several items at a time.

We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack.

An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found.

The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time.

In this context we also establish how to enumerate the collection of sortable sequences.

Today I read a paper titled “Provably Bounded-Optimal Agents”

The abstract is:
Since its inception, artificial intelligence has relied upon a theoretical foundation centered around perfect rationality as the desired property of intelligent systems.

We argue, as others have done, that this foundation is inadequate because it imposes fundamentally unsatisfiable requirements.

As a result, there has arisen a wide gap between theory and practice in AI, hindering progress in the field.

We propose instead a property called bounded optimality.

Roughly speaking, an agent is bounded-optimal if its program is a solution to the constrained optimization problem presented by its architecture and the task environment.

We show how to construct agents with this property for a simple class of machine architectures in a broad class of real-time environments.

We illustrate these results using a simple model of an automated mail sorting facility.

We also define a weaker property, asymptotic bounded optimality (ABO), that generalizes the notion of optimality in classical complexity theory.

We then construct universal ABO programs, i.e., programs that are ABO no matter what real-time constraints are applied.

Universal ABO programs can be used as building blocks for more complex systems.

We conclude with a discussion of the prospects for bounded optimality as a theoretical basis for AI, and relate it to similar trends in philosophy, economics, and game theory..

Today I read a paper titled “Optimal Aggregation Algorithms for Middleware”

The abstract is:
Let D be a database of N objects where each object has m fields.

The objects are given in m sorted lists (where the ith list is sorted according to the ith field).

Our goal is to find the top k objects according to a monotone aggregation function t, while minimizing access to the lists.

The problem arises in several contexts.

In particular Fagin (JCSS 1999) considered it for the purpose of aggregating information in a multimedia database system.

We are interested in instance optimality, i.e.

that our algorithm will be as good as any other (correct) algorithm on any instance.

We provide and analyze several instance optimal algorithms for the task, with various access costs and models.

Today I read a paper titled “Computer-Generated Photorealistic Hair”

The abstract is:
This paper presents an efficient method for generating and rendering photorealistic hair in two dimensional pictures.

The method consists of three major steps.

Simulating an artist drawing is used to design the rough hair shape.

A convolution based filter is then used to generate photorealistic hair patches.

A refine procedure is finally used to blend the boundaries of the patches with surrounding areas.

This method can be used to create all types of photorealistic human hair (head hair, facial hair and body hair).

It is also suitable for fur and grass generation.

Applications of this method include: hairstyle designing/editing, damaged hair image restoration, human hair animation, virtual makeover of a human, and landscape creation..

Today I read a paper titled “The Risk Profile Problem for Stock Portfolio Optimization”

The abstract is:
This work initiates research into the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit.

The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown.

The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market.

For portfolios made up of two stocks, this work shows how to exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem.

However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem.

In particular, it is #P-complete to compute the distribution function associated with the average-case bound.

On the positive side, approximate answers can be computed by using random sampling techniques similar to those for high-dimensional volume estimation.

When k>2 stocks are considered, it is proved that a simple solution based on the same flow concepts as the 2-stock algorithm would imply that P = NP, so is highly unlikely.

This work gives approximation algorithms for this case as well as exact algorithms for some important special cases.

Today I read a paper titled “Behaviour-based Knowledge Systems: An Epigenetic Path from Behaviour to Knowledge”

The abstract is:
In this paper we expose the theoretical background underlying our current research.

This consists in the development of behaviour-based knowledge systems, for closing the gaps between behaviour-based and knowledge-based systems, and also between the understandings of the phenomena they model.

We expose the requirements and stages for developing behaviour-based knowledge systems and discuss their limits.

We believe that these are necessary conditions for the development of higher order cognitive capacities, in artificial and natural cognitive systems.

Today I read a paper titled “Towards a Theory of Cache-Efficient Algorithms”

The abstract is:
We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters.

Our model, an extension of Aggarwal and Vitter’s I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations.

As a corollary, we obtain cache-optimal algorithms for some fundamental problems like sorting, FFT, and an important subclass of permutations in the single-level cache model.

We also show that ignoring associativity concerns could lead to inferior performance, by analyzing the average-case cache behavior of mergesort.

We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting.

Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and dealing with the hitherto unresolved problem of limited associativity.

Today I read a paper titled “Map Graphs”

The abstract is:
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires).

Such adjacencies define a map graph.

We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point.

Today I read a paper titled “Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees”

The abstract is:
In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights.

The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time.

The first part of the paper surveys various algorithms available today both in sequential and distributed environments to solve static MST problem.

We also present some of the efficient sequential algorithms for computing dynamic MST like the Frederickson’s algorithm and Eppstein’s sparsification technique.

Lastly we present our new sequential and distributed algorithms for dynamic MST problem.

To our knowledge, this is the first of the distributed algorithms for computing dynamic MSTs.

Today I read a paper titled “Verbal Interactions in Virtual Worlds”

The abstract is:
We first discuss respective advantages of language interaction in virtual worlds and of using 3D images in dialogue systems.

Then, we describe an example of a verbal interaction system in virtual reality: Ulysse.

Ulysse is a conversational agent that helps a user navigate in virtual worlds.

It has been designed to be embedded in the representation of a participant of a virtual conference and it responds positively to motion orders.

Ulysse navigates the user’s viewpoint on his/her behalf in the virtual world.

On tests we carried out, we discovered that users, novices as well as experienced ones have difficulties moving in a 3D environment.

Agents such as Ulysse enable a user to carry out navigation motions that would have been impossible with classical interaction devices.

From the whole Ulysse system, we have stripped off a skeleton architecture that we have ported to VRML, Java, and Prolog.

We hope this skeleton helps the design of language applications in virtual worlds.

Today I read a paper titled “Forgetting Exceptions is Harmful in Language Learning”

The abstract is:
We show that in language learning, contrary to received wisdom, keeping exceptional training instances in memory can be beneficial for generalization accuracy.

We investigate this phenomenon empirically on a selection of benchmark natural language processing tasks: grapheme-to-phoneme conversion, part-of-speech tagging, prepositional-phrase attachment, and base noun phrase chunking.

In a first series of experiments we combine memory-based learning with training set editing techniques, in which instances are edited based on their typicality and class prediction strength.

Results show that editing exceptional instances (with low typicality or low class prediction strength) tends to harm generalization accuracy.

In a second series of experiments we compare memory-based learning and decision-tree learning methods on the same selection of tasks, and find that decision-tree learning often performs worse than memory-based learning.

Moreover, the decrease in performance can be linked to the degree of abstraction from exceptions (i.e., pruning or eagerness).

We provide explanations for both results in terms of the properties of the natural language processing tasks and the learning algorithms.

Today I read a paper titled “Word-Sense Disambiguation Using Decomposable Models”

The abstract is:
Most probabilistic classifiers used for word-sense disambiguation have either been based on only one contextual feature or have used a model that is simply assumed to characterize the interdependencies among multiple contextual features.

In this paper, a different approach to formulating a probabilistic model is presented along with a case study of the performance of models produced in this manner for the disambiguation of the noun “interest”.

We describe a method for formulating probabilistic models that use multiple contextual features for word-sense disambiguation, without requiring untested assumptions regarding the form of the model.

Using this approach, the joint distribution of all variables is described by only the most systematic variable interactions, thereby limiting the number of parameters to be estimated, supporting computational efficiency, and providing an understanding of the data..

Today I read a paper titled “The Minimum Expectation Selection Problem”

The abstract is:
We define the min-min expectation selection problem (resp.

max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp.

maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions.

We assume each distribution has finitely many atoms.

Let d be the number of distinct values in the support of the distributions.

We show that if d is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme.

For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor.

The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d.

We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.

Today I read a paper titled “The Generalized Universal Law of Generalization”

The abstract is:
It has been argued by Shepard that there is a robust psychological law that relates the distance between a pair of items in psychological space and the probability that they will be confused with each other.

Specifically, the probability of confusion is a negative exponential function of the distance between the pair of items.

In experimental contexts, distance is typically defined in terms of a multidimensional Euclidean space-but this assumption seems unlikely to hold for complex stimuli.

We show that, nonetheless, the Universal Law of Generalization can be derived in the more complex setting of arbitrary stimuli, using a much more universal measure of distance.

This universal distance is defined as the length of the shortest program that transforms the representations of the two items of interest into one another: the algorithmic information distance.

It is universal in the sense that it minorizes every computable distance: it is the smallest computable distance.

We show that the universal law of generalization holds with probability going to one-provided the confusion probabilities are computable.

We also give a mathematically more appealing form .

Today I read a paper titled “On the Information Engine of Circuit Design”

The abstract is:
This paper addresses a new approach to find a spectrum of information measures for the process of digital circuit synthesis.

We consider the problem from the information engine point of view.

The circuit synthesis as a whole and different steps of the design process (an example of decision diagram is given) are presented via such measurements as entropy, logical work and information vitality.

We also introduce new information measures to provide better estimates of synthesis criteria.

We show that the basic properties of information engine, such as the conservation law of information flow and the equilibrium law of information can be formulated.

Today I read a paper titled “Using Tree Automata and Regular Expressions to Manipulate Hierarchically Structured Data”

The abstract is:
Information, stored or transmitted in digital form, is often structured.

Individual data records are usually represented as hierarchies of their elements.

Together, records form larger structures.

Information processing applications have to take account of this structuring, which assigns different semantics to different data elements or records.

Big variety of structural schemata in use today often requires much flexibility from applications–for example, to process information coming from different sources.

To ensure application interoperability, translators are needed that can convert one structure into another.

This paper puts forward a formal data model aimed at supporting hierarchical data processing in a simple and flexible way.

The model is based on and extends results of two classical theories, studying finite string and tree automata.

The concept of finite automata and regular languages is applied to the case of arbitrarily structured tree-like hierarchical data records, represented as “structured strings.” These automata are compared with classical string and tree automata; the model is shown to be a superset of the classical models.

Regular grammars and expressions over structured strings are introduced.

Regular expression matching and substitution has been widely used for efficient unstructured text processing; the model described here brings the power of this proven technique to applications that deal with information trees.

A simple generic alternative is offered to replace today’s specialised ad-hoc approaches.

The model unifies structural and content transformations, providing applications with a single data type.

An example scenario of how to build applications based on this theory is discussed.

Further research directions are outlined.

Today I read a paper titled “Semiclassical Neural Network”

The abstract is:
We have constructed a simple semiclassical model of neural network where neurons have quantum links with one another in a chosen way and affect one another in a fashion analogous to action potentials.

We have examined the role of stochasticity introduced by the quantum potential and compare the system with the classical system of an integrate-and-fire model by Hopfield.

Average periodicity and short term retentivity of input memory are noted.

Today I read a paper titled “Structure of some sand pile model”

The abstract is:
SPM (Sand Pile Model) is a simple discrete dynamical system used in physics to represent granular objects.

It is deeply related to integer partitions, and many other combinatorics problems, such as tilings or rewriting systems.

The evolution of the system started with n stacked grains generates a lattice, denoted by SPM(n).

We study here the structure of this lattice.

We first explain how it can be constructed, by showing its strong self-similarity property.

Then, we define SPM(infini), a natural extension of SPM when one starts with an infinite number of grains.

Again, we give an efficient construction algorithm and a coding of this lattice using a self-similar tree.

The two approaches give different recursive formulae for the cardinal of SPM(n), where no closed formula have ever been found.

Today I read a paper titled “The Rough Guide to Constraint Propagation”

The abstract is:
We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way.

In particular, using the notions commutativity and semi-commutativity, we show how the well-known AC-3, PC-2, DAC and DPC algorithms are instances of a single generic algorithm.

The work reported here extends and simplifies that of Apt, cs.AI/9811024.

Today I read a paper titled “Mutual Search”

The abstract is:
We introduce a search problem called “mutual search” where $k$ \agents, arbitrarily distributed over $n$ sites, are required to locate one another by posing queries of the form “Anybody at site $i$?”.

We ask for the least number of queries that is necessary and sufficient.

For the case of two \agents using deterministic protocols we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed) there is no savings: $n-1$ queries are required and are sufficient.

In a nonoblivious setting we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case $0.586n$ queries suffice and $0.536n$ queries are required; in the asynchronous case $0.896n$ queries suffice and a fortiori 0.536 queries are required; for $o(\sqrt{n})$ \agents using a deterministic protocol less than $n$ queries suffice; there is a simple randomized protocol for two \agents with worst-case expected $0.5n$ queries and all randomized protocols require at least $0.125n$ worst-case expected queries.

The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

Today I read a paper titled “Evolution of genetic organization in digital organisms”

The abstract is:
We examine the evolution of expression patterns and the organization of genetic information in populations of self-replicating digital organisms.

Seeding the experiments with a linearly expressed ancestor, we witness the development of complex, parallel secondary expression patterns.

Using principles from information theory, we demonstrate an evolutionary pressure towards overlapping expressions causing variation (and hence further evolution) to sharply drop.

Finally, we compare the overlapping sections of dominant genomes to those portions which are singly expressed and observe a significant difference in the entropy of their encoding.

Today I read a paper titled “Constraint Logic Programming for Natural Language Processing”

The abstract is:
This paper proposes an evaluation of the adequacy of the constraint logic programming paradigm for natural language processing.

Theoretical aspects of this question have been discussed in several works.

We adopt here a pragmatic point of view and our argumentation relies on concrete solutions.

Using actual contraints (in the CLP sense) is neither easy nor direct.

However, CLP can improve parsing techniques in several aspects such as concision, control, efficiency or direct representation of linguistic formalism.

This discussion is illustrated by several examples and the presentation of an HPSG parser..

Today I read a paper titled “From Alife Agents to a Kingdom of N Queens”

The abstract is:
This paper presents a new approach to solving N-queen problems, which involves a model of distributed autonomous agents with artificial life (ALife) and a method of representing N-queen constraints in an agent environment.

The distributed agents locally interact with their living environment, i.e., a chessboard, and execute their reactive behaviors by applying their behavioral rules for randomized motion, least-conflict position searching, and cooperating with other agents etc.

The agent-based N-queen problem solving system evolves through selection and contest according to the rule of Survival of the Fittest, in which some agents will die or be eaten if their moving strategies are less efficient than others.

The experimental results have shown that this system is capable of solving large-scale N-queen problems.

This paper also provides a model of ALife agents for solving general CSPs.

Today I read a paper titled “A Classification Approach to Word Prediction”

The abstract is:
The eventual goal of a language model is to accurately predict the value of a missing word given its context.

We present an approach to word prediction that is based on learning a representation for each word as a function of words and linguistics predicates in its context.

This approach raises a few new questions that we address.

First, in order to learn good word representations it is necessary to use an expressive representation of the context.

We present a way that uses external knowledge to generate expressive context representations, along with a learning method capable of handling the large number of features generated this way that can, potentially, contribute to each prediction.

Second, since the number of words “competing” for each prediction is large, there is a need to “focus the attention” on a smaller subset of these.

We exhibit the contribution of a “focus of attention” mechanism to the performance of the word predictor.

Finally, we describe a large scale experimental study in which the approach presented is shown to yield significant improvements in word prediction tasks.

Today I read a paper titled “Linear and Order Statistics Combiners for Pattern Classification”

The abstract is:
Several researchers have experimentally shown that substantial improvements can be obtained in difficult pattern recognition problems by combining or integrating the outputs of multiple classifiers.

This chapter provides an analytical framework to quantify the improvements in classification results due to combining.

The results apply to both linear combiners and order statistics combiners.

We first show that to a first order approximation, the error rate obtained over and above the Bayes error rate, is directly proportional to the variance of the actual decision boundaries around the Bayes optimum boundary.

Combining classifiers in output space reduces this variance, and hence reduces the “added” error.

If N unbiased classifiers are combined by simple averaging, the added error rate can be reduced by a factor of N if the individual errors in approximating the decision boundaries are uncorrelated.

Expressions are then derived for linear combiners which are biased or correlated, and the effect of output correlations on ensemble performance is quantified.

For order statistics based non-linear combiners, we derive expressions that indicate how much the median, the maximum and in general the ith order statistic can improve classifier performance.

The analysis presented here facilitates the understanding of the relationships among error rates, classifier boundary distributions, and combining in output space.

Experimental results on several public domain data sets are provided to illustrate the benefits of combining and to support the analytical results.

Today I read a paper titled “A better lower bound for quantum algorithms searching an ordered list”

The abstract is:
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them.

Classically, log n queries are both necessary and sufficient.

This shows that quantum algorithms can achieve only a constant speedup for this problem.

Our result improves lower bounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann and Sipser (quant-ph/9812057).

Today I read a paper titled “Perception games, the image understanding and interpretational geometry”

The abstract is:
The interactive game theoretical approach to the description of perception processes is proposed.

The subject is treated formally in terms of a new class of the verbalizable interactive games which are called the perception games.

An application of the previously elaborated formalism of dialogues and verbalizable interactive games to the visual perception allows to combine the linguistic (such as formal grammars), psycholinguistic and (interactive) game theoretical methods for analysis of the image understanding by a human that may be also useful for the elaboration of computer vision systems.

By the way the interactive game theoretical aspects of interpretational geometries are clarified.

Today I read a paper titled “Multimodal Surrogates for Video Browsing”

The abstract is:
Three types of video surrogates – visual (keyframes), verbal (keywords/phrases), and combination of the two – were designed and studied in a qualitative investigation of user cognitive processes.

The results favor the combined surrogates in which verbal information and images reinforce each other, lead to better comprehension, and may actually require less processing time.

The results also highlight image features users found most helpful.

These findings will inform the interface design and video representation for video retrieval and browsing.

Today I read a paper titled “Chunk Tagger – Statistical Recognition of Noun Phrases”

The abstract is:
We describe a stochastic approach to partial parsing, i.e., the recognition of syntactic structures of limited depth.

The technique utilises Markov Models, but goes beyond usual bracketing approaches, since it is capable of recognising not only the boundaries, but also the internal structure and syntactic category of simple as well as complex NP’s, PP’s, AP’s and adverbials.

We compare tagging accuracy for different applications and encoding schemes.

Today I read a paper titled “Digital Color Imaging”

The abstract is:
This paper surveys current technology and research in the area of digital color imaging.

In order to establish the background and lay down terminology, fundamental concepts of color perception and measurement are first presented us-ing vector-space notation and terminology.

Present-day color recording and reproduction systems are reviewed along with the common mathematical models used for representing these devices.

Algorithms for processing color images for display and communication are surveyed, and a forecast of research trends is attempted.

An extensive bibliography is provided..

Today I read a paper titled “A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs”

The abstract is:
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits.

Specifically, a graph with property pi is called a pi-graph.

If pi satisfies certain properties, then an n-node m-edge pi-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs.

The methodology is applicable to general classes of graphs; this paper focuses on planar graphs.

Examples of such pi include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from {1, …, ell_1} for ell_1 <= n; (5) the edges of G are labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node (respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively, ell_4 = O(1) multiple edges).

Moreover, ell_3 and ell_4 are not required to be O(1) for the cases of pi being a plane triangulation.

These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes..

Today I read a paper titled “Data sonification and sound visualization”

The abstract is:
This article describes a collaborative project between researchers in the Mathematics and Computer Science Division at Argonne National Laboratory and the Computer Music Project of the University of Illinois at Urbana-Champaign.

The project focuses on the use of sound for the exploration and analysis of complex data sets in scientific computing.

The article addresses digital sound synthesis in the context of DIASS (Digital Instrument for Additive Sound Synthesis) and sound visualization in a virtual-reality environment by means of M4CAVE.

It describes the procedures and preliminary results of some experiments in scientific sonification and sound visualization.

Today I read a paper titled “Genetic Algorithms in Time-Dependent Environments”

The abstract is:
The influence of time-dependent fitnesses on the infinite population dynamics of simple genetic algorithms (without crossover) is analyzed.

Based on general arguments, a schematic phase diagram is constructed that allows one to characterize the asymptotic states in dependence on the mutation rate and the time scale of changes.

Furthermore, the notion of regular changes is raised for which the population can be shown to converge towards a generalized quasispecies.

Based on this, error thresholds and an optimal mutation rate are approximately calculated for a generational genetic algorithm with a moving needle-in-the-haystack landscape.

The so found phase diagram is fully consistent with our general considerations.

Today I read a paper titled “A Flexible Shallow Approach to Text Generation”

The abstract is:
In order to support the efficient development of NL generation systems, two orthogonal methods are currently pursued with emphasis: (1) reusable, general, and linguistically motivated surface realization components, and (2) simple, task-oriented template-based techniques.

In this paper we argue that, from an application-oriented perspective, the benefits of both are still limited.

In order to improve this situation, we suggest and evaluate shallow generation methods associated with increased flexibility.

We advise a close connection between domain-motivated and linguistic ontologies that supports the quick adaptation to new tasks and domains, rather than the reuse of general resources.

Our method is especially designed for generating reports with limited linguistic variations.

Today I read a paper titled “A Differential Invariant for Zooming”

The abstract is:
This paper presents an invariant under scaling and linear brightness change.

The invariant is based on differentials and therefore is a local feature.

Rotationally invariant 2-d differential Gaussian operators up to third order are proposed for the implementation of the invariant.

The performance is analyzed by simulating a camera zoom-out.

Today I read a paper titled “Dynamic Backtracking”

The abstract is:
Because of their occasional need to return to shallow points in a search tree, existing backtracking methods can sometimes erase meaningful progress toward solving a search problem.

In this paper, we present a method by which backtrack points can be moved deeper in the search space, thereby avoiding this difficulty.

The technique developed is a variant of dependency-directed backtracking that uses only polynomial space while still providing useful control information and retaining the completeness guarantees provided by earlier approaches..

Today I read a paper titled “An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings”

The abstract is:
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees.

Previous work on this similarity measure is only concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves).

This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner.

In addition to this generality, this algorithm is faster than the previous algorithms.

Another contribution of this paper is on maximum weight bipartite matchings.

We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced.

Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.

Today I read a paper titled “A Quick Glance at Quantum Cryptography”

The abstract is:
The recent application of the principles of quantum mechanics to cryptography has led to a remarkable new dimension in secret communication.

As a result of these new developments, it is now possible to construct cryptographic communication systems which detect unauthorized eavesdropping should it occur, and which give a guarantee of no eavesdropping should it not occur.

CONTENTS P3.

Cryptographic systems before quantum cryptography P7.

Preamble to quantum cryptography P10.

The BB84 quantum cryptographic protocol without noise P16.

The BB84 quantum cryptographic protocol with noise P19..The B92 quantum cryptographic protocol P21.

EPR quantum cryptographic protocols P25.

Other protocols P25.

Eavesdropping stategies and counter measures P26.

Conclusion P29.

Appendix A.

The no cloning theorem P30.

Appendix B.

Proof that an undetectable eavesdropper can obtain no information from the B92 protocol P31.

Appendix C.

Part of a Rosetta stone for quantum mechanics P44.

References .