Justin Lloyd's Thinkering

Today I read a paper titled “Nearly optimal exploration-exploitation decision thresholds”

The abstract is:
While in general trading off exploration and exploitation in reinforcement learning is hard, under some formulations relatively simple solutions exist.

Optimal decision thresholds for the multi-armed bandit problem, one for the infinite horizon discounted reward case and one for the finite horizon undiscounted reward case are derived, which make the link between the reward horizon, uncertainty and the need for exploration explicit.

From this result follow two practical approximate algorithms, which are illustrated experimentally.

Today I read a paper titled “How to Simulate Billiards and Similar Systems”

The abstract is:
An N-component continuous-time dynamic system is considered whose components evolve autonomously all the time except for in discrete asynchronous instances of pairwise interactions.

Examples include chaotically colliding billiard balls and combat models.

A new efficient serial event-driven algorithm is described for simulating such systems.

Rather than maintaining and updating the global state of the system, the algorithm tries to examine only essential events, i.e., component interactions.

The events are processed in a non-decreasing order of time; new interactions are scheduled on the basis of the examined interactions using preintegrated equations of the evolutions of the components.

If the components are distributed uniformly enough in the evolution space, so that this space can be subdivided into small sectors such that only O(1) sectors and O(1)$components are in the neighborhood of a sector, then the algorithm spends time O (log N) for processing an event which is the asymptotical minimum.

The algorithm uses a simple strategy for handling data: only two states are maintained for each simulated component.

Fast data access in this strategy assures the practical efficiency of the algorithm.

It works noticeably faster than other algorithms proposed for this model.

Key phrases: collision detection, dense packing, molecular dynamics, hard spheres, granular flow .

Today I read a paper titled “The `Face on Mars’: a photographic approach for the search of signs of past civilizations from a macroscopic point of view, factoring long-term erosion in image reconstruction”

The abstract is:
This short article presents an alternative view of high resolution imaging from various sources with the aim of the discovery of potential sites of archaeological importance, or sites that exhibit `anomalies’ such that they may merit closer inspection and analysis.

It is conjectured, and to a certain extent demonstrated here, that it is possible for advanced civilizations to factor in erosion by natural processes into a large scale design so that main features be preserved even with the passage of millions of years.

Alternatively viewed, even without such intent embedded in a design left for posterity, it is possible that a gigantic construction may naturally decay in such a way that even cataclysmic (massive) events may leave sufficient information intact with the passage of time, provided one changes the point of view from high resolution images to enhanced blurred renderings of the sites in question.

Today I read a paper titled “Clustering Techniques for Marbles Classification”

The abstract is:
Automatic marbles classification based on their visual appearance is an important industrial issue.

However, there is no definitive solution to the problem mainly due to the presence of randomly distributed high number of different colours and its subjective evaluation by the human expert.

In this paper we present a study of segmentation techniques, we evaluate they overall performance using a training set and standard quality measures and finally we apply different clustering techniques to automatically classify the marbles.

KEYWORDS: Segmentation, Clustering, Quadtrees, Learning Vector Quantization (LVQ), Simulated Annealing (SA).

Today I read a paper titled “Quantum Algorithm Processor For Finding Exact Divisors”

The abstract is:
Wiring diagrams are given for a quantum algorithm processor in CMOS to compute, in parallel, all divisors of an n-bit integer.

Lines required in a wiring diagram are proportional to n.

Execution time is proportional to the square of n.

Today I read a paper titled “Locally connected spanning trees on graphs”

The abstract is:
A locally connected spanning tree of a graph $G$ is a spanning tree $T$ of $G$ such that the set of all neighbors of $v$ in $T$ induces a connected subgraph of $G$ for every $v\in V(G)$.

The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.

Today I read a paper titled “On the Design of Perceptual MPEG-Video Encryption Algorithms”

The abstract is:
In this paper, some existing perceptual encryption algorithms of MPEG videos are reviewed and some problems, especially security defects of two recently proposed MPEG-video perceptual encryption schemes, are pointed out.

Then, a simpler and more effective design is suggested, which selectively encrypts fixed-length codewords (FLC) in MPEG-video bitstreams under the control of three perceptibility factors.

The proposed design is actually an encryption configuration that can work with any stream cipher or block cipher.

Compared with the previously-proposed schemes, the new design provides more useful features, such as strict size-preservation, on-the-fly encryption and multiple perceptibility, which make it possible to support more applications with different requirements.

In addition, four different measures are suggested to provide better security against known/chosen-plaintext attacks.

Today I read a paper titled “The Bayesian Decision Tree Technique with a Sweeping Strategy”

The abstract is:
The uncertainty of classification outcomes is of crucial importance for many safety critical applications including, for example, medical diagnostics.

In such applications the uncertainty of classification can be reliably estimated within a Bayesian model averaging technique that allows the use of prior information.

Decision Tree (DT) classification models used within such a technique gives experts additional information by making this classification scheme observable.

The use of the Markov Chain Monte Carlo (MCMC) methodology of stochastic sampling makes the Bayesian DT technique feasible to perform.

However, in practice, the MCMC technique may become stuck in a particular DT which is far away from a region with a maximal posterior.

Sampling such DTs causes bias in the posterior estimates, and as a result the evaluation of classification uncertainty may be incorrect.

In a particular case, the negative effect of such sampling may be reduced by giving additional prior information on the shape of DTs.

In this paper we describe a new approach based on sweeping the DTs without additional priors on the favorite shape of DTs.

The performances of Bayesian DT techniques with the standard and sweeping strategies are compared on a synthetic data as well as on real datasets.

Quantitatively evaluating the uncertainty in terms of entropy of class posterior probabilities, we found that the sweeping strategy is superior to the standard strategy.

Today I read a paper titled “Compact Representations by Finite-State Transducers”

The abstract is:
Finite-state transducers give efficient representations of many Natural Language phenomena.

They allow to account for complex lexicon restrictions encountered, without involving the use of a large set of complex rules difficult to analyze.

We here show that these representations can be made very compact, indicate how to perform the corresponding minimization, and point out interesting linguistic side-effects of this operation..

Today I read a paper titled “Von Neumann Quantum Processors”

The abstract is:
Most modern classical processors support so-called von Neumann architecture with program and data registers.

In present work is revisited similar approach to models of quantum processors.

Deterministic programmable quantum gate arrays are considered as an example.

They are also called von Neumann quantum processors here and use conditional quantum dynamics.

Such devices have some problems with universality, but consideration of hybrid quantum processors, i.e., models with both continuous and discrete quantum variables resolves the problems.

It is also discussed comparison of such a model of quantum processors with more traditional approach.

Today I read a paper titled “Packrat Parsing: Simple, Powerful, Lazy, Linear Time”

The abstract is:
Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language.

A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time.

Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support.

This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing.

Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change.

This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.