Archives for 2008

Today I read a paper titled “Artificial Agents and Speculative Bubbles”

The abstract is:
Pertaining to Agent-based Computational Economics (ACE), this work presents two models for the rise and downfall of speculative bubbles through an exchange price fixing based on double auction mechanisms.

The first model is based on a finite time horizon context, where the expected dividends decrease along time.

The second model follows the {\em greater fool} hypothesis; the agent behaviour depends on the comparison of the estimated risk with the greater fool’s.

Simulations shed some light on the influent parameters and the necessary conditions for the apparition of speculative bubbles in an asset market within the considered framework.

Today I read a paper titled “Difficulties in the Implementation of Quantum Computers”

The abstract is:
This paper reviews various engineering hurdles facing the field of quantum computing.

Specifically, problems related to decoherence, state preparation, error correction, and implementability of gates are considered.

Today I read a paper titled “Using Propagation for Solving Complex Arithmetic Constraints”

The abstract is:
Solving a system of nonlinear inequalities is an important problem for which conventional numerical analysis has no satisfactory method.

With a box-consistency algorithm one can compute a cover for the solution set to arbitrarily close approximation.

Because of difficulties in the use of propagation for complex arithmetic expressions, box consistency is computed with interval arithmetic.

In this paper we present theorems that support a simple modification of propagation that allows complex arithmetic expressions to be handled efficiently.

The version of box consistency that is obtained in this way is stronger than when interval arithmetic is used.

Today I read a paper titled “How far will you walk to find your shortcut: Space Efficient Synopsis Construction Algorithms”

The abstract is:
In this paper we consider the wavelet synopsis construction problem without the restriction that we only choose a subset of coefficients of the original data.

We provide the first near optimal algorithm.

We arrive at the above algorithm by considering space efficient algorithms for the restricted version of the problem.

In this context we improve previous algorithms by almost a linear factor and reduce the required space to almost linear.

Our techniques also extend to histogram construction, and improve the space-running time tradeoffs for V-Opt and range query histograms.

We believe the idea applies to a broad range of dynamic programs and demonstrate it by showing improvements in a knapsack-like setting seen in construction of Extended Wavelets.

Today I read a paper titled “Characterizing Video Responses in Social Networks”

The abstract is:
Video sharing sites, such as YouTube, use video responses to enhance the social interactions among their users.

The video response feature allows users to interact and converse through video, by creating a video sequence that begins with an opening video and followed by video responses from other users.

Our characterization is over 3.4 million videos and 400,000 video responses collected from YouTube during a 7-day period.

We first analyze the characteristics of the video responses, such as popularity, duration, and geography.

We then examine the social networks that emerge from the video response interactions.

Today I read a paper titled “Petascale Computational Systems”

The abstract is:
Computational science is changing to be data intensive.

Super-Computers must be balanced systems; not just CPU farms but also petascale IO and networking arrays.

Anyone building CyberInfrastructure should allocate resources to support a balanced Tier-1 through Tier-3 design.

Today I read a paper titled “Voice-controlled Debugging of Spreadsheets”

The abstract is:
Developments in Mobile Computing are putting pressure on the software industry to research new modes of interaction that do not rely on the traditional keyboard and mouse combination.

Computer users suffering from Repetitive Strain Injury also seek an alternative to keyboard and mouse devices to reduce suffering in wrist and finger joints.

Voice-control is an alternative approach to spreadsheet development and debugging that has been researched and used successfully in other domains.

While voice-control technology for spreadsheets is available its effectiveness has not been investigated.

This study is the first to compare the performance of a set of expert spreadsheet developers that debugged a spreadsheet using voice-control technology and another set that debugged the same spreadsheet using keyboard and mouse.

The study showed that voice, despite its advantages, proved to be slower and less accurate.

However, it also revealed ways in which the technology might be improved to redress this imbalance.

Today I read a paper titled “Simple Recursive Games”

The abstract is:
We define the class of “simple recursive games”.

A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but disallow moves of chance.

We study the complexity of solving simple recursive games and obtain an almost-linear time comparison-based algorithm for computing an equilibrium of such a game.

The existence of a linear time comparison-based algorithm remains an open problem.

Today I read a paper titled “Chaos in computer performance”

The abstract is:
Modern computer microprocessors are composed of hundreds of millions of transistors that interact through intricate protocols.

Their performance during program execution may be highly variable and present aperiodic oscillations.

In this paper, we apply current nonlinear time series analysis techniques to the performances of modern microprocessors during the execution of prototypical programs.

