OpenRaiser/Intern-Atlas huggingface dataset:
Some model theory for the modal $μ$-calculus: syntactic characterisations of semantic properties
Venue: arXiv cs.LO 2018
Year: 2018

This paper contributes to the theory of the modal $μ$-calculus by proving some model-theoretic results. More in particular, we discuss a number of semantic properties pertaining to formulas of the modal $μ$-calculus. For each of these properties we provide a corresponding syntactic fragment, in the sense that a $μ$-formula $ξ$ has the given property iff it is equivalent to a formula $ξ'$ in the corresponding fragment. Since this formula $ξ'$ will always be effectively obtainable from $ξ$, as a corollary, for each of the properties under discussion, we prove that it is decidable in elementary time whether a given $μ$-calculus formula has the property or not. The properties that we study all concern the way in which the meaning of a formula $ξ$ in a model depends on the meaning of a single, fixed proposition letter $p$. For example, consider a formula $ξ$ which is monotone in $p$; such a formula a formula $ξ$ is called continuous (respectively, fully additive), if in addition it satisfies the property that, if $ξ$ is true at a state $s$ then there is a finite set (respectively, a singleton set) $U$ such that $ξ$ remains true at $s$ if we restrict the interpretation of $p$ to the set $U$. Each of the properties that we consider is, in a similar way, associated with one of the following special kinds of subset of a tree model: singletons, finite sets, finitely branching subtrees, noetherian subtrees (i.e., without infinite paths), and branches. Our proofs for these characterization results will be automata-theoretic in nature; we will see that the effectively defined maps on formulas are in fact induced by rather simple transformations on modal automata. Thus our results can also be seen as a contribution to the model theory of modal automata.
Natural Language Multitasking: Analyzing and Improving Syntactic Saliency of Hidden Representations
Venue: arXiv cs.CL 2018
Year: 2018

We train multi-task autoencoders on linguistic tasks and analyze the learned hidden sentence representations. The representations change significantly when translation and part-of-speech decoders are added. The more decoders a model employs, the better it clusters sentences according to their syntactic similarity, as the representation space becomes less entangled. We explore the structure of the representation space by interpolating between sentences, which yields interesting pseudo-English sentences, many of which have recognizable syntactic structure. Lastly, we point out an interesting property of our models: The difference-vector between two sentences can be added to change a third sentence with similar features in a meaningful way.
Approximate Early Output Asynchronous Adders Based on Dual-Rail Data Encoding and 4-Phase Return-to-Zero and Return-to-One Handshaking
Venue: arXiv cs.AR 2018
Year: 2018

Approximate computing is emerging as an alternative to accurate computing due to its potential for realizing digital circuits and systems with low power dissipation, less critical path delay, and less area occupancy for an acceptable trade-off in the accuracy of results. In the domain of computer arithmetic, several approximate adders and multipliers have been designed and their potential have been showcased versus accurate adders and multipliers for practical digital signal processing applications. Nevertheless, in the existing literature, almost all the approximate adders and multipliers reported correspond to the synchronous design method. In this work, we consider robust asynchronous i.e. quasi-delay-insensitive realizations of approximate adders by employing delay-insensitive codes for data representation and processing, and the 4-phase handshake protocols for data communication. The 4-phase handshake protocols used are the return-to-zero and the return-to-one protocols. Specifically, we consider the implementations of 32-bit approximate adders based on the return-to-zero and return-to-one handshake protocols by adopting the delay-insensitive dual-rail code for data encoding. We consider a range of approximations varying from 4-bits to 20-bits for the least significant positions of the accurate 32-bit asynchronous adder. The asynchronous adders correspond to early output (i.e. early reset) type, which are based on the well-known ripple carry adder architecture. The experimental results show that approximate asynchronous adders achieve reductions in the design metrics such as latency, cycle time, average power dissipation, and silicon area compared to the accurate asynchronous adders. Further, the reductions in the design metrics are greater for the return-to-one protocol compared to the return-to-zero protocol. The design metrics were estimated using a 32/28nm CMOS technology.
Invariants of multidimensional time series based on their iterated-integral signature
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a novel class of features for multidimensional time series, that are invariant with respect to transformations of the ambient space. The general linear group, the group of rotations and the group of permutations of the axes are considered. The starting point for their construction is Chen's iterated-integral signature.
Anatomy of an online misinformation network
Venue: arXiv cs.SI 2018
Year: 2018

