OpenRaiser/Intern-Atlas huggingface dataset:
Merging real and virtual worlds: An analysis of the state of the art and practical evaluation of Microsoft Hololens
Venue: arXiv cs.HC 2017
Year: 2017

Achieving a symbiotic blending between reality and virtuality is a dream that has been lying in the minds of many people for a long time. Advances in various domains constantly bring us closer to making that dream come true. Augmented reality as well as virtual reality are in fact trending terms and are expected to further progress in the years to come. This master's thesis aims to explore these areas and starts by defining necessary terms such as augmented reality (AR) or virtual reality (VR). Usual taxonomies to classify and compare the corresponding experiences are then discussed. In order to enable those applications, many technical challenges need to be tackled, such as accurate motion tracking with 6 degrees of freedom (positional and rotational), that is necessary for compelling experiences and to prevent user sickness. Additionally, augmented reality experiences typically rely on image processing to position the superimposed content. To do so, "paper" markers or features extracted from the environment are often employed. Both sets of techniques are explored and common solutions and algorithms are presented. After investigating those technical aspects, I carry out an objective comparison of the existing state-of-the-art and state-of-the-practice in those domains, and I discuss present and potential applications in these areas. As a practical validation, I present the results of an application that I have developed using Microsoft HoloLens, one of the more advanced affordable technologies for augmented reality that is available today. Based on the experience and lessons learned during this development, I discuss the limitations of current technologies and present some avenues of future research.
Specifying Non-Markovian Rewards in MDPs Using LDL on Finite Traces (Preliminary Version)
Venue: arXiv cs.AI 2017
Year: 2017

In Markov Decision Processes (MDPs), the reward obtained in a state depends on the properties of the last state and action. This state dependency makes it difficult to reward more interesting long-term behaviors, such as always closing a door after it has been opened, or providing coffee only following a request. Extending MDPs to handle such non-Markovian reward function was the subject of two previous lines of work, both using variants of LTL to specify the reward function and then compiling the new model back into a Markovian model. Building upon recent progress in the theories of temporal logics over finite traces, we adopt LDLf for specifying non-Markovian rewards and provide an elegant automata construction for building a Markovian model, which extends that of previous work and offers strong minimality and compositionality guarantees.
Random Forests for Industrial Device Functioning Diagnostics Using Wireless Sensor Networks
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, random forests are proposed for operating devices diagnostics in the presence of a variable number of features. In various contexts, like large or difficult-to-access monitored areas, wired sensor networks providing features to achieve diagnostics are either very costly to use or totally impossible to spread out. Using a wireless sensor network can solve this problem, but this latter is more subjected to flaws. Furthermore, the networks' topology often changes, leading to a variability in quality of coverage in the targeted area. Diagnostics at the sink level must take into consideration that both the number and the quality of the provided features are not constant, and that some politics like scheduling or data aggregation may be developed across the network. The aim of this article is ($1$) to show that random forests are relevant in this context, due to their flexibility and robustness, and ($2$) to provide first examples of use of this method for diagnostics based on data provided by a wireless sensor network.
Dependability of Sensor Networks for Industrial Prognostics and Health Management
Venue: arXiv cs.SE 2017
Year: 2017

Maintenance is an important activity in industry. It is performed either to revive a machine/component or to prevent it from breaking down. Different strategies have evolved through time, bringing maintenance to its current state: condition-based and predictive maintenances. This evolution was due to the increasing demand of reliability in industry. The key process of condition-based and predictive maintenances is prognostics and health management, and it is a tool to predict the remaining useful life of engineering assets. Nowadays, plants are required to avoid shutdowns while offering safety and reliability. Nevertheless, planning a maintenance activity requires accurate information about the system/component health state. Such information is usually gathered by means of independent sensor nodes. In this study, we consider the case where the nodes are interconnected and form a wireless sensor network. As far as we know, no research work has considered such a case of study for prognostics. Regarding the importance of data accuracy, a good prognostics requires reliable sources of information. This is why, in this paper, we will first discuss the dependability of wireless sensor networks, and then present a state of the art in prognostic and health management activities.
Roaming across the Castle Tunnels: an Empirical Study of Inter-App Navigation Behaviors of Android Users
Venue: arXiv cs.HC 2017
Year: 2017