Our results present pieces of evidence strongly supporting that the high variability of the performance dynamics during the execution of several programs display low-dimensional deterministic chaos, with sensitivity to initial conditions comparable to textbook models.

Taken together, these results show that the instantaneous performances of modern microprocessors constitute a complex (or at least complicated) system and would benefit from analysis with modern tools of nonlinear and complexity science.

Today I read a paper titled “Multirobot rendezvous with visibility sensors in nonconvex environments”

The abstract is:
This paper presents a coordination algorithm for mobile autonomous robots.

Relying upon distributed sensing the robots achieve rendezvous, that is, they move to a common location.

Each robot is a point mass moving in a nonconvex environment according to an omnidirectional kinematic model.

Each robot is equipped with line-of-sight limited-range sensors, i.e., a robot can measure the relative position of any object (robots or environment boundary) if and only if the object is within a given distance and there are no obstacles in-between.

The algorithm is designed using the notions of robust visibility, connectivity-preserving constraint sets, and proximity graphs.

Simulations illustrate the theoretical results on the correctness of the proposed algorithm, and its performance in asynchronous setups and with sensor measurement and control errors.

Today I read a paper titled “Digital watermarking in the singular vector domain”

The abstract is:
Many current watermarking algorithms insert data in the spatial or transform domains like the discrete cosine, the discrete Fourier, and the discrete wavelet transforms.

In this paper, we present a data-hiding algorithm that exploits the singular value decomposition (SVD) representation of the data.

We compute the SVD of the host image and the watermark and embed the watermark in the singular vectors of the host image.

The proposed method leads to an imperceptible scheme for digital images, both in grey scale and color and is quite robust against attacks like noise and JPEG compression.

Today I read a paper titled “Can a Computer Laugh ?”

The abstract is:
A computer model of “a sense of humour” suggested previously [arXiv:0711.2058,0711.2061], relating the humorous effect with a specific malfunction in information processing, is given in somewhat different exposition.

Psychological aspects of humour are elaborated more thoroughly.

The mechanism of laughter is formulated on the more general level.

Detailed discussion is presented for the higher levels of information processing, which are responsible for a perception of complex samples of humour.

Development of a sense of humour in the process of evolution is discussed.

Today I read a paper titled “Swarm-Based Spatial Sorting”

The abstract is:
Purpose: To present an algorithm for spatially sorting objects into an annular structure.

Design/Methodology/Approach: A swarm-based model that requires only stochastic agent behaviour coupled with a pheromone-inspired “attraction-repulsion” mechanism.

Findings: The algorithm consistently generates high-quality annular structures, and is particularly powerful in situations where the initial configuration of objects is similar to those observed in nature.

Research limitations/implications: Experimental evidence supports previous theoretical arguments about the nature and mechanism of spatial sorting by insects.

Practical implications: The algorithm may find applications in distributed robotics.

Originality/value: The model offers a powerful minimal algorithmic framework, and also sheds further light on the nature of attraction-repulsion algorithms and underlying natural processes.

Today I read a paper titled “Mathematical Structure of Quantum Decision Theory”

The abstract is:
One of the most complex systems is the human brain whose formalized functioning is characterized by decision theory.

We present a “Quantum Decision Theory” of decision making, based on the mathematical theory of separable Hilbert spaces.

This mathematical structure captures the effect of superposition of composite prospects, including many incorporated intentions, which allows us to explain a variety of interesting fallacies and anomalies that have been reported to particularize the decision making of real human beings.

The theory describes entangled decision making, non-commutativity of subsequent decisions, and intention interference of composite prospects.

We demonstrate how the violation of the Savage’s sure-thing principle (disjunction effect) can be explained as a result of the interference of intentions, when making decisions under uncertainty.

The conjunction fallacy is also explained by the presence of the interference terms.

We demonstrate that all known anomalies and paradoxes, documented in the context of classical decision theory, are reducible to just a few mathematical archetypes, all of which finding straightforward explanations in the frame of the developed quantum approach.

Today I read a paper titled “Self-Organizing Multilayered Neural Networks of Optimal Complexity”

The abstract is:
The principles of self-organizing the neural networks of optimal complexity is considered under the unrepresentative learning set.

The method of self-organizing the multi-layered neural networks is offered and used to train the logical neural networks which were applied to the medical diagnostics.

Today I read a paper titled “Quantum search algorithms”

The abstract is:
We review some of quantum algorithms for search problems: Grover’s search algorithm, its generalization to amplitude amplification, the applications of amplitude amplification to various problems and the recent quantum algorithms based on quantum walks.

