OpenRaiser/Intern-Atlas huggingface dataset:
Inter-language Collaboration in an Object-oriented Virtual Machine
Venue: arXiv cs.PL 2016
Year: 2016

Multi-language virtual machines have a number of advantages. They allow software developers to use software libraries that were written for different programming languages. Furthermore, language implementors do not have to bother with low-level VM functionality and their implementation can benefit from optimizations in existing virtual machines. MagLev is an implementation of the Ruby programming language on top of the GemStone/S virtual machine for the Smalltalk programming language. In this work, we present how software components written in both languages can interact. We show how MagLev unifies the Smalltalk and the Ruby object model, taking into account Smalltalk meta classes, Ruby singleton classes, and Ruby modules. Besides, we show how we can call Ruby methods from Smalltalk and vice versa. We also present MagLev's concept of bridge methods for implementing Ruby method calling conventions. Finally, we compare our solution to other language implementations and virtual machines.
A Timed Process Algebra for Wireless Networks
Venue: arXiv cs.LO 2016
Year: 2016

This paper proposes a timed process algebra for wireless networks, an extension of the Algebra for Wireless Networks. It combines treatments of local broadcast, conditional unicast and data structures, which are essential features for the modelling of network protocols. In this framework we model and analyse the Ad hoc On-Demand Distance Vector routing protocol, and show that, contrary to claims in the literature, it fails to be loop free. We also present boundary conditions for a fix ensuring that the resulting protocol is indeed loop free.
Resource Allocation and Fairness in Wireless Powered Cooperative Cognitive Radio Networks
Venue: arXiv cs.IT 2016
Year: 2016

We integrate a wireless powered communication network with a cooperative cognitive radio network, where multiple secondary users (SUs) powered wirelessly by a hybrid access point (HAP) help a primary user relay the data. As a reward for the cooperation, the secondary network gains the spectrum access where SUs transmit to HAP using time division multiple access. To maximize the sum-throughput of SUs, we present a secondary sum-throughput optimal resource allocation (STORA) scheme. Under the constraint of meeting target primary rate, the STORA scheme chooses the optimal set of relaying SUs and jointly performs the time and energy allocation for SUs. Specifically, by exploiting the structure of the optimal solution, we find the order in which SUs are prioritized to relay primary data. Since the STORA scheme focuses on the sum-throughput, it becomes inconsiderate towards individual SU throughput, resulting in low fairness. To enhance fairness, we investigate three resource allocation schemes, which are (i) equal time allocation, (ii) minimum throughput maximization, and (iii) proportional time allocation. Simulation results reveal the trade-off between sum-throughput and fairness. The minimum throughput maximization scheme is the fairest one as each SU gets the same throughput, but yields the least SU sum-throughput.
A Simple Extension of Dirac's Theorem on Hamiltonicity
Venue: arXiv cs.DM 2016
Year: 2016

The classical Dirac theorem asserts that every graph $G$ on $n$ vertices with minimum degree $δ(G) \ge \lceil n/2 \rceil$ is Hamiltonian. The lower bound of $\lceil n/2 \rceil$ on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where $δ(G) \ge \lfloor n/2 \rfloor $ by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph $G$ with $δ(G) \ge \lfloor n/2 \rfloor$, or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when $δ(G) \ge \lfloor n/2 \rfloor$ and is promising for extending the results of this paper to the cases with smaller degree bounds.
SenseFlow: An Experimental Study for Tracking People
Venue: arXiv cs.HC 2016
Year: 2016

The main challenges in large-scale people tracking are the recognition of people density in a specific area and tracking the people flow path. To address these challenges, we present SenseFlow, a lightweight people tracking system. SenseFlow utilises off-the-shelf devices which sniff probe requests periodically polled by user's smartphones in a passive manner. We demonstrate the feasibility of SenseFlow by building a proof-of-concept prototype and undertaking extensive evaluations in real-world settings. We deploy the system in one laboratory to study office hours of researchers, a crowded public area in city to evaluate the scalability and performance "in the wild", and four classrooms in the university to monitor the number of students. We also evaluate SenseFlow with varying walking speeds and different models of smartphones to investigate the people flow tracking performance.
Automated Space/Time Scaling of Streaming Task Graph
Venue: arXiv cs.AR 2016
Year: 2016

