The science papers I've read

Today I read a paper titled “Opportunity Cost Algorithms for Combinatorial Auctions”

The abstract is:
Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids.

Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other.

The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs.

The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids.

Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.

Today I read a paper titled “Quantum simulations of classical random walks and undirected graph connectivity”

The abstract is:
It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case.

In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs.

By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely.

It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.

Today I read a paper titled “An Integrated Heuristic Scheme for Partial Parse Evaluation”

The abstract is:
GLR* is a recently developed robust version of the Generalized LR Parser, that can parse almost ANY input sentence by ignoring unrecognizable parts of the sentence.

On a given input sentence, the parser returns a collection of parses that correspond to maximal, or close to maximal, parsable subsets of the original input.

This paper describes recent work on developing an integrated heuristic scheme for selecting the parse that is deemed “best” from such a collection.

We describe the heuristic measures used and their combination scheme.

Preliminary results from experiments conducted on parsing speech recognized spontaneous speech are also reported..

Today I read a paper titled “Optimal Constructions of Hybrid Algorithms”

The abstract is:
We study on-line strategies for solving problems with hybrid algorithms.

There is a problem Q and w basic algorithms for solving Q.

For some lambda <= w, we have a computer with lambda disjoint memory areas, each of which can be used to run a basic algorithm and store its intermediate results.

In the worst case, only one basic algorithm can solve Q in finite time, and all the other basic algorithms run forever without solving Q.

To solve Q with a hybrid algorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process until Q is solved.

The goal is to solve Q in the least amount of time.

Using competitive ratios to measure the efficiency of a hybrid algorithm, we construct an optimal deterministic hybrid algorithm and an efficient randomized hybrid algorithm.

This resolves an open question on searching with multiple robots posed by Baeza-Yates, Culberson and Rawlins.

We also prove that our randomized algorithm is optimal for lambda = 1, settling a conjecture of Kao, Reif and Tate.

Today I read a paper titled “Differentiated End-to-End Internet Services using a Weighted Proportional Fair Sharing TCP”

The abstract is:
In this document we study the application of weighted proportional fairness to data flows in the Internet.

We let the users set the weights of their connections in order to maximise the utility they get from the network.

When combined with a pricing scheme where connections are billed by weight and time, such a system is known to maximise the total utility of the network.

Our study case is a national Web cache server connected to long distance links.

We propose two ways of weighting TCP connections by manipulating some parameters of the protocol and present results from simulations and prototypes.

We finally discuss how proportional fairness could be used to implement an Internet with differentiated services.

Today I read a paper titled “Detecting and Correcting Speech Repairs”

The abstract is:
Interactive spoken dialog provides many new challenges for spoken language systems.

One of the most critical is the prevalence of speech repairs.

This paper presents an algorithm that detects and corrects speech repairs based on finding the repair pattern.

The repair pattern is built by finding word matches and word replacements, and identifying fragments and editing terms.

Rather than using a set of prebuilt templates, we build the pattern on the fly.

In a fair test, our method, when combined with a statistical model to filter possible repairs, was successful at detecting and correcting 80\% of the repairs, without using prosodic information or a parser..

Today I read a paper titled “Toward Natural Gesture/Speech Control of a Large Display”

The abstract is:
In recent years because of the advances in computer vision research, free hand gestures have been explored as means of human-computer interaction (HCI).

Together with improved speech processing technology it is an important step toward natural multimodal HCI.

However, inclusion of non-predefined continuous gestures into a multimodal framework is a challenging problem.

In this paper, we propose a structured approach for studying patterns of multimodal language in the context of a 2D-display control.

We consider systematic analysis of gestures from observable kinematical primitives to their semantics as pertinent to a linguistic structure.

Proposed semantic classification of co-verbal gestures distinguishes six categories based on their spatio-temporal deixis.

We discuss evolution of a computational framework for gesture and speech integration which was used to develop an interactive testbed (iMAP).

The testbed enabled elicitation of adequate, non-sequential, multimodal patterns in a narrative mode of HCI.

