Archives for 2008

Today I read a paper titled “Iterative Rounding for the Closest String Problem”

The abstract is:
The closest string problem is an NP-hard problem, whose task is to find a string that minimizes maximum Hamming distance to a given set of strings.

This can be reduced to an integer program (IP).

However, to date, there exists no known polynomial-time algorithm for IP.

In 2004, Meneses et al.

introduced a branch-and-bound (B & B) method for solving the IP problem.

Their algorithm is not always efficient and has the exponential time complexity.

In the paper, we attempt to solve efficiently the IP problem by a greedy iterative rounding technique.

The proposed algorithm is polynomial time and much faster than the existing B & B IP for the CSP.

If the number of strings is limited to 3, the algorithm is provably at most 1 away from the optimum.

The empirical results show that in many cases we can find an exact solution.

Even though we fail to find an exact solution, the solution found is very close to exact solution.

Today I read a paper titled “Avoiding the Bloat with Stochastic Grammar-based Genetic Programming”

The abstract is:
The application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the search space, and consequently by the computer resources needed.

In many cases, the extreme demand for memory and CPU is due to the massive growth of non-coding segments, the introns.

The paper presents a new program evolution framework which combines distribution-based evolution in the PBIL spirit, with grammar-based genetic programming; the information is stored as a probability distribution on the gra mmar rules, rather than in a population.

Experiments on a real-world like problem show that this approach gives a practical solution to the problem of intron growth.

Today I read a paper titled “The concept of strong and weak virtual reality”

The abstract is:
We approach the virtual reality phenomenon by studying its relationship to set theory, and we investigate the case where this is done using the wellfoundedness property of sets.

Our hypothesis is that non-wellfounded sets (hypersets) give rise to a different quality of virtual reality than do familiar wellfounded sets.

We initially provide an alternative approach to virtual reality based on Sommerhoff’s idea of first and second order self-awareness; both categories of self-awareness are considered as necessary conditions for consciousness in terms of higher cognitive functions.

We then introduce a representation of first and second order self-awareness through sets, and assume that these sets, which we call events, originally form a collection of wellfounded sets.

Strong virtual reality characterizes virtual reality environments which have the limited capacity to create only events associated with wellfounded sets.

In contrast, the more general concept of weak virtual reality characterizes collections of virtual reality mediated events altogether forming an entirety larger than any collection of wellfounded sets.

By giving reference to Aczel’s hyperset theory we indicate that this definition is not empty, because hypersets encompass wellfounded sets already.

Moreover, we argue that weak virtual reality could be realized in human history through continued progress in computer technology.

Finally, we reformulate our characterization into a more general framework, and use Baltag’s Structural Theory of Sets (STS) to show that within this general hyperset theory Sommerhoff’s first and second order self-awareness as well as both concepts of virtual reality admit a consistent mathematical representation.

Today I read a paper titled “On the Submodularity of Influence in Social Networks”

The abstract is:
We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks.

A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship.

