Justin Lloyd's Thinkering

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..