Massive amounts of fake news and conspiratorial content have spread over social media before and after the 2016 US Presidential Elections despite intense fact-checking efforts. How do the spread of misinformation and fact-checking compete? What are the structural and dynamic characteristics of the core of the misinformation diffusion network, and who are its main purveyors? How to reduce the overall amount of misinformation? To explore these questions we built Hoaxy, an open platform that enables large-scale, systematic studies of how misinformation and fact-checking spread and compete on Twitter. Hoaxy filters public tweets that include links to unverified claims or fact-checking articles. We perform k-core decomposition on a diffusion network obtained from two million retweets produced by several hundred thousand accounts over the six months before the election. As we move from the periphery to the core of the network, fact-checking nearly disappears, while social bots proliferate. The number of users in the main core reaches equilibrium around the time of the election, with limited churn and increasingly dense connections. We conclude by quantifying how effectively the network can be disrupted by penalizing the most central nodes. These findings provide a first look at the anatomy of a massive online misinformation diffusion network.
On the Contractivity of Privacy Mechanisms
Venue: arXiv cs.IT 2018
Year: 2018

We present a novel way to compare the statistical cost of privacy mechanisms using their Dobrushin coefficient. Specifically, we provide upper and lower bounds for the Dobrushin coefficient of a privacy mechanism in terms of its maximal leakage and local differential privacy guarantees. Given the geometric nature of the Dobrushin coefficient, this approach provides some insights into the general statistical cost of these privacy guarantees. We highlight the strength of this method by applying our results to develop new bounds on the $\ell_2$-minimax risk in a distribution estimation setting under maximal leakage constraints. Specifically, we find its order with respect to the sample size and privacy level, allowing a quantitative comparison with the corresponding local differential privacy $\ell_2$-minimax risk.
Mining Android App Usages for Generating Actionable GUI-based Execution Scenarios
Venue: arXiv cs.SE 2018
Year: 2018

GUI-based models extracted from Android app execution traces, events, or source code can be extremely useful for challenging tasks such as the generation of scenarios or test cases. However, extracting effective models can be an expensive process. Moreover, existing approaches for automatically deriving GUI-based models are not able to generate scenarios that include events which were not observed in execution (nor event) traces. In this paper, we address these and other major challenges in our novel hybrid approach, coined as MonkeyLab. Our approach is based on the Record-Mine-Generate-Validate framework, which relies on recording app usages that yield execution (event) traces, mining those event traces and generating execution scenarios using statistical language modeling, static and dynamic analyses, and validating the resulting scenarios using an interactive execution of the app on a real device. The framework aims at mining models capable of generating feasible and fully replayable (i.e., actionable) scenarios reflecting either natural user behavior or uncommon usages (e.g., corner cases) for a given app. We evaluated MONKEYLAB in a case study involving several medium-to-large open-source Android apps. Our results demonstrate that MonkeyLab is able to mine GUI-based models that can be used to generate actionable execution scenarios for both natural and unnatural sequences of events on Google Nexus 7 tablets.
Plagiarism: Taxonomy, Tools and Detection Techniques
Venue: arXiv cs.IR 2018
Year: 2018

To detect plagiarism of any form, it is essential to have broad knowledge of its possible forms and classes, and existence of various tools and systems for its detection. Based on impact or severity of damages, plagiarism may occur in an article or in any production in a number of ways. This survey presents a taxonomy of various plagiarism forms and include discussion on each of these forms. Over the years, a good number tools and techniques have been introduced to detect plagiarism. This paper highlights few promising methods for plagiarism detection based on machine learning techniques. We analyse the pros and cons of these methods and finally we highlight a list of issues and research challenges related to this evolving research problem.
Some aspects of physical prototyping in Pervasive Computing
Venue: arXiv cs.NI 2018
Year: 2018

This document summarises the results of several research campaigns over the past seven years. The main connecting theme is the physical layer of widely deployed sensors in Pervasive Computing domains. In particular, we have focused on the RF-channel or on ambient audio. The initial problem from which we started this work was that of distributed adaptive transmit beamforming. We have been looking for a simple method to align the phases of jointly transmitting nodes (e.g. sensor or IoT nodes). The algorithmic solution to this problem was to implement a distributed random optimisation method on the participating nodes in which the transmitters and the receiver follow an iterative question-and-answer scheme. We have been able to derive sharp asymptotic bounds on the expected optimisation time of an evolutionary random optimiser and presented an asymptotically optimal approach. One thing that we have learned from the work on these physical layer algorithms was that the signals we work on are fragile and perceptive to physical environmental changes. These could be obstacles such as furniture, opened or closed windows or doors as well as movement of individuals. This observation motivated us to view the wireless interface as a sensor for environmental changes in Pervasive Computing environments. Another use of physical layer RF-signals is for security applications. We are currently working to further push these mentioned directions and novel fields of physical prototyping. In particular, the calculation of mathematical operations on the wireless channel at the time of transmission appears to contain good potential for gains in efficiency for communication and computation in Pervasive Computing domains.
Proceedings of eNTERFACE 2015 Workshop on Intelligent Interfaces
Venue: arXiv cs.HC 2018
Year: 2018