In this paper, we describe a high-level synthesis (HLS) tool that automatically allows area/throughput trade-offs for implementing streaming task graphs (STG). Our tool targets a massively parallel processor array (MPPA) architecture, very similar to the Ambric MPPA chip architecture, which is to be implemented as an FPGA overlay. Similar to Ambric tools, our HLS tool accepts a STG as input written in a subset of Java and a structural language in the style of a Kahn Processing Network (KPN). Unlike the Ambric tools, our HLS tool analyzes the parallelism internal to each Java "node" and evaluates the throughput and area of several possible implementations. It then analyzes the full graph for bottlenecks or excess compute capacity, selects an implementation for each node, and even considers replicating or splitting nodes while either minimizing area (for a fixed throughput target), or maximizing throughput (for a fixed area target). In addition to traditional node selection and replication methods used in prior work, we have uniquely implemented node combining and splitting to find a better area/throughput trade-off. We present two optimization approaches, a formal ILP formulation and a heuristic solution. Results show that the heuristic is more flexible and can find design points not available to the ILP, thereby achieving superior results.
Towards Self-Calibrating Inertial Body Motion Capture
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a novel online capable method for simultaneous estimation of human motion in terms of segment orientations and positions along with sensor-to-segment calibration parameters from inertial sensors attached to the body. In order to solve this ill-posed estimation problem, state-of-the-art motion, measurement and biomechanical models are combined with new stochastic equations and priors. These are based on the kinematics of multi-body systems, anatomical and body shape information, as well as, parameter properties for regularisation. This leads to a constrained weighted least squares problem that is solved in a sliding window fashion. Magnetometer information is currently only used for initialisation, while the estimation itself works without magnetometers. The method was tested on simulated, as well as, on real data, captured from a lower body configuration.
Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time
Venue: arXiv cs.FL 2016
Year: 2016

We show that the equivalence of deterministic linear top-down tree-to-word transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not necessarily order-preserving and can be used to express XML and other document transformations. The result is based on a partial normal form that provides a basic characterization of the languages produced by linear tree-to-word transducers.
Deep Image Homography Estimation
Venue: arXiv cs.CV 2016
Year: 2016

We present a deep convolutional neural network for estimating the relative homography between a pair of images. Our feed-forward network has 10 layers, takes two stacked grayscale images as input, and produces an 8 degree of freedom homography which can be used to map the pixels from the first image to the second. We present two convolutional neural network architectures for HomographyNet: a regression network which directly estimates the real-valued homography parameters, and a classification network which produces a distribution over quantized homographies. We use a 4-point homography parameterization which maps the four corners from one image into the second image. Our networks are trained in an end-to-end fashion using warped MS-COCO images. Our approach works without the need for separate local feature detection and transformation estimation stages. Our deep models are compared to a traditional homography estimator based on ORB features and we highlight the scenarios where HomographyNet outperforms the traditional technique. We also describe a variety of applications powered by deep homography estimation, thus showcasing the flexibility of a deep learning approach.
Laplacian LRR on Product Grassmann Manifolds for Human Activity Clustering in Multi-Camera Video Surveillance
Venue: arXiv cs.CV 2016
Year: 2016

In multi-camera video surveillance, it is challenging to represent videos from different cameras properly and fuse them efficiently for specific applications such as human activity recognition and clustering. In this paper, a novel representation for multi-camera video data, namely the Product Grassmann Manifold (PGM), is proposed to model video sequences as points on the Grassmann manifold and integrate them as a whole in the product manifold form. Additionally, with a new geometry metric on the product manifold, the conventional Low Rank Representation (LRR) model is extended onto PGM and the new LRR model can be used for clustering non-linear data, such as multi-camera video data. To evaluate the proposed method, a number of clustering experiments are conducted on several multi-camera video datasets of human activity, including Dongzhimen Transport Hub Crowd action dataset, ACT 42 Human action dataset and SKIG action dataset. The experiment results show that the proposed method outperforms many state-of-the-art clustering methods.
User Experience of a Smart Factory Robot: Assembly Line Workers Demand Adaptive Robots
Venue: arXiv cs.RO 2016
Year: 2016