Conducted user studies illustrate significance of accounting for the temporal alignment of gesture and speech parts in semantic mapping.

Furthermore, co-occurrence analysis of gesture/speech production suggests syntactic organization of gestures at the lexical level.

Today I read a paper titled “Random Shuffling to Reduce Disorder in Adaptive Sorting Scheme”

The abstract is:
In this paper we present a random shuffling scheme to apply with adaptive sorting algorithms.

Adaptive sorting algorithms utilize the presortedness present in a given sequence.

We have probabilistically increased the amount of presortedness present in a sequence by using a random shuffling technique that requires little computation.

Theoretical analysis suggests that the proposed scheme can improve the performance of adaptive sorting.

Experimental results show that it significantly reduces the amount of disorder present in a given sequence and improves the execution time of adaptive sorting algorithm as well.

Today I read a paper titled “Connectivity Compression for Irregular Quadrilateral Meshes”

The abstract is:
Applications that require Internet access to remote 3D datasets are often limited by the storage costs of 3D models.

Several compression methods are available to address these limits for objects represented by triangle meshes.

Many CAD and VRML models, however, are represented as quadrilateral meshes or mixed triangle/quadrilateral meshes, and these models may also require compression.

We present an algorithm for encoding the connectivity of such quadrilateral meshes, and we demonstrate that by preserving and exploiting the original quad structure, our approach achieves encodings 30 – 80% smaller than an approach based on randomly splitting quads into triangles.

We present both a code with a proven worst-case cost of 3 bits per vertex (or 2.75 bits per vertex for meshes without valence-two vertices) and entropy-coding results for typical meshes ranging from 0.3 to 0.9 bits per vertex, depending on the regularity of the mesh.

Our method may be implemented by a rule for a particular splitting of quads into triangles and by using the compression and decompression algorithms introduced in [Rossignac99] and [Rossignac&Szymczak99].

We also present extensions to the algorithm to compress meshes with holes and handles and meshes containing triangles and other polygons as well as quads..

Today I read a paper titled “Time and Space Bounds for Reversible Simulation”

The abstract is:
We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation.

Previously, only simulations using exponential time or quadratic space were known.

The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space.

The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the ($\log 3$)th power time with square space required by the Bennett method.

We also give the first general lower bound on the extra storage space required by general reversible simulation.

This lower bound is optimal in that it is achieved by some reversible simulations.

Today I read a paper titled “Document Archiving, Replication and Migration Container for Mobile Web Users”

The abstract is:
With the increasing use of mobile workstations for a wide variety of tasks and associated information needs, and with many variations of available networks, access to data becomes a prime consideration.

This paper discusses issues of workstation mobility and proposes a solution wherein the data structures are accessed in an encapsulated form – through the Portable File System (PFS) wrapper.

The paper discusses an implementation of the Portable File System, highlighting the architecture and commenting upon performance of an experimental system.

Although investigations have been focused upon mobile access of WWW documents, this technique could be applied to any mobile data access situation.

Today I read a paper titled “Memory-Based Lexical Acquisition and Processing”

The abstract is:
Current approaches to computational lexicology in language technology are knowledge-based (competence-oriented) and try to abstract away from specific formalisms, domains, and applications.

This results in severe complexity, acquisition and reusability bottlenecks.

As an alternative, we propose a particular performance-oriented approach to Natural Language Processing based on automatic memory-based learning of linguistic (lexical) tasks.

The consequences of the approach for computational lexicology are discussed, and the application of the approach on a number of lexical acquisition and disambiguation tasks in phonology, morphology and syntax is described..

Today I read a paper titled “A Learning Approach to Natural Language Understanding”

The abstract is:
In this paper we propose a learning paradigm for the problem of understanding spoken language.

The basis of the work is in a formalization of the understanding problem as a communication problem.

This results in the definition of a stochastic model of the production of speech or text starting from the meaning of a sentence.

The resulting understanding algorithm consists in a Viterbi maximization procedure, analogous to that commonly used for recognizing speech..

