Archives for 2011

Today I read a paper titled “Unstructured Human Activity Detection from RGBD Images”

The abstract is:
Being able to detect and recognize human activities is essential for several applications, including personal assistive robotics.

In this paper, we perform detection and recognition of unstructured human activity in unstructured environments.

We use a RGBD sensor (Microsoft Kinect) as the input sensor, and compute a set of features based on human pose and motion, as well as based on image and pointcloud information.

Our algorithm is based on a hierarchical maximum entropy Markov model (MEMM), which considers a person’s activity as composed of a set of sub-activities.

We infer the two-layered graph structure using a dynamic programming approach.

We test our algorithm on detecting and recognizing twelve different activities performed by four people in different environments, such as a kitchen, a living room, an office, etc., and achieve good performance even when the person was not seen before in the training set.

Today I read a paper titled “A Vortex Method for Bi-phasic Fluids Interacting with Rigid Bodies”

The abstract is:
We present an accurate Lagrangian method based on vortex particles, level-sets, and immersed boundary methods, for animating the interplay between two fluids and rigid solids.

We show that a vortex method is a good choice for simulating bi-phase flow, such as liquid and gas, with a good level of realism.

Vortex particles are localized at the interfaces between the two fluids and within the regions of high turbulence.

We gain local precision and efficiency from the stable advection permitted by the vorticity formulation.

Moreover, our numerical method straightforwardly solves the two-way coupling problem between the fluids and animated rigid solids.

This new approach is validated through numerical comparisons with reference experiments from the computational fluid community.

We also show that the visually appealing results obtained in the CG community can be reproduced with increased efficiency and an easier implementation.

Today I read a paper titled “Probabilistically Safe Vehicle Control in a Hostile Environment”

The abstract is:
In this paper we present an approach to control a vehicle in a hostile environment with static obstacles and moving adversaries.

The vehicle is required to satisfy a mission objective expressed as a temporal logic specification over a set of properties satisfied at regions of a partitioned environment.

We model the movements of adversaries in between regions of the environment as Poisson processes.

Furthermore, we assume that the time it takes for the vehicle to traverse in between two facets of each region is exponentially distributed, and we obtain the rate of this exponential distribution from a simulator of the environment.

We capture the motion of the vehicle and the vehicle updates of adversaries distributions as a Markov Decision Process.

Using tools in Probabilistic Computational Tree Logic, we find a control strategy for the vehicle that maximizes the probability of accomplishing the mission objective.

We demonstrate our approach with illustrative case studies.

Today I read a paper titled “A path following algorithm for the graph matching problem”

The abstract is:
We propose a convex-concave programming approach for the labeled weighted graph matching problem.

The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices.

The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem.

We therefore construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation.

This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching.

The algorithm is compared with some of the best performing graph matching methods on four datasets: simulated graphs, QAPLib, retina vessel images and handwritten chinese characters.

In all cases, the results are competitive with the state-of-the-art.

Today I read a paper titled “Established Clustering Procedures for Network Analysis”

The abstract is:
In light of the burgeoning interest in network analysis in the new millenium, we bring to the attention of contemporary network theorists, a two-stage double-standarization and hierarchical clustering (single-linkage-like) procedure devised in 1974.

In its many applications over the next decade–primarily to the migration flows between geographic subdivisions within nations–the presence was often revealed of “hubs”.

These are, typically, “cosmopolitan/non-provincial” areas–such as the French capital, Paris–which send and receive people relatively broadly across their respective nations.

Additionally, this two-stage procedure–which “might very well be the most successful application of cluster analysis” (R.

C.

Dubes)–has detected many (physically or socially) isolated groups (regions) of areas, such as those forming the southern islands, Shikoku and Kyushu, of Japan, the Italian islands of Sardinia and Sicily, and the New England region of the United States.

Further, we discuss a (complementary) approach developed in 1976, involving the application of the max-flow/min-cut theorem to raw/non-standardized flows.

Today I read a paper titled “Colorization of Natural Images via L1 Optimization”

The abstract is:
Natural images in the colour space YUV have been observed to have a non-Gaussian, heavy tailed distribution (called ‘sparse’) when the filter G(U)(r) = U(r) – sum_{s \in N(r)} w{(Y)_{rs}} U(s), is applied to the chromacity channel U (and equivalently to V), where w is a weighting function constructed from the intensity component Y [1].

In this paper we develop Bayesian analysis of the colorization problem using the filter response as a regularization term to arrive at a non-convex optimization problem.

This problem is convexified using L1 optimization which often gives the same results for sparse signals [2].

It is observed that L1 optimization, in many cases, over-performs the famous colorization algorithm by Levin et al [3].

Today I read a paper titled “Feature Dynamic Bayesian Networks”

The abstract is:
Feature Markov Decision Processes (PhiMDPs) are well-suited for learning agents in general environments.

Nevertheless, unstructured (Phi)MDPs are limited to relatively simple environments.

Structured MDPs like Dynamic Bayesian Networks (DBNs) are used for large-scale real-world problems.

In this article I extend PhiMDP to PhiDBN.