Today I read a paper titled “Optimal Scheduling of Peer-to-Peer File Dissemination”

The abstract is:
Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are increasingly used for disseminating potentially large files from a server to many end users via the Internet.

The key idea is to divide the file into many equally-sized parts and then let users download each part (or, for network coding based systems such as Avalanche, linear combinations of the parts) either from the server or from another user who has already downloaded it.

However, their performance evaluation has typically been limited to comparing one system relative to another and typically been realized by means of simulation and measurements.

In contrast, we provide an analytic performance analysis that is based on a new uplink-sharing version of the well-known broadcasting problem.

Assuming equal upload capacities, we show that the minimal time to disseminate the file is the same as for the simultaneous send/receive version of the broadcasting problem.

For general upload capacities, we provide a mixed integer linear program (MILP) solution and a complementary fluid limit solution.

We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system.

We also investigate the performance of a decentralized strategy, providing evidence that the performance of necessarily decentralized P2P file dissemination systems should be close to this bound and therefore that it is useful in practice.

Today I read a paper titled “Novelty Detection on a Mobile Robot Using Habituation”

The abstract is:
In this paper a novelty filter is introduced which allows a robot operating in an un structured environment to produce a self-organised model of its surroundings and to detect deviations from the learned model.

The environment is perceived using the rob ot’s 16 sonar sensors.

The algorithm produces a novelty measure for each sensor scan relative to the model it has learned.

This means that it highlights stimuli which h ave not been previously experienced.

The novelty filter proposed uses a model of hab ituation.

Habituation is a decrement in behavioural response when a stimulus is pre sented repeatedly.

Robot experiments are presented which demonstrate the reliable o peration of the filter in a number of environments.

Today I read a paper titled “A Real-Time Novelty Detector for a Mobile Robot”

The abstract is:
Recognising new or unusual features of an environment is an ability which is potentially very useful to a robot.

This paper demonstrates an algorithm which achieves this task by learning an internal representation of `normality’ from sonar scans taken as a robot explores the environment.

This model of the environment is used to evaluate the novelty of each sonar scan presented to it with relation to the model.

Stimuli which have not been seen before, and therefore have more novelty, are highlighted by the filter.

The filter has the ability to forget about features which have been learned, so that stimuli which are seen only rarely recover their response over time.

A number of robot experiments are presented which demonstrate the operation of the filter.

Today I read a paper titled “Face Recognition Based on Polar Frequency Features”

The abstract is:
A novel biologically motivated face recognition algorithm based on polar frequency is presented.

Polar frequency descriptors are extracted from face images by Fourier-Bessel transform (FBT).

Next, the Euclidean distance between all images is computed and each image is now represented by its dissimilarity to the other images.

A Pseudo-Fisher Linear Discriminant was built on this dissimilarity space.

The performance of Discrete Fourier transform (DFT) descriptors, and a combination of both feature types was also evaluated.

The algorithms were tested on a 40- and 1196-subjects face database (ORL and FERET, respectively).

With 5 images per subject in the training and test datasets, error rate on the ORL database was 3.8, 1.25 and 0.2% for the FBT, DFT, and the combined classifier, respectively, as compared to 2.6% achieved by the best previous algorithm.

The most informative polar frequency features were concentrated at low-to-medium angular frequencies coupled to low radial frequencies.

On the FERET database, where an affine normalization pre-processing was applied, the FBT algorithm outperformed only the PCA in a rank recognition test.

However, it achieved performance comparable to state-of-the-art methods when evaluated by verification tests.

These results indicate the high informative value of the polar frequency content of face images in relation to recognition and verification tasks, and that the Cartesian frequency content can complement information about the subjects’ identity, but possibly only when the images are not pre-normalized.

Possible implications for human face recognition are discussed.

Today I read a paper titled “Convexity Analysis of Snake Models Based on Hamiltonian Formulation”

The abstract is:
This paper presents a convexity analysis for the dynamic snake model based on the Potential Energy functional and the Hamiltonian formulation of the classical mechanics.

First we see the snake model as a dynamical system whose singular points are the borders we seek.

Next we show that a necessary condition for a singular point to be an attractor is that the energy functional is strictly convex in a neighborhood of it, that means, if the singular point is a local minimum of the potential energy.

As a consequence of this analysis, a local expression relating the dynamic parameters and the rate of convergence arises.

Such results link the convexity analysis of the potential energy and the dynamic snake model and point forward to the necessity of a physical quantity whose convexity analysis is related to the dynamic and which incorporate the velocity space.

Such a quantity is exactly the (conservative) Hamiltonian of the system.