Mobile applications (a.k.a., apps), which facilitate a large variety of tasks on mobile devices, have become indispensable in our everyday lives. Accomplishing a task may require the user to navigate among various apps. Unlike Web pages that are inherently interconnected through hyperlinks, mobile apps are usually isolated building blocks, and the lack of direct links between apps has largely compromised the efficiency of task completion. In this paper, we present the first in-depth empirical study of inter-app navigation behaviors of smartphone users based on a comprehensive dataset collected through a sizable user study over three months. We propose a model to distinguish informational pages and transitional pages, based on which a large number of inter-app navigation are identified. We reveal that developing 'tunnels' between of isolated apps has a huge potential to reduce the cost of navigation. Our analysis provides various practical implications on how to improve app-navigation experiences from both the operating system's perspective and the developer's perspective.
Bidirectional Nested Weighted Automata
Venue: arXiv cs.FL 2017
Year: 2017

Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.
Beyond Moore-Penrose Part I: Generalized Inverses that Minimize Matrix Norms
Venue: arXiv cs.IT 2017
Year: 2017

This is the first paper of a two-long series in which we study linear generalized inverses that minimize matrix norms. Such generalized inverses are famously represented by the Moore-Penrose pseudoinverse (MPP) which happens to minimize the Frobenius norm. Freeing up the degrees of freedom associated with Frobenius optimality enables us to promote other interesting properties. In this Part I, we look at the basic properties of norm-minimizing generalized inverses, especially in terms of uniqueness and relation to the MPP. We first show that the MPP minimizes many norms beyond those unitarily invariant, thus further bolstering its role as a robust choice in many situations. We then concentrate on some norms which are generally not minimized by the MPP, but whose minimization is relevant for linear inverse problems and sparse representations. In particular, we look at mixed norms and the induced $\ell^p \rightarrow \ell^q$ norms. An interesting representative is the sparse pseudoinverse which we study in much more detail in Part II. Next, we shift attention from norms to matrices with interesting behaviors. We exhibit a class whose generalized inverse is always the MPP-even for norms that normally result in different inverses-and a class for which many generalized inverses coincide, but not with the MPP. Finally, we discuss efficient computation of norm-minimizing generalized inverses.
Image Processing in Floriculture Using a robotic Mobile Platform
Venue: arXiv cs.CY 2017
Year: 2017

Colombia has a privileged geographical location which makes it a cornerstone and equidistant point to all regional markets. The country has a great ecological diversity and it is one of the largest suppliers of flowers for US. Colombian flower companies have made innovations in the marketing process, using methods to reach all conditions for final consumers. This article develops a monitoring system for floriculture industries. The system was implemented in a robotic platform. This device has the ability to be programmed in different programming languages. The robot takes the necessary environment information from its camera. The algorithm of the monitoring system was developed with the image processing toolbox on Matlab. The implemented algorithm acquires images through its camera, it performs a preprocessing of the image, noise filter, enhancing of the color and adjusting the dimension in order to increase processing speed. Then, the image is segmented by color and with the binarized version of the image using morphological operations (erosion and dilation), extract relevant features such as centroid, perimeter and area. The data obtained from the image processing helps the robot with the automatic identification of objectives, orientation and move towards them. Also, the results generate a diagnostic quality of each object scanned.
Distributed compression through the lens of algorithmic information theory: a primer
Venue: arXiv cs.CC 2017
Year: 2017

Distributed compression is the task of compressing correlated data by several parties, each one possessing one piece of data and acting separately. The classical Slepian-Wolf theorem (D. Slepian, J. K. Wolf, IEEE Transactions on Inf. Theory, 1973) shows that if data is generated by independent draws from a joint distribution, that is by a memoryless stochastic process, then distributed compression can achieve the same compression rates as centralized compression when the parties act together. Recently, the author (M. Zimand, STOC 2017) has obtained an analogue version of the Slepian-Wolf theorem in the framework of Algorithmic Information Theory (also known as Kolmogorov complexity). The advantage over the classical theorem, is that the AIT version works for individual strings, without any assumption regarding the generative process. The only requirement is that the parties know the complexity profile of the input strings, which is a simple quantitative measure of the data correlation. The goal of this paper is to present in an accessible form that omits some technical details the main ideas from the reference (M. Zimand, STOC 2017).
Natural Language Does Not Emerge 'Naturally' in Multi-Agent Dialog
Venue: arXiv cs.CL 2017
Year: 2017