The primary contribution is to derive a cost criterion that allows to automatically extract the most relevant features from the environment, leading to the “best” DBN representation.

I discuss all building blocks required for a complete general learning algorithm.

Today I read a paper titled “Discrete Complex Structure on Surfel Surfaces”

The abstract is:
This paper defines a theory of conformal parametrization of digital surfaces made of surfels equipped with a normal vector.

The main idea is to locally project each surfel to the tangent plane, therefore deforming its aspect-ratio.

It is a generalization of the theory known for polyhedral surfaces.

The main difference is that the conformal ratios that appear are no longer real in general.

It yields a generalization of the standard Laplacian on weighted graphs.

Today I read a paper titled “Fairness in Combinatorial Auctioning Systems”

The abstract is:
One of the Multi-Agent Systems that is widely used by various government agencies, buyers and sellers in a market economy, in such a manner so as to attain optimized resource allocation, is the Combinatorial Auctioning System (CAS).

We study another important aspect of resource allocations in CAS, namely fairness.

We present two important notions of fairness in CAS, extended fairness and basic fairness.

We give an algorithm that works by incorporating a metric to ensure fairness in a CAS that uses the Vickrey-Clark-Groves (VCG) mechanism, and uses an algorithm of Sandholm to achieve optimality.

Mathematical formulations are given to represent measures of extended fairness and basic fairness.

Today I read a paper titled “Increasing Linear Dynamic Range of Commercial Digital Photocamera Used in Imaging Systems with Optical Coding”

The abstract is:
Methods of increasing linear optical dynamic range of commercial photocamera for optical-digital imaging systems are described.

Use of such methods allows to use commercial photocameras for optical measurements.

Experimental results are reported.

Today I read a paper titled “Controlling wheelchairs by body motions: A learning framework for the adaptive remapping of space”

The abstract is:
Learning to operate a vehicle is generally accomplished by forming a new cognitive map between the body motions and extrapersonal space.

Here, we consider the challenge of remapping movement-to-space representations in survivors of spinal cord injury, for the control of powered wheelchairs.

Our goal is to facilitate this remapping by developing interfaces between residual body motions and navigational commands that exploit the degrees of freedom that disabled individuals are most capable to coordinate.

We present a new framework for allowing spinal cord injured persons to control powered wheelchairs through signals derived from their residual mobility.

The main novelty of this approach lies in substituting the more common joystick controllers of powered wheelchairs with a sensor shirt.

This allows the whole upper body of the user to operate as an adaptive joystick.

Considerations about learning and risks have lead us to develop a safe testing environment in 3D Virtual Reality.

A Personal Augmented Reality Immersive System (PARIS) allows us to analyse learning skills and provide users with an adequate training to control a simulated wheelchair through the signals generated by body motions in a safe environment.

We provide a description of the basic theory, of the development phases and of the operation of the complete system.

We also present preliminary results illustrating the processing of the data and supporting of the feasibility of this approach.

Today I read a paper titled “Spatial Networks”

The abstract is:
Complex systems are very often organized under the form of networks where nodes and edges are embedded in space.

Transportation and mobility networks, Internet, mobile phone networks, power grids, social and contact networks, neural networks, are all examples where space is relevant and where topology alone does not contain all the information.

Characterizing and understanding the structure and the evolution of spatial networks is thus crucial for many different fields ranging from urbanism to epidemiology.

An important consequence of space on networks is that there is a cost associated to the length of edges which in turn has dramatic effects on the topological structure of these networks.

We will expose thoroughly the current state of our understanding of how the spatial constraints affect the structure and properties of these networks.

We will review the most recent empirical observations and the most important models of spatial networks.

We will also discuss various processes which take place on these spatial networks, such as phase transitions, random walks, synchronization, navigation, resilience, and disease spread.

Today I read a paper titled “Elementary epistemological features of machine intelligence”

The abstract is:
Theoretical analysis of machine intelligence (MI) is useful for defining a common platform in both theoretical and applied artificial intelligence (AI).

The goal of this paper is to set canonical definitions that can assist pragmatic research in both strong and weak AI.

Described epistemological features of machine intelligence include relationship between intelligent behavior, intelligent and unintelligent machine characteristics, observable and unobservable entities and classification of intelligence.

The paper also establishes algebraic definitions of efficiency and accuracy of MI tests as their quality measure.

The last part of the paper addresses the learning process with respect to the traditional epistemology and the epistemology of MI described here.

The proposed views on MI positively correlate to the Hegelian monistic epistemology and contribute towards amalgamating idealistic deliberations with the AI theory, particularly in a local frame of reference.

Today I read a paper titled “Opinion formation and cyclic dominance in adaptive networks”

The abstract is:
The Rock-Paper-Scissors(RPS) game is a paradigmatic model for cyclic dominance in biological systems.

Here we consider this game in the social context of competition between opinions in a networked society.

In our model, every agent has an opinion which is drawn from the three choices: rock, paper or scissors.

In every timestep a link is selected randomly and the game is played between the nodes connected by the link.

The loser either adopts the opinion of the winner or rewires the link.

These rules define an adaptive network on which the agent’s opinions coevolve with the network topology of social contacts.