This paper reports a case study on the User Experience (UX)of an industrial robotic prototype in the context of human-robot cooperation in an automotive assembly line. The goal was to find out what kinds of suggestions the assembly line workers, who actually use the new robotic system, propose in order to improve the human-robot interaction (HRI). The operators working with the robotic prototype were interviewed three weeks after the deployment using established UX narrative interview guidelines. Our results show that the cooperation with a robot that executes predefined working steps actually impedes the user in terms of flexibility and individual speed. This results in a change of working routine for the operators, impacts the UX, and potentially leads to a decrease in productivity. We present the results of the interviews as well as first thoughts on technical solutions in order to enhance the adaptivity and subsequently the UX of the human-robot cooperation.
Extending E Prover with Similarity Based Clause Selection Strategies
Venue: arXiv cs.LO 2016
Year: 2016

E prover is a state-of-the-art theorem prover for first-order logic with equality. E prover is built around a saturation loop, where new clauses are derived by inference rules from previously derived clauses. Selection of clauses for the inference provides the main source of non-determinism and an important choice-point of the loop where the right choice can dramatically influence the proof search. In this work we extend E Prover with several new clause selection strategies based on similarity of a clause with the conjecture. In particular, clauses which are more related to the conjecture are preferred. We implement different strategies that define the relationship with a conjecture in different ways. We provide an implementation of the proposed selection strategies and we evaluate their efficiency on an extensive benchmark set.
Inferring Sparsity: Compressed Sensing using Generalized Restricted Boltzmann Machines
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we consider compressed sensing reconstruction from $M$ measurements of $K$-sparse structured signals which do not possess a writable correlation model. Assuming that a generative statistical model, such as a Boltzmann machine, can be trained in an unsupervised manner on example signals, we demonstrate how this signal model can be used within a Bayesian framework of signal reconstruction. By deriving a message-passing inference for general distribution restricted Boltzmann machines, we are able to integrate these inferred signal models into approximate message passing for compressed sensing reconstruction. Finally, we show for the MNIST dataset that this approach can be very effective, even for $M < K$.
Optimisation Of Pressure Sewer Operation
Venue: arXiv cs.SY 2016
Year: 2016

The paper deals with the new control method developed for the pressure sewer systems. This method eliminates the disadvantages of currently common used on-off regulation. The major disadvantage is a transition of inconstancies of the effluent production into the sewage system. The propose method is primarily based on the principle of an allocation of the drawing off into the given time slots. This control method is further improved by the extended modules provide higher level of the optimization (learning mode and emergent drawing off). Proposed method is able to decrease of the standard deviation of pumping even by 80%.
What Communication Modalities Do Users Prefer in Real Time HRI?
Venue: arXiv cs.RO 2016
Year: 2016

This paper investigates users' preferred interaction modalities when playing an imitation game with KASPAR, a small child-sized humanoid robot. The study involved 16 adult participants teaching the robot to mime a nursery rhyme via one of three interaction modalities in a real-time Human-Robot Interaction (HRI) experiment: voice, guiding touch and visual demonstration. The findings suggest that the users appeared to have no preference in terms of human effort for completing the task. However, there was a significant difference in human enjoyment preferences of input modality and a marginal difference in the robot's perceived ability to imitate.
Adaptivity vs Postselection
Venue: arXiv cs.CC 2016
Year: 2016

We study the following problem: with the power of postselection (classically or quantumly), what is your ability to answer adaptive queries to certain languages? More specifically, for what kind of computational classes $\mathcal{C}$, we have $\mathsf{P}^{\mathcal{C}}$ belongs to $\mathsf{PostBPP}$ and $\mathsf{PostBQP}$? While a complete answer to the above question seems impossible given the development of present computational complexity theory. We study the analogous question in query complexity, which sheds light on the limitation of {\em relativized} methods (the relativization barrier) to the above question. Informally, we show that, for a partial function $f$, if there is no efficient (In the world of query complexity, being efficient means using $O(\operatorname*{polylog}(n))$ time.) {\em small bounded-error} algorithm for $f$ classically or quantumly, then there is no efficient postselection bounded-error algorithm to answer adaptive queries to $f$ classically or quantumly. Our results imply a new proof for the classical oracle separation $\mathsf{P}^{\mathsf{NP}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}$. They also lead to a new oracle separation $\mathsf{P}^{\mathsf{SZK}^{\mathcal{O}}} \not\subset \mathsf{PP}^{\mathcal{O}}$. Our result also implies a hardness amplification construction for polynomial approximation: given a function $f$ on $n$ bits, we construct an adaptive-version of $f$, denoted by $F$, on $O(m \cdot n)$ bits, such that if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense, then $F$ requires large degree to approximate even to error $1/2 - 2^{-m}$. Our construction achieves the same amplification in the work of Thaler (ICALP, 2016), by composing a function with $O(\log n)$ {\em deterministic query complexity}.
On the exact learnability of graph parameters: The case of partition functions
Venue: arXiv cs.LG 2016
Year: 2016