A number of recent works have proposed techniques for end-to-end learning of communication protocols among cooperative multi-agent populations, and have simultaneously found the emergence of grounded human-interpretable language in the protocols developed by the agents, all learned without any human supervision! In this paper, using a Task and Tell reference game between two agents as a testbed, we present a sequence of 'negative' results culminating in a 'positive' one -- showing that while most agent-invented languages are effective (i.e. achieve near-perfect task rewards), they are decidedly not interpretable or compositional. In essence, we find that natural language does not emerge 'naturally', despite the semblance of ease of natural-language-emergence that one may gather from recent literature. We discuss how it is possible to coax the invented languages to become more and more human-like and compositional by increasing restrictions on how two agents may communicate.
Democratizing Design for Future Computing Platforms
Venue: arXiv cs.CY 2017
Year: 2017

Information and communications technology can continue to change our world. These advances will partially depend upon designs that synergistically combine software with specialized hardware. Today open-source software incubates rapid software-only innovation. The government can unleash software-hardware innovation with programs to develop open hardware components, tools, and design flows that simplify and reduce the cost of hardware design. Such programs will speed development for startup companies, established industry leaders, education, scientific research, and for government intelligence and defense platforms.
The Minor Fall, the Major Lift: Inferring Emotional Valence of Musical Chords through Lyrics
Venue: arXiv cs.CL 2017
Year: 2017

We investigate the association between musical chords and lyrics by analyzing a large dataset of user-contributed guitar tablatures. Motivated by the idea that the emotional content of chords is reflected in the words used in corresponding lyrics, we analyze associations between lyrics and chord categories. We also examine the usage patterns of chords and lyrics in different musical genres, historical eras, and geographical regions. Our overall results confirms a previously known association between Major chords and positive valence. We also report a wide variation in this association across regions, genres, and eras. Our results suggest possible existence of different emotional associations for other types of chords.
Relating Complexity-theoretic Parameters with SAT Solver Performance
Venue: arXiv cs.AI 2017
Year: 2017

Over the years complexity theorists have proposed many structural parameters to explain the surprising efficiency of conflict-driven clause-learning (CDCL) SAT solvers on a wide variety of large industrial Boolean instances. While some of these parameters have been studied empirically, until now there has not been a unified comparative study of their explanatory power on a comprehensive benchmark. We correct this state of affairs by conducting a large-scale empirical evaluation of CDCL SAT solver performance on nearly 7000 industrial and crafted formulas against several structural parameters such as backdoors, treewidth, backbones, and community structure. Our study led us to several results. First, we show that while such parameters only weakly correlate with CDCL solving time, certain combinations of them yield much better regression models. Second, we show how some parameters can be used as a "lens" to better understand the efficiency of different solving heuristics. Finally, we propose a new complexity-theoretic parameter, which we call learning-sensitive with restarts (LSR) backdoors, that extends the notion of learning-sensitive (LS) backdoors to incorporate restarts and discuss algorithms to compute them. We mathematically prove that for certain class of instances minimal LSR-backdoors are exponentially smaller than minimal-LS backdoors.
Forbidden branches in trees with minimal atom-bond connectivity index
Venue: arXiv cs.DM 2017
Year: 2017

The atom-bond connectivity (ABC) index has been, in recent years, one of the most actively studied vertex-degree-based graph invariants in chemical graph theory. For a given graph $G$, the ABC index is defined as $\sum_{uv\in E}\sqrt{\frac{d(u) +d(v)-2}{d(u)d(v)}}$, where $d(u)$ is the degree of vertex $u$ in $G$ and $E(G)$ denotes the set of edges of $G$. In this paper we present some new structural properties of trees with a minimal ABC index (also refer to as a minimal-ABC tree), which is a step further towards understanding their complete characterization. We show that a minimal-ABC tree cannot simultaneously contain a $B_4$-branch and $B_1$ or $B_2$-branches.
Spatial Coding Based on Minimum BER in 1-Bit Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

We consider a downlink 1-bit quantized multiuser (MU) multiple-input-multiple-output (MIMO) system, where 1-bit digital-to-analog (DACs) and analog-to-digital converters (ADCs) are used at the transmitter and the receiver for economical and computational efficiency. We end up with a discrete memoryless channel with input and output vectors belonging to the QPSK constellation. In the context of massive (MIMO) systems the number of base station (BS) antennas is much larger than the number of receive antennas. This leads to high input cardinality of the channel. In this work we introduce a method to reduce the input set based on the mimimum bit-error-ratio (BER) criterion combined with a non-linear precoding technique. This method is denoted as spatial coding. Simulations show that this spatial coding improves the BER behavior significantly removing the error floor due to coarse quantization.
Auto-Encoder Guided GAN for Chinese Calligraphy Synthesis
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we investigate the Chinese calligraphy synthesis problem: synthesizing Chinese calligraphy images with specified style from standard font(eg. Hei font) images (Fig. 1(a)). Recent works mostly follow the stroke extraction and assemble pipeline which is complex in the process and limited by the effect of stroke extraction. We treat the calligraphy synthesis problem as an image-to-image translation problem and propose a deep neural network based model which can generate calligraphy images from standard font images directly. Besides, we also construct a large scale benchmark that contains various styles for Chinese calligraphy synthesis. We evaluate our method as well as some baseline methods on the proposed dataset, and the experimental results demonstrate the effectiveness of our proposed model.
The k-means-u* algorithm: non-local jumps and greedy retries improve k-means++ clustering
Venue: arXiv cs.LG 2017
Year: 2017

We present a new clustering algorithm called k-means-u* which in many cases is able to significantly improve the clusterings found by k-means++, the current de-facto standard for clustering in Euclidean spaces. First we introduce the k-means-u algorithm which starts from a result of k-means++ and attempts to improve it with a sequence of non-local "jumps" alternated by runs of standard k-means. Each jump transfers the "least useful" center towards the center with the largest local error, offset by a small random vector. This is continued as long as the error decreases and often leads to an improved solution. Occasionally k-means-u terminates despite obvious remaining optimization possibilities. By allowing a limited number of retries for the last jump it is frequently possible to reach better local minima. The resulting algorithm is called k-means-u* and dominates k-means++ wrt. solution quality which is demonstrated empirically using various data sets. By construction the logarithmic quality bound established for k-means++ holds for k-means-u* as well.
Multi-armed Bandit Problems with Strategic Arms
Venue: arXiv cs.GT 2017
Year: 2017

We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over the course of $T$ rounds. Our goal is to design an algorithm for the principal incentivizing these arms to pass on as much of their private rewards as possible. When private rewards are stochastically drawn each round ($v_a^t \leftarrow D_a$), we show that: - Algorithms that perform well in the classic adversarial multi-armed bandit setting necessarily perform poorly: For all algorithms that guarantee low regret in an adversarial setting, there exist distributions $D_1,\ldots,D_k$ and an approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. - Still, there exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. When each arm plays its dominant strategy, the principal sees expected reward $μ'T - o(T)$, where $μ'$ is the second-largest of the means $\mathbb{E}[D_{a}]$. This algorithm maintains its guarantee if the arms are non-strategic ($x_a = v_a$), and also if there is a mix of strategic and non-strategic arms.
Network Creation Games: Structure vs Anarchy
Venue: arXiv cs.GT 2017
Year: 2017

We study Nash equilibria and the price of anarchy in the classical model of Network Creation Games introduced by Fabrikant et al. In this model every agent (node) buys links at a prefixed price $α>0$ in order to get connected to the network formed by all the $n$ agents. In this setting, the reformulated tree conjecture states that for $α> n$, every Nash equilibrium network is a tree. Since it was shown that the price of anarchy for trees is constant, if the tree conjecture were true, then the price of anarchy would be constant for $α>n$. Moreover, Demaine et al. conjectured that the price of anarchy for this model is constant. Up to now the last conjecture has been proven in (i) the \emph{lower range}, for $α= O(n^{1-ε})$ with $ε\geq \frac{1}{\log n}$ and (ii) in the \emph{upper range}, for $α> 65n$. In contrast, the best upper bound known for the price of anarchy for the remaining range is $2^{O(\sqrt{\log n})}$. In this paper we give new insights into the structure of the Nash equilibria for different ranges of $α$ and we enlarge the range for which the price of anarchy is constant. Regarding the upper range, we prove that every Nash equilibrium is a tree for $α> 17n$ and that the price of anarchy is constant even for $α> 9n$. In the lower range, we show that any Nash equilibrium for $α< n/C$ with $C > 4$, induces an $ε-$distance-almost-uniform graph.
Drawbacks and alternatives to the numerical calculation of the base inertial parameters expressions for low mobility mechanisms
Venue: arXiv cs.RO 2017
Year: 2017

Base inertial parameters constitute a minimal inertial parametrization of mechanical systems that is of interest, for example, in parameter estimation and model reduction. Numerical and symbolic methods are available to determine their expressions. In this paper the problems associated with the numerical determination of the base inertial parameters expressions in the context of low mobility mechanisms are analyzed and discussed through and example. To circumvent these problems two alternatives are proposed: a variable precision arithmetic implementation of the customary numerical algorithm and the application of a general symbolic method. Finally, the advantages of both approaches compared to the numerical one are discussed in the context of the proposed low mobility example.