Today I read a paper titled “A Theory of Universal Artificial Intelligence based on Algorithmic Complexity”

The abstract is:
Decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known.

Solomonoff’s theory of universal induction formally solves the problem of sequence prediction for unknown prior distribution.

We combine both ideas and get a parameterless theory of universal Artificial Intelligence.

We give strong arguments that the resulting AIXI model is the most intelligent unbiased agent possible.

We outline for a number of problem classes, including sequence prediction, strategic games, function minimization, reinforcement and supervised learning, how the AIXI model can formally solve them.

The major drawback of the AIXI model is that it is uncomputable.

To overcome this problem, we construct a modified algorithm AIXI-tl, which is still effectively more intelligent than any other time t and space l bounded agent.

The computation time of AIXI-tl is of the order tx2^l.

Other discussed topics are formal definitions of intelligence order relations, the horizon problem and relations of the AIXI theory to other AI approaches.

Today I read a paper titled “A note on quantum black-box complexity of almost all Boolean functions”

The abstract is:
We show that, for almost all N-variable Boolean functions f, at least N/4-O(\sqrt{N} log N) queries are required to compute f in quantum black-box model with bounded error.

Today I read a paper titled “Chess Pure Strategies are Probably Chaotic”

The abstract is:
It is odd that chess grandmasters often disagree in their analysis of positions, sometimes even of simple ones, and that a grandmaster can hold his own against an powerful analytic machine such as Deep Blue.

The fact that there must exist pure winning strategies for chess is used to construct a control strategy function.

It is then shown that chess strategy is equivalent to an autonomous system of differential equations, and conjectured that the system is chaotic.

If true the conjecture would explain the forenamed peculiarities and would also imply that there cannot exist a static evaluator for chess.

Today I read a paper titled “A Scrollbar-based Visualization for Document Navigation”

The abstract is:
We are interested in questions of improving user control in best-match text-retrieval systems, specifically questions as to whether simple visualizations that nonetheless go beyond the minimal ones generally available can significantly help users.

Recently, we have been investigating ways to help users decide-given a set of documents retrieved by a query-which documents and passages are worth closer examination.

We built a document viewer incorporating a visualization centered around a novel content-displaying scrollbar and color term highlighting, and studied whether the visualization is helpful to non-expert searchers.

Participants’ reaction to the visualization was very positive, while the objective results were inconclusive.

Today I read a paper titled “Towards a computational theory of human daydreaming”

The abstract is:
This paper examines the phenomenon of daydreaming: spontaneously recalling or imagining personal or vicarious experiences in the past or future.

The following important roles of daydreaming in human cognition are postulated: plan preparation and rehearsal, learning from failures and successes, support for processes of creativity, emotion regulation, and motivation.

A computational theory of daydreaming and its implementation as the program DAYDREAMER are presented.

DAYDREAMER consists of 1) a scenario generator based on relaxed planning, 2) a dynamic episodic memory of experiences used by the scenario generator, 3) a collection of personal goals and control goals which guide the scenario generator, 4) an emotion component in which daydreams initiate, and are initiated by, emotional states arising from goal outcomes, and 5) domain knowledge of interpersonal relations and common everyday occurrences.

The role of emotions and control goals in daydreaming is discussed.

Four control goals commonly used in guiding daydreaming are presented: rationalization, failure/success reversal, revenge, and preparation.

The role of episodic memory in daydreaming is considered, including how daydreamed information is incorporated into memory and later used.

An initial version of DAYDREAMER which produces several daydreams (in English) is currently running.

Today I read a paper titled “Average-Case Complexity of Shellsort”

The abstract is:
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p)$ for all $p \leq \log n$.

Using similar arguments, we analyze the average-case complexity of several other sorting algorithms.

Today I read a paper titled “Speech Dialogue with Facial Displays: Multimodal Human-Computer Conversation”

The abstract is:
Human face-to-face conversation is an ideal model for human-computer dialogue.