We show analytically and numerically that nonequilibrium phase transitions occur as a function of the rewiring strength.

The transitions separate four distinct phases which differ in the observed dynamics of opinions and topology.

In particular, there is one phase where the population settles to an arbitrary consensus opinion.

We present a detailed analysis of the corresponding transitions revealing an apparently paradoxial behavior.

The system approaches consensus states where they are unstable, whereas other dynamics prevail when the consensus states are stable.

Today I read a paper titled “Quantum Interaction Approach in Cognition, Artificial Intelligence and Robotics”

The abstract is:
The mathematical formalism of quantum mechanics has been successfully employed in the last years to model situations in which the use of classical structures gives rise to problematical situations, and where typically quantum effects, such as ‘contextuality’ and ‘entanglement’, have been recognized.

This ‘Quantum Interaction Approach’ is briefly reviewed in this paper focusing, in particular, on the quantum models that have been elaborated to describe how concepts combine in cognitive science, and on the ensuing identification of a quantum structure in human thought.

We point out that these results provide interesting insights toward the development of a unified theory for meaning and knowledge formalization and representation.

Then, we analyze the technological aspects and implications of our approach, and a particular attention is devoted to the connections with symbolic artificial intelligence, quantum computation and robotics.

Today I read a paper titled “Using explosive percolation in analysis of real-world networks”

The abstract is:
We apply a variant of the explosive percolation procedure to large real-world networks, and show with finite-size scaling that the university class, ordinary or explosive, of the resulting percolation transition depends on the structural properties of the network as well as the number of unoccupied links considered for comparison in our procedure.

We observe that in our social networks, the percolation clusters close to the critical point are related to the community structure.

This relationship is further highlighted by applying the procedure to model networks with pre-defined communities.

Today I read a paper titled “Dimensionality Reduction and Reconstruction using Mirroring Neural Networks and Object Recognition based on Reduced Dimension Characteristic Vector”

The abstract is:
In this paper, we present a Mirroring Neural Network architecture to perform non-linear dimensionality reduction and Object Recognition using a reduced lowdimensional characteristic vector.

In addition to dimensionality reduction, the network also reconstructs (mirrors) the original high-dimensional input vector from the reduced low-dimensional data.

The Mirroring Neural Network architecture has more number of processing elements (adalines) in the outer layers and the least number of elements in the central layer to form a converging-diverging shape in its configuration.

Since this network is able to reconstruct the original image from the output of the innermost layer (which contains all the information about the input pattern), these outputs can be used as object signature to classify patterns.

The network is trained to minimize the discrepancy between actual output and the input by back propagating the mean squared error from the output layer to the input layer.

After successfully training the network, it can reduce the dimension of input vectors and mirror the patterns fed to it.

The Mirroring Neural Network architecture gave very good results on various test patterns.

Today I read a paper titled “L2-optimal image interpolation and its applications to medical imaging”

The abstract is:
Digital medical images are always displayed scaled to fit particular view.

Interpolation is responsible for this scaling, and if not done properly, can significantly degrade diagnostic image quality.

However, theoretically-optimal interpolation algorithms may also be the most time-consuming and impractical.

We propose a new approach, adapted to the needs of digital medical imaging, to combine high interpolation speed and superior L2-optimal image quality.

Today I read a paper titled “Music By Numbers”

The abstract is:
In this paper we present a mathematical way of defining musical modes, we derive a formula for the total number of modes and define the musicality of a mode as the total number of harmonic chords whithin the mode.

We also give an algorithm for the construction of a duet of melodic lines given a sequence of numbers and a mode.

We attach the .mus files of the counterpoints obtained by using the sequence of primes and several musical modes.

Today I read a paper titled “Doubly Robust Policy Evaluation and Learning”

The abstract is:
We study decision making in environments where the reward is only partially observed, but can be modeled as a function of an action and an observed context.

This setting, known as contextual bandits, encompasses a wide variety of applications including health-care policy and Internet advertising.

A central task is evaluation of a new policy given historic data consisting of contexts, actions and received rewards.

The key challenge is that the past data typically does not faithfully represent proportions of actions taken by a new policy.

Previous approaches rely either on models of rewards or models of the past policy.

The former are plagued by a large bias whereas the latter have a large variance.

In this work, we leverage the strength and overcome the weaknesses of the two approaches by applying the doubly robust technique to the problems of policy evaluation and optimization.

We prove that this approach yields accurate value estimates when we have either a good (but not necessarily consistent) model of rewards or a good (but not necessarily consistent) model of past policy.

Extensive empirical comparison demonstrates that the doubly robust approach uniformly improves over existing techniques, achieving both lower variance in value estimation and better policies.

As such, we expect the doubly robust approach to become common practice.

Today I read a paper titled “Topological Quantum Error Correction with Optimal Encoding Rate”

The abstract is:
We prove the existence of topological quantum error correcting codes with encoding rates $k/n$ asymptotically approaching the maximum possible value.

Explicit constructions of these topological codes are presented using surfaces of arbitrary genus.

We find a class of regular toric codes that are optimal.

For physical implementations, we present planar topological codes.