We study the exact learnability of real valued graph parameters $f$ which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph $H$ with vertex weights $α$ and edge weights $β$. M. Freedman, L. Lovász and A. Schrijver have given a characterization of these graph parameters in terms of the $k$-connection matrices $C(f,k)$ of $f$. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter $f$, the learner can ask for the values of $f$ for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices $C(f,k)$ of $f$. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of $H$ and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.
Networked Intelligence: Towards Autonomous Cyber Physical Systems
Venue: arXiv cs.AI 2016
Year: 2016

Developing intelligent systems requires combining results from both industry and academia. In this report you find an overview of relevant research fields and industrially applicable technologies for building very large scale cyber physical systems. A concept architecture is used to illustrate how existing pieces may fit together, and the maturity of the subsystems is estimated. The goal is to structure the developments and the challenge of machine intelligence for Consumer and Industrial Internet technologists, cyber physical systems researchers and people interested in the convergence of data & Internet of Things. It can be used for planning developments of intelligent systems.
Rationalizing Neural Predictions
Venue: arXiv cs.CL 2016
Year: 2016

Prediction without justification has limited applicability. As a remedy, we learn to extract pieces of input text as justifications -- rationales -- that are tailored to be short and coherent, yet sufficient for making the same prediction. Our approach combines two modular components, generator and encoder, which are trained to operate well together. The generator specifies a distribution over text fragments as candidate rationales and these are passed through the encoder for prediction. Rationales are never given during training. Instead, the model is regularized by desiderata for rationales. We evaluate the approach on multi-aspect sentiment analysis against manually annotated test cases. Our approach outperforms attention-based baseline by a significant margin. We also successfully illustrate the method on the question retrieval task.
Single machine scheduling with job-dependent machine deterioration
Venue: arXiv cs.DS 2016
Year: 2016

We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum; in the full maintenance case every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case has been proven NP-hard; several special cases of the problem in the partial maintenance case were shown solvable in polynomial time, but the complexity of the general problem is left open. In this paper we first prove that the problem in the partial maintenance case is NP-hard, thus settling the open problem; we then design a $2$-approximation algorithm.
A Primer on 3GPP Narrowband Internet of Things (NB-IoT)
Venue: arXiv cs.NI 2016
Year: 2016

Narrowband Internet of Things (NB-IoT) is a new cellular technology introduced in 3GPP Release 13 for providing wide-area coverage for the Internet of Things (IoT). This article provides an overview of the air interface of NB-IoT. We describe how NB-IoT addresses key IoT requirements such as deployment flexibility, low device complexity, long battery life time, support of massive number of devices in a cell, and significant coverage extension beyond existing cellular technologies. We also share the various design rationales during the standardization of NB-IoT in Release 13 and point out several open areas for future evolution of NB-IoT.
Social- and Mobility-Aware Device-to-Device Content Delivery
Venue: arXiv cs.MM 2016
Year: 2016

Mobile online social network services have seen a rapid increase, in which the huge amount of user-generated social media contents propagating between users via social connections has significantly challenged the traditional content delivery paradigm: First, replicating all of the contents generated by users to edge servers that well "fit" the receivers becomes difficult due to the limited bandwidth and storage capacities. Motivated by device-to-device (D2D) communication that allows users with smart devices to transfer content directly, we propose replicating bandwidth-intensive social contents in a device-to-device manner. Based on large-scale measurement studies on social content propagation and user mobility patterns in edge-network regions, we observe that (1) Device-to-device replication can significantly help users download social contents from nearby neighboring peers; (2) Both social propagation and mobility patterns affect how contents should be replicated; (3) The replication strategies depend on regional characteristics ({\em e.g.}, how users move across regions). Using these measurement insights, we propose a joint \emph{propagation- and mobility-aware} content replication strategy for edge-network regions, in which social contents are assigned to users in edge-network regions according to a joint consideration of social graph, content propagation and user mobility. We formulate the replication scheduling as an optimization problem and design distributed algorithm only using historical, local and partial information to solve it. Trace-driven experiments further verify the superiority of our proposal: compared with conventional pure movement-based and popularity-based approach, our design can significantly ($2-4$ times) improve the amount of social contents successfully delivered by device-to-device replication.