Monthly Archives: August 2017

You are browsing the site archives by month.

Clustering in hypergraphs

August 10, 2017 09:45 ,

P. Purkait, T. J. Chin, A. Sadri and D. Suter, Clustering with Hypergraphs: The Case for Large Hyperedges, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 9, pp. 1697-1711, DOI: 10.1109/TPAMI.2016.2614980.

The extension of conventional clustering to hypergraph clustering, which involves higher order similarities instead of pairwise similarities, is increasingly gaining attention in computer vision. This is due to the fact that many clustering problems require an affinity measure that must involve a subset of data of size more than two. In the context of hypergraph clustering, the calculation of such higher order similarities on data subsets gives rise to hyperedges. Almost all previous work on hypergraph clustering in computer vision, however, has considered the smallest possible hyperedge size, due to a lack of study into the potential benefits of large hyperedges and effective algorithms to generate them. In this paper, we show that large hyperedges are better from both a theoretical and an empirical standpoint. We then propose a novel guided sampling strategy for large hyperedges, based on the concept of random cluster models. Our method can generate large pure hyperedges that significantly improve grouping accuracy without exponential increases in sampling costs. We demonstrate the efficacy of our technique on various higher-order grouping problems. In particular, we show that our approach improves the accuracy and efficiency of motion segmentation from dense, long-term, trajectories.

Posted in: Graph theory , Tagged: ,

An interesting soft-partition method based on hierarchical graphs (trees, actually) applied to topic detection in documents

August 9, 2017 09:37 ,

Peixian Chen, Nevin L. Zhang, Tengfei Liu, Leonard K.M. Poon, Zhourong Chen, Farhan Khawar, Latent tree models for hierarchical topic detection, Artificial Intelligence, Volume 250, 2017, Pages 105-124, DOI: 10.1016/j.artint.2017.06.004.

We present a novel method for hierarchical topic detection where topics are obtained by clustering documents in multiple ways. Specifically, we model document collections using a class of graphical models called hierarchical latent tree models (HLTMs). The variables at the bottom level of an HLTM are observed binary variables that represent the presence/absence of words in a document. The variables at other levels are binary latent variables that represent word co-occurrence patterns or co-occurrences of such patterns. Each latent variable gives a soft partition of the documents, and document clusters in the partitions are interpreted as topics. Latent variables at high levels of the hierarchy capture long-range word co-occurrence patterns and hence give thematically more general topics, while those at low levels of the hierarchy capture short-range word co-occurrence patterns and give thematically more specific topics. In comparison with LDA-based methods, a key advantage of the new method is that it represents co-occurrence patterns explicitly using model structures. Extensive empirical results show that the new method significantly outperforms the LDA-based methods in term of model quality and meaningfulness of topics and topic hierarchies.

Posted in: Artificial Intelligence , Tagged: , ,

POMDPs with multicriteria in the cost to optimize – a hierarchical approach

August 7, 2017 09:25 ,

Seyedshams Feyzabadi, Stefano Carpin, Planning using hierarchical constrained Markov decision processes, Autonomous Robots, Volume 41, Issue 8, pp 1589–1607, DOI: 10.1007/s10514-017-9630-4.

Constrained Markov decision processes offer a principled method to determine policies for sequential stochastic decision problems where multiple costs are concurrently considered. Although they could be very valuable in numerous robotic applications, to date their use has been quite limited. Among the reasons for their limited adoption is their computational complexity, since policy computation requires the solution of constrained linear programs with an extremely large number of variables. To overcome this limitation, we propose a hierarchical method to solve large problem instances. States are clustered into macro states and the parameters defining the dynamic behavior and the costs of the clustered model are determined using a Monte Carlo approach. We show that the algorithm we propose to create clustered states maintains valuable properties of the original model, like the existence of a solution for the problem. Our algorithm is validated in various planning problems in simulation and on a mobile robot platform, and we experimentally show that the clustered approach significantly outperforms the non-hierarchical solution while experiencing only moderate losses in terms of objective functions.

Posted in: Artificial Intelligence, Probability and statistics, Robot task planning , Tagged: , ,

A new robotic middleware that exposes “resources” to the network instead of functionality

August 7, 2017 09:23 ,

Marcus V. D. VelosoJosé Tarcísio C. FilhoGuilherme A. Barreto, SOM4R: a Middleware for Robotic Applications Based on the Resource-Oriented Architecture, Journal of Intelligent & Robotic Systems, Volume 87, Issue 3–4, pp 487–506, DOI: 10.1007/s10846-017-0504-y.

This paper relies on the resource-oriented architecture (ROA) to propose a middleware that shares resources (sensors, actuators and services) of one or more robots through the TCP/IP network, providing greater efficiency in the development of software applications for robotics. The proposed middleware consists of a set of web services that provides access to representational state of resources through simple and high-level interfaces to implement a software architecture for autonomous robots. The benefits of the proposed approach are manifold: i) full abstraction of complexity and heterogeneity of robotic devices through web services and uniform interfaces, ii) scalability and independence of the operating system and programming language, iii) secure control of resources for local or remote applications through the TCP/IP network, iv) the adoption of the Resource Description Framework (RDF), XML language and HTTP protocol, and v) dynamic configuration of the connections between services at runtime. The middleware was developed using the Linux operating system (Ubuntu), with some applications built as proofs of concept for the Android operating system. The architecture specification and the open source implementation of the proposed middleware are detailed in this article, as well as applications for robot remote control via wireless networks, voice command functionality, and obstacle detection and avoidance.

Posted in: Robotic architectures, Robotic software , Tagged: