OpenRaiser/Intern-Atlas huggingface dataset:
Robots with Lights: Overcoming Obstructed Visibility Without Colliding
Venue: arXiv cs.DC 2014
Year: 2014

Robots with lights is a model of autonomous mobile computational entities operating in the plane in Look-Compute-Move cycles: each agent has an externally visible light which can assume colors from a fixed set; the lights are persistent (i.e., the color is not erased at the end of a cycle), but otherwise the agents are oblivious. The investigation of computability in this model, initially suggested by Peleg, is under way, and several results have been recently established. In these investigations, however, an agent is assumed to be capable to see through another agent. In this paper we start the study of computing when visibility is obstructable, and investigate the most basic problem for this setting, Complete Visibility: The agents must reach within finite time a configuration where they can all see each other and terminate. We do not make any assumption on a-priori knowledge of the number of agents, on rigidity of movements nor on chirality. The local coordinate system of an agent may change at each activation. Also, by definition of lights, an agent can communicate and remember only a constant number of bits in each cycle. In spite of these weak conditions, we prove that Complete Visibility is always solvable, even in the asynchronous setting, without collisions and using a small constant number of colors. The proof is constructive. We also show how to extend our protocol for Complete Visibility so that, with the same number of colors, the agents solve the (non-uniform) Circle Formation problem with obstructed visibility.
Coordinate System Selection for Minimum Error Rate Training in Statistical Machine Translation
Venue: arXiv cs.CL 2014
Year: 2014

Minimum error rate training (MERT) is a widely used training procedure for statistical machine translation. A general problem of this approach is that the search space is easy to converge to a local optimum and the acquired weight set is not in accord with the real distribution of feature functions. This paper introduces coordinate system selection (RSS) into the search algorithm for MERT. Contrary to previous approaches in which every dimension only corresponds to one independent feature function, we create several coordinate systems by moving one of the dimensions to a new direction. The basic idea is quite simple but critical that the training procedure of MERT should be based on a coordinate system formed by search directions but not directly on feature functions. Experiments show that by selecting coordinate systems with tuning set results, better results can be obtained without any other language knowledge.
Taking advantage of hybrid systems for sparse direct solvers via task-based runtimes
Venue: arXiv cs.DC 2014
Year: 2014

The ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of computing resources. The pressure to maintain reasonable levels of performance and portability forces application developers to leave the traditional programming paradigms and explore alternative solutions. PaStiX is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical manycore architectures. In this paper, we study the benefits and limits of replacing the highly specialized internal scheduler of the PaStiX solver with two generic runtime systems: PaRSEC and StarPU. The tasks graph of the factorization step is made available to the two runtimes, providing them the opportunity to process and optimize its traversal in order to maximize the algorithm efficiency for the targeted hardware platform. A comparative study of the performance of the PaStiX solver on top of its native internal scheduler, PaRSEC, and StarPU frameworks, on different execution environments, is performed. The analysis highlights that these generic task-based runtimes achieve comparable results to the application-optimized embedded scheduler on homogeneous platforms. Furthermore, they are able to significantly speed up the solver on heterogeneous environments by taking advantage of the accelerators while hiding the complexity of their efficient manipulation from the programmer.
Selecting Near-Optimal Approximate State Representations in Reinforcement Learning
Venue: arXiv cs.LG 2014
Year: 2014

We consider a reinforcement learning setting introduced in (Maillard et al., NIPS 2011) where the learner does not have explicit access to the states of the underlying Markov decision process (MDP). Instead, she has access to several models that map histories of past interactions to states. Here we improve over known regret bounds in this setting, and more importantly generalize to the case where the models given to the learner do not contain a true model resulting in an MDP representation but only approximations of it. We also give improved error bounds for state aggregation.
Malicious User Detection in Spectrum Sensing for WRAN Using Different Outliers Detection Techniques
Venue: arXiv cs.NI 2014
Year: 2014

In cognitive radio it is of prime importance that the presence of Primary Users (PU) is detected correctly at each of the time. In order to do so the help from all present Secondary Users (SU) is taken and such a taken is known as co-operative spectrum sensing. Ideally it is assumed that all the secondary users give the correct result to the control center. But there are certain conditions under which the secondary users deliberately forward wrong result to the control center so as to degrade the performance of the cognitive network. In this paper we study the different techniques for detecting the malicious users or outliers. We take into consideration practical environmental condition such that the received signal of the secondary users is made to undergo fading and noise is also introduced in the signal. We further go on to examine each of the outlier detector techniques and find out the most suitable at various instants.
Tabling, Rational Terms, and Coinduction Finally Together!
Venue: arXiv cs.PL 2014
Year: 2014

To appear in Theory and Practice of Logic Programming (TPLP). Tabling is a commonly used technique in logic programming for avoiding cyclic behavior of logic programs and enabling more declarative program definitions. Furthermore, tabling often improves computational performance. Rational term are terms with one or more infinite sub-terms but with a finite representation. Rational terms can be generated in Prolog by omitting the occurs check when unifying two terms. Applications of rational terms include definite clause grammars, constraint handling systems, and coinduction. In this paper, we report our extension of YAP's Prolog tabling mechanism to support rational terms. We describe the internal representation of rational terms within the table space and prove its correctness. We then use this extension to implement a tabling based approach to coinduction. We compare our approach with current coinductive transformations and describe the implementation. In addition, we present an algorithm that ensures a canonical representation for rational terms.
Imitation-based Social Spectrum Sharing
Venue: arXiv cs.NI 2014
Year: 2014

Dynamic spectrum sharing is a promising technology for improving the spectrum utilization. In this paper, we study how secondary users can share the spectrum in a distributed fashion based on social imitations. The imitation-based mechanism leverages the social intelligence of the secondary user crowd and only requires a low computational power for each individual user. We introduce the information sharing graph to model the social information sharing relationship among the secondary users. We propose an imitative spectrum access mechanism on a general information sharing graph such that each secondary user first estimates its expected throughput based on local observations, and then imitates the channel selection of another neighboring user who achieves a higher throughput. We show that the imitative spectrum access mechanism converges to an imitation equilibrium, where no beneficial imitation can be further carried out on the time average. Numerical results show that the imitative spectrum access mechanism can achieve efficient spectrum utilization and meanwhile provide good fairness across secondary users.
Resource Prediction for Humanoid Robots
Venue: arXiv cs.RO 2014
Year: 2014

Humanoid robots are designed to operate in human centered environments where they execute a multitude of challenging tasks, each differing in complexity, resource requirements, and execution time. In such highly dynamic surroundings it is desirable to anticipate upcoming situations in order to predict future resource requirements such as CPU or memory usage. Resource prediction information is essential for detecting upcoming resource bottlenecks or conflicts and can be used enhance resource negotiation processes or to perform speculative resource allocation. In this paper we present a prediction model based on Markov chains for predicting the behavior of the humanoid robot ARMAR-III in human robot interaction scenarios. Robot state information required by the prediction algorithm is gathered through self-monitoring and combined with environmental context information. Adding resource profiles allows generating probability distributions of possible future resource demands. Online learning of model parameters is made possible through disclosure mechanisms provided by the robot framework ArmarX.
Automatic Detection of Performance Anomalies in Task-Parallel Programs
Venue: arXiv cs.DC 2014
Year: 2014

To efficiently exploit the resources of new many-core architectures, integrating dozens or even hundreds of cores per chip, parallel programming models have evolved to expose massive amounts of parallelism, often in the form of fine-grained tasks. Task-parallel languages, such as OpenStream, X10, Habanero Java and C or StarSs, simplify the development of applications for new architectures, but tuning task-parallel applications remains a major challenge. Performance bottlenecks can occur at any level of the implementation, from the algorithmic level (e.g., lack of parallelism or over-synchronization), to interactions with the operating and runtime systems (e.g., data placement on NUMA architectures), to inefficient use of the hardware (e.g., frequent cache misses or misaligned memory accesses); detecting such issues and determining the exact cause is a difficult task. In previous work, we developed Aftermath, an interactive tool for trace-based performance analysis and debugging of task-parallel programs and run-time systems. In contrast to other trace-based analysis tools, such as Paraver or Vampir, Aftermath offers native support for tasks, i.e., visualization, statistics and analysis tools adapted for performance debugging at task granularity. However, the tool currently does not provide support for the automatic detection of performance bottlenecks and it is up to the user to investigate the relevant aspects of program execution by focusing the inspection on specific slices of a trace file. In this paper, we present ongoing work on two extensions that guide the user through this process.
Autotuning and Self-Adaptability in Concurrency Libraries
Venue: arXiv cs.SE 2014
Year: 2014

Autotuning is an established technique for optimizing the performance of parallel applications. However, programmers must prepare applications for autotuning, which is tedious and error prone coding work. We demonstrate how applications become ready for autotuning with few or no modifications by extending Threading Building Blocks (TBB), a library for parallel programming, with autotuning. The extended TBB library optimizes all application-independent tuning parameters fully automatically. We compare manual effort, autotuning overhead and performance gains on 17 examples. While some examples benefit only slightly, others speed up by 28% over standard TBB.
What Will 5G Be?
Venue: arXiv cs.IT 2014
Year: 2014

What will 5G be? What it will not be is an incremental advance on 4G. The previous four generations of cellular technology have each been a major paradigm shift that has broken backwards compatibility. And indeed, 5G will need to be a paradigm shift that includes very high carrier frequencies with massive bandwidths, extreme base station and device densities and unprecedented numbers of antennas. But unlike the previous four generations, it will also be highly integrative: tying any new 5G air interface and spectrum together with LTE and WiFi to provide universal high-rate coverage and a seamless user experience. To support this, the core network will also have to reach unprecedented levels of flexibility and intelligence, spectrum regulation will need to be rethought and improved, and energy and cost efficiencies will become even more critical considerations. This paper discusses all of these topics, identifying key challenges for future research and preliminary 5G standardization activities, while providing a comprehensive overview of the current literature, and in particular of the papers appearing in this special issue.
Semantic Support for Log Analysis of Safety-Critical Embedded Systems
Venue: arXiv cs.SE 2014
Year: 2014

Testing is a relevant activity for the development life-cycle of Safety Critical Embedded systems. In particular, much effort is spent for analysis and classification of test logs from SCADA subsystems, especially when failures occur. The human expertise is needful to understand the reasons of failures, for tracing back the errors, as well as to understand which requirements are affected by errors and which ones will be affected by eventual changes in the system design. Semantic techniques and full text search are used to support human experts for the analysis and classification of test logs, in order to speedup and improve the diagnosis phase. Moreover, retrieval of tests and requirements, which can be related to the current failure, is supported in order to allow the discovery of available alternatives and solutions for a better and faster investigation of the problem.
The inverted Pendulum: A fundamental Benchmark in Control Theory and Robotics
Venue: arXiv cs.RO 2014
Year: 2014

For at least fifty years, the inverted pendulum has been the most popular benchmark, among others, for teaching and researches in control theory and robotics. This paper presents the key motivations for the use of that system and explains, in details, the main reflections on how the inverted pendulum benchmark gives an effective and efficient application. Several real experiences, virtual models and web-based remote control laboratories will be presented with emphasis on the practical design implementation of this system. A bibliographical survey of different design control approaches and trendy robotic problems will be presented through applications to the inverted pendulum system. In total, 150 references in the open literature, dating back to 1960, are compiled to provide an overall picture of historical, current and challenging developments.
Scalable Coordinated Beamforming for Dense Wireless Cooperative Networks
Venue: arXiv cs.IT 2014
Year: 2014

To meet the ever growing demand for both high throughput and uniform coverage in future wireless networks, dense network deployment will be ubiquitous, for which co- operation among the access points is critical. Considering the computational complexity of designing coordinated beamformers for dense networks, low-complexity and suboptimal precoding strategies are often adopted. However, it is not clear how much performance loss will be caused. To enable optimal coordinated beamforming, in this paper, we propose a framework to design a scalable beamforming algorithm based on the alternative direction method of multipliers (ADMM) method. Specifically, we first propose to apply the matrix stuffing technique to transform the original optimization problem to an equivalent ADMM-compliant problem, which is much more efficient than the widely-used modeling framework CVX. We will then propose to use the ADMM algorithm, a.k.a. the operator splitting method, to solve the transformed ADMM-compliant problem efficiently. In particular, the subproblems of the ADMM algorithm at each iteration can be solved with closed-forms and in parallel. Simulation results show that the proposed techniques can result in significant computational efficiency compared to the state- of-the-art interior-point solvers. Furthermore, the simulation results demonstrate that the optimal coordinated beamforming can significantly improve the system performance compared to sub-optimal zero forcing beamforming.
Locally Boosted Graph Aggregation for Community Detection
Venue: arXiv cs.LG 2014
Year: 2014

Learning the right graph representation from noisy, multi-source data has garnered significant interest in recent years. A central tenet of this problem is relational learning. Here the objective is to incorporate the partial information each data source gives us in a way that captures the true underlying relationships. To address this challenge, we present a general, boosting-inspired framework for combining weak evidence of entity associations into a robust similarity metric. Building on previous work, we explore the extent to which different local quality measurements yield graph representations that are suitable for community detection. We present empirical results on a variety of datasets demonstrating the utility of this framework, especially with respect to real datasets where noise and scale present serious challenges. Finally, we prove a convergence theorem in an ideal setting and outline future research into other application domains.
Rate of Convergence and Error Bounds for LSTD($λ$)
Venue: arXiv cs.LG 2014
Year: 2014

We consider LSTD($λ$), the least-squares temporal-difference algorithm with eligibility traces algorithm proposed by Boyan (2002). It computes a linear approximation of the value function of a fixed policy in a large Markov Decision Process. Under a $β$-mixing assumption, we derive, for any value of $λ\in (0,1)$, a high-probability estimate of the rate of convergence of this algorithm to its limit. We deduce a high-probability bound on the error of this algorithm, that extends (and slightly improves) that derived by Lazaric et al. (2012) in the specific case where $λ=0$. In particular, our analysis sheds some light on the choice of $λ$ with respect to the quality of the chosen linear space and the number of samples, that complies with simulations.
Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we study lifted inference for the Weighted First-Order Model Counting problem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statistical Relational Learning (SRL) and Probabilistic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P-hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several properties of the algorithm. Finally, we discuss limitations of lifted inference for symmetric probabilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the entire language FOL.
Newton-Type Iterative Solver for Multiple View $L2$ Triangulation
Venue: arXiv cs.CV 2014
Year: 2014

In this note, we show that the L2 optimal solutions to most real multiple view L2 triangulation problems can be efficiently obtained by two-stage Newton-like iterative methods, while the difficulty of such problems mainly lies in how to verify the L2 optimality. Such a working two-stage bundle adjustment approach features: first, the algorithm is initialized by symmedian point triangulation, a multiple-view generalization of the mid-point method; second, a symbolic-numeric method is employed to compute derivatives accurately; third, globalizing strategy such as line search or trust region is smoothly applied to the underlying iteration which assures algorithm robustness in general cases. Numerical comparison with tfml method shows that the local minimizers obtained by the two-stage iterative bundle adjustment approach proposed here are also the L2 optimal solutions to all the calibrated data sets available online by the Oxford visual geometry group. Extensive numerical experiments indicate the bundle adjustment approach solves more than 99% the real triangulation problems optimally. An IEEE 754 double precision C++ implementation shows that it takes only about 0.205 second tocompute allthe 4983 points in the Oxford dinosaur data setvia Gauss-Newton iteration hybrid with a line search strategy on a computer with a 3.4GHz Intel i7 CPU.
Which one is better: presentation-based or content-based math search?
Venue: arXiv cs.IR 2014
Year: 2014

Mathematical content is a valuable information source and retrieving this content has become an important issue. This paper compares two searching strategies for math expressions: presentation-based and content-based approaches. Presentation-based search uses state-of-the-art math search system while content-based search uses semantic enrichment of math expressions to convert math expressions into their content forms and searching is done using these content-based expressions. By considering the meaning of math expressions, the quality of search system is improved over presentation-based systems.
Perceptions of International Female Students Towards E-learning in Resolving High Education and Family Role Strain
Venue: arXiv cs.CY 2014
Year: 2014

It is a common phenomenon for many mature female international students enrolled in high education overseas to experience strain from managing conflicting roles of student and family, and difficulties of cross-cultural adjustment. The purpose of this study is to examine perceptions and behavioral intentions of international female students towards e-learning as a tool for resolving overseas high education and family strain from a technology acceptance standpoint. To achieve this goal, Davis's (1989) technology acceptance model is used as the study's conceptual framework, to investigate perceived usefulness, ease of use and behavioral intentions towards e-learning. The research draws on face-to-face interviews with 21 female international students enrolled in classroom taught degree programs at a university in Wuhan, China. The data is analyzed through coding and transcribing. The findings reveal that given its convenience, e-learning is generally perceived as practical in balancing study with family as well as feasible in saving time, money and energy. However, key concerns were raised over the issues of poor and costly Internet connectivity in developing countries, as well as perceived negative reputation, lack of face-to-face interaction and lack of motivation in online environment. Important issues and recommendations are raised for consideration when promoting e-learning programme. This study emphasis on the need to revisit gender supporting policies and effective marketing to re-position the prevailing image of e-learning as a reputable and reliable education delivery method.