The 11th Summer Workshop on Multimodal Interfaces eNTERFACE 2015 was hosted by the Numediart Institute of Creative Technologies of the University of Mons from August 10th to September 2015. During the four weeks, students and researchers from all over the world came together in the Numediart Institute of the University of Mons to work on eight selected projects structured around intelligent interfaces. Eight projects were selected and their reports are shown here.
Convergence Analysis of Belief Propagation on Gaussian Graphical Models
Venue: arXiv cs.IT 2018
Year: 2018

Gaussian belief propagation (GBP) is a recursive computation method that is widely used in inference for computing marginal distributions efficiently. Depending on how the factorization of the underlying joint Gaussian distribution is performed, GBP may exhibit different convergence properties as different factorizations may lead to fundamentally different recursive update structures. In this paper, we study the convergence of GBP derived from the factorization based on the distributed linear Gaussian model. The motivation is twofold. From the factorization viewpoint, i.e., by specifically employing a factorization based on the linear Gaussian model, in some cases, we are able to bypass difficulties that exist in other convergence analysis methods that use a different (Gaussian Markov random field) factorization. From the distributed inference viewpoint, the linear Gaussian model readily conforms to the physical network topology arising in large-scale networks, and, is practically useful. For the distributed linear Gaussian model, under mild assumptions, we show analytically three main results: the GBP message inverse variance converges exponentially fast to a unique positive limit for arbitrary nonnegative initialization; we provide a necessary and sufficient convergence condition for the belief mean to converge to the optimal value; and, when the underlying factor graph is given by the union of a forest and a single loop, we show that GBP always converges.
EffNet: An Efficient Structure for Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

With the ever increasing application of Convolutional Neural Networks to customer products the need emerges for models to efficiently run on embedded, mobile hardware. Slimmer models have therefore become a hot research topic with various approaches which vary from binary networks to revised convolution layers. We offer our contribution to the latter and propose a novel convolution block which significantly reduces the computational burden while surpassing the current state-of-the-art. Our model, dubbed EffNet, is optimised for models which are slim to begin with and is created to tackle issues in existing models such as MobileNet and ShuffleNet.
A Congestion Control System Based on VANET for Small Length Roads
Venue: arXiv cs.NI 2018
Year: 2018

As vehicle population has been increasing on a daily basis, this leads towards increased number of accidents. To overcome this issue, Vehicular Ad Hoc Network (VANET) has come up with lot of novel ideas such as vehicular communication, navigation and traffic controlling. In this study, the main focus is on congestion control at the intersections which result from unclear ahead. For this purpose, a city lane and intersection model has been proposed to manage vehicle mobility. It shows the actual vehicle to vehicle and vehicle to traffic infrastructure communication. The experiment was conducted using Network Simulator 2 (NS 2). The implementation required modelling the road side unit, traffic control unit, and on-board unit along the roadside. In the simulation, including traffic volume, the distance between two signals, end-to-end delay, packet delivery ratio, throughput and packet lost were taken into consideration. These parameters ensure efficient communication between the traffic signals. This results in improved congestion control and road safety, since the vehicles will be signalled not to enter the junction box and information about other vehicles.
Empowering the Configuration-IP $-$ New PTAS Results for Scheduling with Setups Times
Venue: arXiv cs.DS 2018
Year: 2018

Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently. As an application, we consider scheduling problems with setup times, in which a set of jobs has to be scheduled on a set of identical machines, with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time $f(1/\varepsilon)\times \mathrm{poly}(|I|)$ with a single exponential term in $f$ for the first and a double exponential one for the second case. Previously, only constant factor approximations of $5/3$ and $4/3 + \varepsilon$ respectively were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine.
Deep Learning for Detecting Cyberbullying Across Multiple Social Media Platforms
Venue: arXiv cs.IR 2018
Year: 2018