One of the major features of face-to-face communication is its multiplicity of communication channels that act on multiple modalities.

To realize a natural multimodal dialogue, it is necessary to study how humans perceive information and determine the information to which humans are sensitive.

A face is an independent communication channel that conveys emotional and conversational signals, encoded as facial expressions.

We have developed an experimental system that integrates speech dialogue and facial animation, to investigate the effect of introducing communicative facial expressions as a new modality in human-computer conversation.

Our experiments have shown that facial expressions are helpful, especially upon first contact with the system.

We have also discovered that featuring facial expressions at an early stage improves subsequent interaction..

Today I read a paper titled “Linear probing and graphs”

The abstract is:
Mallows and Riordan showed in 1968 that labeled trees with a small number of inversions are related to labeled graphs that are connected and sparse.

Wright enumerated sparse connected graphs in 1977, and Kreweras related the inversions of trees to the so-called “parking problem” in 1980.

A~combination of these three results leads to a surprisingly simple analysis of the behavior of hashing by linear probing, including higher moments of the cost of successful search.

Today I read a paper titled “Towards Flexible Teamwork”

The abstract is:
Many AI researchers are today striving to build agent teams for complex, dynamic multi-agent domains, with intended applications in arenas such as education, training, entertainment, information integration, and collective robotics.

Unfortunately, uncertainties in these complex, dynamic domains obstruct coherent teamwork.

In particular, team members often encounter differing, incomplete, and possibly inconsistent views of their environment.

Furthermore, team members can unexpectedly fail in fulfilling responsibilities or discover unexpected opportunities.

Highly flexible coordination and communication is key in addressing such uncertainties.

Simply fitting individual agents with precomputed coordination plans will not do, for their inflexibility can cause severe failures in teamwork, and their domain-specificity hinders reusability.

Our central hypothesis is that the key to such flexibility and reusability is providing agents with general models of teamwork.

Agents exploit such models to autonomously reason about coordination and communication, providing requisite flexibility.

Furthermore, the models enable reuse across domains, both saving implementation effort and enforcing consistency.

This article presents one general, implemented model of teamwork, called STEAM.

The basic building block of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b); teamwork in STEAM is based on agents’ building up a (partial) hierarchy of joint intentions (this hierarchy is seen to parallel Grosz & Kraus’s partial SharedPlans, 1996).

Furthermore, in STEAM, team members monitor the team’s and individual members’ performance, reorganizing the team as necessary.

Finally, decision-theoretic communication selectivity in STEAM ensures reduction in communication overheads of teamwork, with appropriate sensitivity to the environmental conditions.

This article describes STEAM’s application in three different complex domains, and presents detailed empirical results.

Today I read a paper titled “Boosting the Differences: A fast Bayesian classifier neural network”

The abstract is:
A Bayesian classifier that up-weights the differences in the attribute values is discussed.

Using four popular datasets from the UCI repository, some interesting features of the network are illustrated.

The network is suitable for classification problems.

Today I read a paper titled “Orderly Spanning Trees with Applications”

The abstract is:
We introduce and study the {\em orderly spanning trees} of plane graphs.

This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs.

Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an {\em orderly pair} for any connected planar graph $G$, consisting of a plane graph $H$ of $G$, and an orderly spanning tree of $H$.

We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder’s Realizer Theorem, (2) the first area-optimal 2-visibility drawing of $G$, and (3) the best known encodings of $G$ with O(1)-time query support.

All algorithms in this paper run in linear time.

Today I read a paper titled “Best-first Model Merging for Hidden Markov Model Induction”