A simple way to model the diffusion of ideas, innovative behavior, or “word-of-mouth” effects on such a graph is to consider an increasing process of “infected” (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value.

Such a model was introduced by KKT in \cite{KeKlTa:03,KeKlTa:05} where the authors also impose several natural assumptions: the threshold values are (uniformly) random; and the activation functions are monotone and submodular.

For an initial set of active nodes $S$, let $\sigma(S)$ denote the expected number of active nodes at termination.

Here we prove a conjecture of KKT: we show that the function $\sigma(S)$ is submodular under the assumptions above.

We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination.

Today I read a paper titled “Augmented Segmentation and Visualization for Presentation Videos”

The abstract is:
We investigate methods of segmenting, visualizing, and indexing presentation videos by separately considering audio and visual data.

The audio track is segmented by speaker, and augmented with key phrases which are extracted using an Automatic Speech Recognizer (ASR).

The video track is segmented by visual dissimilarities and augmented by representative key frames.

An interactive user interface combines a visual representation of audio, video, text, and key frames, and allows the user to navigate a presentation video.

We also explore clustering and labeling of speaker data and present preliminary results.

Today I read a paper titled “Solving Multiclass Learning Problems via Error-Correcting Output Codes”

The abstract is:
Multiclass learning problems involve finding a definition for an unknown function f(x) whose range is a discrete set containing k &gt 2 values (i.e., k “classes”).

The definition is acquired by studying collections of training examples of the form [x_i, f (x_i)].

Existing approaches to multiclass learning problems include direct application of multiclass algorithms such as the decision-tree algorithms C4.5 and CART, application of binary concept learning algorithms to learn individual binary functions for each of the k classes, and application of binary concept learning algorithms with distributed output representations.

This paper compares these three approaches to a new technique in which error-correcting codes are employed as a distributed output representation.

We show that these output representations improve the generalization performance of both C4.5 and backpropagation on a wide range of multiclass learning tasks.

We also demonstrate that this approach is robust with respect to changes in the size of the training sample, the assignment of distributed representations to particular classes, and the application of overfitting avoidance techniques such as decision-tree pruning.

Finally, we show that—like the other methods—the error-correcting code technique can provide reliable class probability estimates.

Taken together, these results demonstrate that error-correcting output codes provide a general-purpose method for improving the performance of inductive learning programs on multiclass problems..

Today I read a paper titled “Linear versus Non-linear Acquisition of Step-Functions”

The abstract is:
We address in this paper the following two closely related problems: 1.

How to represent functions with singularities (up to a prescribed accuracy) in a compact way? 2.

How to reconstruct such functions from a small number of measurements? The stress is on a comparison of linear and non-linear approaches.

As a model case we use piecewise-constant functions on [0,1], in particular, the Heaviside jump function.

Considered as a curve in the Hilbert space, it is completely characterized by the fact that any two its disjoint chords are orthogonal.

We reinterpret this fact in a context of step-functions in one or two variables.

Next we study the limitations on representability and reconstruction of piecewise-constant functions by linear and semi-linear methods.

Our main tools in this problem are Kolmogorov’s n-width and entropy, as well as Temlyakov’s (N,m)-width.

On the positive side, we show that a very accurate non-linear reconstruction is possible.

It goes through a solution of certain specific non-linear systems of algebraic equations.

We discuss the form of these systems and methods of their solution, stressing their relation to Moment Theory and Complex Analysis.

Finally, we informally discuss two problems in Computer Imaging which are parallel to the problems 1 and 2 above: compression of still images and video-sequences on one side, and image reconstruction from indirect measurement (for example, in Computer Tomography), on the other.

Today I read a paper titled “Safe cooperative robot dynamics on graphs”

The abstract is:
This paper initiates the use of vector fields to design, optimize, and implement reactive schedules for safe cooperative robot patterns on planar graphs.

We consider Automated Guided Vehicles (AGV’s) operating upon a predefined network of pathways.

In contrast to the case of locally Euclidean configuration spaces, regularization of collisions is no longer a local procedure, and issues concerning the global topology of configuration spaces must be addressed.

The focus of the present inquiry is the achievement of safe, efficient, cooperative patterns in the simplest nontrivial example (a pair of robots on a Y-network) by means of a state-event heirarchical controller.

Today I read a paper titled “Selfish vs. Unselfish Optimization of Network Creation”

The abstract is:
We investigate several variants of a network creation model: a group of agents builds up a network between them while trying to keep the costs of this network small.

The cost function consists of two addends, namely (i) a constant amount for each edge an agent buys and (ii) the minimum number of hops it takes sending messages to other agents.

Despite the simplicity of this model, various complex network structures emerge depending on the weight between the two addends of the cost function and on the selfish or unselfish behaviour of the agents.

Today I read a paper titled “Blind Detection and Compensation of Camera Lens Geometric Distortions”

The abstract is:
This paper presents a blind detection and compensation technique for camera lens geometric distortions.

The lens distortion introduces higher-order correlations in the frequency domain and in turn it can be detected using higher-order spectral analysis tools without assuming any specific calibration target.

The existing blind lens distortion removal method only considered a single-coefficient radial distortion model.

In this paper, two coefficients are considered to model approximately the geometric distortion.

All the models considered have analytical closed-form inverse formulae.

Today I read a paper titled “Swarms on Continuous Data”

The abstract is:
While being it extremely important, many Exploratory Data Analysis (EDA) systems have the inhability to perform classification and visualization in a continuous basis or to self-organize new data-items into the older ones (evenmore into new labels if necessary), which can be crucial in KDD – Knowledge Discovery, Retrieval and Data Mining Systems (interactive and online forms of Web Applications are just one example).

This disadvantge is also present in more recent approaches using Self-Organizing Maps.

On the present work, and exploiting past sucesses in recently proposed Stigmergic Ant Systems a robust online classifier is presented, which produces class decisions on a continuous stream data, allowing for continuous mappings.

Results show that increasingly better results are achieved, as demonstraded by other authors in different areas.

KEYWORDS: Swarm Intelligence, Ant Systems, Stigmergy, Data-Mining, Exploratory Data Analysis, Image Retrieval, Continuous Classification.

Today I read a paper titled “Target assignment for robotic networks: asymptotic performance under limited communication”

The abstract is:
We are given an equal number of mobile robotic agents, and distinct target locations.

Each agent has simple integrator dynamics, a limited communication range, and knowledge of the position of every target.

We address the problem of designing a distributed algorithm that allows the group of agents to divide the targets among themselves and, simultaneously, leads each agent to reach its unique target.

We do not require connectivity of the communication graph at any time.

We introduce a novel assignment-based algorithm with the following features: initial assignments and robot motions follow a greedy rule, and distributed refinements of the assignment exploit an implicit circular ordering of the targets.

We prove correctness of the algorithm, and give worst-case asymptotic bounds on the time to complete the assignment as the environment grows with the number of agents.

We show that among a certain class of distributed algorithms, our algorithm is asymptotically optimal.

The analysis utilizes results on the Euclidean traveling salesperson problem.

Today I read a paper titled “Multi-Modal Human-Machine Communication for Instructing Robot Grasping Tasks”

The abstract is:
A major challenge for the realization of intelligent robots is to supply them with cognitive abilities in order to allow ordinary users to program them easily and intuitively.

One way of such programming is teaching work tasks by interactive demonstration.

To make this effective and convenient for the user, the machine must be capable to establish a common focus of attention and be able to use and integrate spoken instructions, visual perceptions, and non-verbal clues like gestural commands.

We report progress in building a hybrid architecture that combines statistical methods, neural networks, and finite state machines into an integrated system for instructing grasping tasks by man-machine interaction.

The system combines the GRAVIS-robot for visual attention and gestural instruction with an intelligent interface for speech recognition and linguistic interpretation, and an modality fusion module to allow multi-modal task-oriented man-machine communication with respect to dextrous robot manipulation of objects.

Today I read a paper titled “Modeling the Dynamics of Social Networks”

The abstract is:
Modeling human dynamics responsible for the formation and evolution of the so-called social networks – structures comprised of individuals or organizations and indicating connectivities existing in a community – is a topic recently attracting a significant research interest.

It has been claimed that these dynamics are scale-free in many practically important cases, such as impersonal and personal communication, auctioning in a market, accessing sites on the WWW, etc., and that human response times thus conform to the power law.

While a certain amount of progress has recently been achieved in predicting the general response rate of a human population, existing formal theories of human behavior can hardly be found satisfactory to accommodate and comprehensively explain the scaling observed in social networks.

In the presented study, a novel system-theoretic modeling approach is proposed and successfully applied to determine important characteristics of a communication network and to analyze consumer behavior on the WWW.

Today I read a paper titled “Multi-Dimensional Recurrent Neural Networks”

The abstract is:
Recurrent neural networks (RNNs) have proved effective at one dimensional sequence learning tasks, such as speech and online handwriting recognition.

Some of the properties that make RNNs suitable for such tasks, for example robustness to input warping, and the ability to access contextual information, are also desirable in multidimensional domains.

However, there has so far been no direct way of applying RNNs to data with more than one spatio-temporal dimension.

This paper introduces multi-dimensional recurrent neural networks (MDRNNs), thereby extending the potential applicability of RNNs to vision, video processing, medical imaging and many other areas, while avoiding the scaling problems that have plagued other multi-dimensional models.

Experimental results are provided for two image segmentation tasks.