Harassment by cyberbullies is a significant phenomenon on the social media. Existing works for cyberbullying detection have at least one of the following three bottlenecks. First, they target only one particular social media platform (SMP). Second, they address just one topic of cyberbullying. Third, they rely on carefully handcrafted features of the data. We show that deep learning based models can overcome all three bottlenecks. Knowledge learned by these models on one dataset can be transferred to other datasets. We performed extensive experiments using three real-world datasets: Formspring (12k posts), Twitter (16k posts), and Wikipedia(100k posts). Our experiments provide several useful insights about cyberbullying detection. To the best of our knowledge, this is the first work that systematically analyzes cyberbullying detection on various topics across multiple SMPs using deep learning based models and transfer learning.
Worst-case Optimal Submodular Extensions for Marginal Estimation
Venue: arXiv cs.LG 2018
Year: 2018

Submodular extensions of an energy function can be used to efficiently compute approximate marginals via variational inference. The accuracy of the marginals depends crucially on the quality of the submodular extension. To identify the best possible extension, we show an equivalence between the submodular extensions of the energy and the objective functions of linear programming (LP) relaxations for the corresponding MAP estimation problem. This allows us to (i) establish the worst-case optimality of the submodular extension for Potts model used in the literature; (ii) identify the worst-case optimal submodular extension for the more general class of metric labeling; and (iii) efficiently compute the marginals for the widely used dense CRF model with the help of a recently proposed Gaussian filtering method. Using synthetic and real data, we show that our approach provides comparable upper bounds on the log-partition function to those obtained using tree-reweighted message passing (TRW) in cases where the latter is computationally feasible. Importantly, unlike TRW, our approach provides the first practical algorithm to compute an upper bound on the dense CRF model.
Visualization of Hyperspectral Images Using Moving Least Squares
Venue: arXiv cs.CV 2018
Year: 2018

Displaying the large number of bands in a hyper spectral image on a trichromatic monitor has been an active research topic. The visualized image shall convey as much information as possible form the original data and facilitate image interpretation. Most existing methods display HSIs in false colors which contradict with human's experience and expectation. In this paper, we propose a nonlinear approach to visualize an input HSI with natural colors by taking advantage of a corresponding RGB image. Our approach is based on Moving Least Squares, an interpolation scheme for reconstructing a surface from a set of control points, which in our case is a set of matching pixels between the HSI and the corresponding RGB image. Based on MLS, the proposed method solves for each spectral signature a unique transformation so that the non linear structure of the HSI can be preserved. The matching pixels between a pair of HSI and RGB image can be reused to display other HSIs captured b the same imaging sensor with natural colors. Experiments show that the output image of the proposed method no only have natural colors but also maintain the visual information necessary for human analysis.
Structured Inhomogeneous Density Map Learning for Crowd Counting
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we aim at tackling the problem of crowd counting in extremely high-density scenes, which contain hundreds, or even thousands of people. We begin by a comprehensive analysis of the most widely used density map-based methods, and demonstrate how easily existing methods are affected by the inhomogeneous density distribution problem, e.g., causing them to be sensitive to outliers, or be hard to optimized. We then present an extremely simple solution to the inhomogeneous density distribution problem, which can be intuitively summarized as extending the density map from 2D to 3D, with the extra dimension implicitly indicating the density level. Such solution can be implemented by a single Density-Aware Network, which is not only easy to train, but also can achieve the state-of-art performance on various challenging datasets.
Determination of Digital Straight Segments Using the Slope
Venue: arXiv cs.CV 2018
Year: 2018

We present a new method for the recognition of digital straight lines based on the slope. This method combines the Freeman's chain coding scheme and new discovered properties of the digital slope introduced in this paper. We also present the efficiency of our method from a testbed.
Decision Rules for Robotic Mobile Fulfillment Systems
Venue: arXiv cs.MA 2018
Year: 2018

The Robotic Mobile Fulfillment Systems (RMFS) is a new type of robotized, parts-to-picker material handling system, designed especially for e-commerce warehouses. Robots bring movable shelves, called pods, to workstations where inventory is put on or removed from the pods. This paper simulates both the pick and replenishment process and studies the order assignment, pod selection and pod storage assignment problems by evaluating multiple decision rules per problem. The discrete event simulation uses realistic robot movements and keeps track of every unit of inventory on every pod. We analyze seven performance measures, e.g. throughput capacity and order due time, and find that the unit throughput is strongly correlated with the other performance measures. We vary the number of robots, the number of pick stations, the number of SKUs (stock keeping units), the order size and whether returns need processing or not. The decision rules for pick order assignment have a strong impact on the unit throughput rate. This is not the case for replenishment order assignment, pod selection and pod storage. Furthermore, for warehouses with a large number of SKUs, more robots are needed for a high unit throughput rate, even if the number of pods and the dimensions of the storage area remain the same. Lastly, processing return orders only affects the unit throughput rate for warehouse with a large number of SKUs and large pick orders.