The abstract is:
This report describes a new technique for inducing the structure of Hidden Markov Models from data which is based on the general `model merging’ strategy (Omohundro 1992).

The process begins with a maximum likelihood HMM that directly encodes the training data.

Successively more general models are produced by merging HMM states.

A Bayesian posterior probability criterion is used to determine which states to merge and when to stop generalizing.

The procedure may be considered a heuristic search for the HMM structure with the highest posterior probability.

We discuss a variety of possible priors for HMMs, as well as a number of approximations which improve the computational efficiency of the algorithm.

We studied three applications to evaluate the procedure.

The first compares the merging algorithm with the standard Baum-Welch approach in inducing simple finite-state languages from small, positive-only training samples.

We found that the merging procedure is more robust and accurate, particularly with a small amount of training data.

The second application uses labelled speech data from the TIMIT database to build compact, multiple-pronunciation word models that can be used in speech recognition.

Finally, we describe how the algorithm was incorporated in an operational speech understanding system, where it is combined with neural network acoustic likelihood estimators to improve performance over single-pronunciation word models..

Today I read a paper titled “Collaboration on reference to objects that are not mutually known”

The abstract is:
In conversation, a person sometimes has to refer to an object that is not previously known to the other participant.

We present a plan-based model of how agents collaborate on reference of this sort.

In making a reference, an agent uses the most salient attributes of the referent.

In understanding a reference, an agent determines his confidence in its adequacy as a means of identifying the referent.

To collaborate, the agents use judgment, suggestion, and elaboration moves to refashion an inadequate referring expression..

Today I read a paper titled “Extracting Noun Phrases from Large-Scale Texts: A Hybrid Approach and Its Automatic Evaluation”

The abstract is:
To acquire noun phrases from running texts is useful for many applications, such as word grouping,terminology indexing, etc.

The reported literatures adopt pure probabilistic approach, or pure rule-based noun phrases grammar to tackle this problem.

In this paper, we apply a probabilistic chunker to deciding the implicit boundaries of constituents and utilize the linguistic knowledge to extract the noun phrases by a finite state mechanism.

The test texts are SUSANNE Corpus and the results are evaluated by comparing the parse field of SUSANNE Corpus automatically.

The results of this preliminary experiment are encouraging..

Today I read a paper titled “Identifying Discourse Markers in Spoken Dialog”

The abstract is:
In this paper, we present a method for identifying discourse marker usage in spontaneous speech based on machine learning.

Discourse markers are denoted by special POS tags, and thus the process of POS tagging can be used to identify discourse markers.

By incorporating POS tagging into language modeling, discourse markers can be identified during speech recognition, in which the timeliness of the information can be used to help predict the following words.

We contrast this approach with an alternative machine learning approach proposed by Litman (1996).

This paper also argues that discourse markers can be used to help the hearer predict the role that the upcoming utterance plays in the dialog.

Thus discourse markers should provide valuable evidence for automatic dialog act prediction..

Today I read a paper titled “Distorted English Alphabet Identification : An application of Difference Boosting Algorithm”

The abstract is:
The difference-boosting algorithm is used on letters dataset from the UCI repository to classify distorted raster images of English alphabets.

In contrast to rather complex networks, the difference-boosting is found to produce comparable or better classification efficiency on this complex problem.

Today I read a paper titled “Knowledge and common knowledge in a distributed environment”

The abstract is:
Reasoning about knowledge seems to play a fundamental role in distributed systems.

Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols.

Communication in a distributed system can be viewed as the act of transforming the system’s state of knowledge.

This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems.

We argue that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols.

In particular, distributed knowledge corresponds to knowledge that is “distributed” among the members of the group, while common knowledge corresponds to a fact being “publicly known”.

The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated.

Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained.

A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.

Today I read a paper titled “A Market-Oriented Programming Environment and its Application to Distributed Multicommodity Flow Problems”

The abstract is:
Market price systems constitute a well-understood class of mechanisms that under certain conditions provide effective decentralization of decision making with minimal communication overhead.

In a market-oriented programming approach to distributed problem solving, we derive the activities and resource allocations for a set of computational agents by computing the competitive equilibrium of an artificial economy.

WALRAS provides basic constructs for defining computational market structures, and protocols for deriving their corresponding price equilibria.

In a particular realization of this approach for a form of multicommodity flow problem, we see that careful construction of the decision process according to economic principles can lead to efficient distributed resource allocation, and that the behavior of the system can be meaningfully analyzed in economic terms..

Today I read a paper titled “General Theory of Image Normalization”

The abstract is:
We give a systematic, abstract formulation of the image normalization method as applied to a general group of image transformations, and then illustrate the abstract analysis by applying it to the hierarchy of viewing transformations of a planar object.

Today I read a paper titled “Syntactic-Head-Driven Generation”

The abstract is:
The previously proposed semantic-head-driven generation methods run into problems if none of the daughter constituents in the syntacto-semantic rule schemata of a grammar fits the definition of a semantic head given in Shieber et al.

1990.

This is the case for the semantic analysis rules of certain constraint-based semantic representations, e.g.

Underspecified Discourse Representation Structures (UDRSs) (Frank/Reyle 1992).

Since head-driven generation in general has its merits, we simply return to a syntactic definition of `head’ and demonstrate the feasibility of syntactic-head-driven generation.

In addition to its generality, a syntactic-head-driven algorithm provides a basis for a logically well-defined treatment of the movement of (syntactic) heads, for which only ad-hoc solutions existed, so far..

Today I read a paper titled “Complexity limitations on quantum computation”

The abstract is:
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation.

We show several results for the probabilistic quantum class BQP.

1.

BQP is low for PP, i.e., PP^BQP=PP.

2.

There exists a relativized world where P=BQP and the polynomial-time hierarchy is infinite.

3.

There exists a relativized world where BQP does not have complete sets.

4.

There exists a relativized world where P=BQP but P is not equal to UP intersect coUP and one-way functions exist.

This gives a relativized answer to an open question of Simon.

Today I read a paper titled “Character design for soccer commmentary”

The abstract is:
In this paper we present early work on an animated talking head commentary system called {\bf Byrne}\footnote{David Byrne is the lead singer of the Talking Heads.}.

The goal of this project is to develop a system which can take the output from the RoboCup soccer simulator, and generate appropriate affective speech and facial expressions, based on the character’s personality, emotional state, and the state of play.

Here we describe a system which takes pre-analysed simulator output as input, and which generates text marked-up for use by a speech generator and a face animation system.

We make heavy use of inter-system standards, so that future versions of Byrne will be able to take advantage of advances in the technologies that it incorporates.

Today I read a paper titled “Simple and Superlattice Turing Patterns in Reaction-Diffusion Systems: Bifurcation, Bistability, and Parameter Collapse”

The abstract is:
This paper investigates the competition between both simple (e.g.

stripes, hexagons) and “superlattice” (super squares, super hexagons) Turing patterns in two-component reaction-diffusion systems.

“Superlattice” patterns are formed from eight or twelve Fourier modes, and feature structure at two different length scales.

Using perturbation theory, we derive simple analytical expressions for the bifurcation equation coefficients on both rhombic and hexagonal lattices.

These expressions show that, no matter how complicated the reaction kinectics, the nonlinear reaction terms reduce to just four effective terms within the bifurcation equation coefficients.

Moreover, at the hexagonal degeneracy — when the quadratic term in the hexagonal bifurcation equation disappears — the number of effective system parameters drops to two, allowing a complete characterization of the possible bifurcation results at this degeneracy.

The general results are then applied to specific model equations, to investigate the stability of different patterns within those models.

Today I read a paper titled “Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets”

The abstract is:
This paper introduces new algorithms and data structures for quick counting for machine learning datasets.

We focus on the counting task of constructing contingency tables, but our approach is also applicable to counting the number of records in a dataset that match conjunctive queries.

Subject to certain assumptions, the costs of these operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table.

We provide a very sparse data structure, the ADtree, to minimize memory use.

We provide analytical worst-case bounds for this structure for several models of data distribution.

We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a) using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves.

We show how the ADtree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADtree methods against traditional direct counting approaches.

We also discuss the possible uses of ADtrees in other machine learning methods, and discuss the merits of ADtrees in comparison with alternative representations such as kd-trees, R-trees and Frequent Sets.

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.

Today I read a paper titled “MOO: A Methodology for Online Optimization through Mining the Offline Optimum”

The abstract is:
Ports, warehouses and courier services have to decide online how an arriving task is to be served in order that cost is minimized (or profit maximized).

These operators have a wealth of historical data on task assignments; can these data be mined for knowledge or rules that can help the decision-making? MOO is a novel application of data mining to online optimization.

The idea is to mine (logged) expert decisions or the offline optimum for rules that can be used for online decisions.

It requires little knowledge about the task distribution and cost structure, and is applicable to a wide range of problems.

This paper presents a feasibility study of the methodology for the well-known k-server problem.

Experiments with synthetic data show that optimization can be recast as classification of the optimum decisions; the resulting heuristic can achieve the optimum for strong request patterns, consistently outperforms other heuristics for weak patterns, and is robust despite changes in cost model.

Today I read a paper titled “Designing an interface to optimize reading with small display windows”

The abstract is:
The electronic presentation of text in small display windows is mushrooming.

In the present paper, four ways of presenting text in a small display window were examined and compared to a Normal Page condition: rapid serial visual presentation (RSVP), RSVP with a Completion Meter, Sentence-by-Sentence presentation, and Sentence-by-Sentence presentation with a Completion Meter.

Dependent measures were reading efficiency – speed and comprehension – and preference.

For designers of hardware or software with small display windows, the results suggest the following: (1) Though RSVP is disliked by readers, the present methods of allowing self-pacing and regressions in RSVP, unlike earlier tested methods, are efficient and feasible.

(2) Slower reading in RSVP should be achieved by increasing pauses between sentences or by repeating sentences, not by decreasing the within-sentence rate.

(3) Completion meters do not interfere with performance, and are usually preferred.

(4) The space-saving Sentence-by-Sentence format is as efficient and as preferred as the Normal Page format.

Today I read a paper titled “Software Agents: Completing Patterns and Constructing User Interfaces”

The abstract is:
To support the goal of allowing users to record and retrieve information, this paper describes an interactive note-taking system for pen-based computers with two distinctive features.

First, it actively predicts what the user is going to write.

Second, it automatically constructs a custom, button-box user interface on request.

The system is an example of a learning-apprentice software- agent.

A machine learning component characterizes the syntax and semantics of the user’s information.

A performance system uses this learned information to generate completion strings and construct a user interface.

Description of Online Appendix: People like to record information.

Doing this on paper is initially efficient, but lacks flexibility.

Recording information on a computer is less efficient but more powerful.

In our new note taking softwre, the user records information directly on a computer.

Behind the interface, an agent acts for the user.

To help, it provides defaults and constructs a custom user interface.

The demonstration is a QuickTime movie of the note taking agent in action.

The file is a binhexed self-extracting archive.

Macintosh utilities for binhex are available from mac.archive.umich.edu.

QuickTime is available from ftp.apple.com in the dts/mac/sys.soft/quicktime..

Today I read a paper titled “Virtual Kathakali : Gesture Driven Metamorphosis”

The abstract is:
Training in motor skills such as athletics, dance, or gymnastics is not possible today except in the direct presence of the coach/instructor.

This paper describes a computer vision based gesture recognition system which is used to metamorphose the user into a Virtual person, e.g.

as a Kathakali dancer, which is graphically recreated at a near or diatant location.

Thus this can be seen by an off-site coach using low-bandwidth joint-motion data which permits real time animation.

The metamorphosis involves altering the appearance and identity of the user and also creating a specific environment possibly in interaction with other virtual creatures.

A robust vision module is used to identify the user, based on very simple binary image processing in real time which also manages to resolve self-occlusion, correct for clothing/colour and other variations among users.

Gestures are identified by locating key points at the shoulder, elbow and wrist joint, which are then recreated in an articulated humanoid model, which in this instance, representes a Kathakali dancer in elaborate traditional dress.

Unlike glove based or other and movement tracking systems, this application requires the user to wear no hardwire devices and is aimed at making gesture tracking simpler, cheaper, and more user friendly.