OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Online Classification and Tracking on Resource-constrained IoT Devices
Venue: arXiv cs.NI 2020
Year: 2020

Timely processing has been increasingly required on smart IoT devices, which leads to directly implementing information processing tasks on an IoT device for bandwidth savings and privacy assurance. Particularly, monitoring and tracking the observed signals in continuous form are common tasks for a variety of near real-time processing IoT devices, such as in smart homes, body-area and environmental sensing applications. However, these systems are likely low-cost resource-constrained embedded systems, equipped with compact memory space, whereby the ability to store the full information state of continuous signals is limited. Hence, in this paper, we develop solutions of efficient timely processing embedded systems for online classification and tracking of continuous signals with compact memory space. Particularly, we focus on the application of smart plugs that are capable of timely classification of appliance types and tracking of appliance behavior in a standalone manner. We implemented a smart plug prototype using low-cost Arduino platform with small amount of memory space to demonstrate the following timely processing operations: (1) learning and classifying the patterns associated with the continuous power consumption signals, and (2) tracking the occurrences of signal patterns using small local memory space. Furthermore, our system designs are also sufficiently generic for timely monitoring and tracking applications in other resource-constrained IoT devices.
Adversarial Reinforcement Learning-based Robust Access Point Coordination Against Uncoordinated Interference
Venue: arXiv cs.NI 2020
Year: 2020

This paper proposes a robust adversarial reinforcement learning (RARL)-based multi-access point (AP) coordination method that is robust even against unexpected decentralized operations of uncoordinated APs. Multi-AP coordination is a promising technique towards IEEE 802.11be, and there are studies that use RL for multi-AP coordination. Indeed, a simple RL-based multi-AP coordination method diminishes the collision probability among the APs; therefore, the method is a promising approach to improve time-resource efficiency. However, this method is vulnerable to frame transmissions of uncoordinated APs that are less aware of frame transmissions of other coordinated APs. To help the central agent experience even such unexpected frame transmissions, in addition to the central agent, the proposed method also competitively trains an adversarial AP that disturbs coordinated APs by causing frame collisions intensively. Besides, we propose to exploit a history of frame losses of a coordinated AP to promote reasonable competition between the central agent and adversarial AP. The simulation results indicate that the proposed method can avoid uncoordinated interference and thereby improve the minimum sum of the throughputs in the system compared to not considering the uncoordinated AP.
Exact and Approximate Methods for Proving Unrealizability of Syntax-Guided Synthesis Problems
Venue: arXiv cs.PL 2020
Year: 2020

We consider the problem of automatically establishing that a given syntax-guided-synthesis (SyGuS) problem is unrealizable (i.e., has no solution). We formulate the problem of proving that a SyGuS problem is unrealizable over a finite set of examples as one of solving a set of equations: the solution yields an overapproximation of the set of possible outputs that any term in the search space can produce on the given examples. If none of the possible outputs agrees with all of the examples, our technique has proven that the given SyGuS problem is unrealizable. We then present an algorithm for exactly solving the set of equations that result from SyGuS problems over linear integer arithmetic (LIA) and LIA with conditionals (CLIA), thereby showing that LIA and CLIA SyGuS problems over finitely many examples are decidable. We implement the proposed technique and algorithms in a tool called Nay. Nay can prove unrealizability for 70/132 existing SyGuS benchmarks, with running times comparable to those of the state-of-the-art tool Nope. Moreover, Nay can solve 11 benchmarks that Nope cannot solve.
How Furiously Can Colourless Green Ideas Sleep? Sentence Acceptability in Context
Venue: arXiv cs.CL 2020
Year: 2020

We study the influence of context on sentence acceptability. First we compare the acceptability ratings of sentences judged in isolation, with a relevant context, and with an irrelevant context. Our results show that context induces a cognitive load for humans, which compresses the distribution of ratings. Moreover, in relevant contexts we observe a discourse coherence effect which uniformly raises acceptability. Next, we test unidirectional and bidirectional language models in their ability to predict acceptability ratings. The bidirectional models show very promising results, with the best model achieving a new state-of-the-art for unsupervised acceptability prediction. The two sets of experiments provide insights into the cognitive aspects of sentence processing and central issues in the computational modelling of text and discourse.
A k-hop Collaborate Game Model: Extended to Community Budgets and Adaptive Non-Submodularity
Venue: arXiv cs.SI 2020
Year: 2020

Revenue maximization (RM) is one of the most important problems on online social networks (OSNs), which attempts to find a small subset of users in OSNs that makes the expected revenue maximized. It has been researched intensively before. However, most of exsiting literatures were based on non-adaptive seeding strategy and on simple information diffusion model, such as IC/LT-model. It considered the single influenced user as a measurement unit to quantify the revenue. Until Collaborate Game model appeared, it considered activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distance are within k-hop from the initiator. Based on that, we adopt adaptive seed strategy and formulate the Revenue Maximization under the Size Budget (RMSB) problem. If taking into account the product's promotion, we extend RMSB to the Revenue Maximization under the Community Budget (RMCB) problem, where the influence can be distributed over the whole network. The objective function of RMSB and RMCB is adatpive monotone and not adaptive submodular, but in some special cases, it is adaptive submodular. We study the RMSB and RMCB problem under both the speical submodular cases and general non-submodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. Especially, we give a data-dependent approximation ratio for RMSB problem under the general non-submodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions.
Learning Representations For Images With Hierarchical Labels
Venue: arXiv cs.LG 2020
Year: 2020

Image classification has been studied extensively but there has been limited work in the direction of using non-conventional, external guidance other than traditional image-label pairs to train such models. In this thesis we present a set of methods to leverage information about the semantic hierarchy induced by class labels. In the first part of the thesis, we inject label-hierarchy knowledge to an arbitrary classifier and empirically show that availability of such external semantic information in conjunction with the visual semantics from images boosts overall performance. Taking a step further in this direction, we model more explicitly the label-label and label-image interactions by using order-preserving embedding-based models, prevalent in natural language, and tailor them to the domain of computer vision to perform image classification. Although, contrasting in nature, both the CNN-classifiers injected with hierarchical information, and the embedding-based models outperform a hierarchy-agnostic model on the newly presented, real-world ETH Entomological Collection image dataset https://www.research-collection.ethz.ch/handle/20.500.11850/365379.
An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
Venue: arXiv cs.AI 2020
Year: 2020

In this article, we present the anytime tree search algorithm we designed for the 2018 ROADEF/EURO challenge glass cutting problem proposed by the French company Saint-Gobain. The resulting program was ranked first among 64 participants. Its key components are: a new search algorithm called Memory Bounded A* (MBA*) with guide functions, a symmetry breaking strategy, and a pseudo-dominance rule. We perform a comprehensive study of these components showing that each of them contributes to the algorithm global performances. In addition, we designed a second tree search algorithm fully based on the pseudo-dominance rule and dedicated to some of the challenge instances with strong precedence constraints. On these instances, it finds the best-known solutions very quickly.
Pruned Wasserstein Index Generation Model and wigpy Package
Venue: arXiv cs.LG 2020
Year: 2020

Recent proposal of Wasserstein Index Generation model (WIG) has shown a new direction for automatically generating indices. However, it is challenging in practice to fit large datasets for two reasons. First, the Sinkhorn distance is notoriously expensive to compute and suffers from dimensionality severely. Second, it requires to compute a full $N\times N$ matrix to be fit into memory, where $N$ is the dimension of vocabulary. When the dimensionality is too large, it is even impossible to compute at all. I hereby propose a Lasso-based shrinkage method to reduce dimensionality for the vocabulary as a pre-processing step prior to fitting the WIG model. After we get the word embedding from Word2Vec model, we could cluster these high-dimensional vectors by $k$-means clustering, and pick most frequent tokens within each cluster to form the "base vocabulary". Non-base tokens are then regressed on the vectors of base token to get a transformation weight and we could thus represent the whole vocabulary by only the "base tokens". This variant, called pruned WIG (pWIG), will enable us to shrink vocabulary dimension at will but could still achieve high accuracy. I also provide a \textit{wigpy} module in Python to carry out computation in both flavor. Application to Economic Policy Uncertainty (EPU) index is showcased as comparison with existing methods of generating time-series sentiment indices.
Grammar-Compressed Indexes with Logarithmic Search Time
Venue: arXiv cs.DS 2020
Year: 2020

Let a text $T[1..n]$ be the only string generated by a context-free grammar with $g$ (terminal and nonterminal) symbols, and of size $G$ (measured as the sum of the lengths of the right-hand sides of the rules). Such a grammar, called a grammar-compressed representation of $T$, can be encoded using essentially $G\lg g$ bits. We introduce the first grammar-compressed index that uses $O(G\lg n)$ bits and can find the $occ$ occurrences of patterns $P[1..m]$ in time $O((m^2+occ)\lg G)$. We implement the index and demonstrate its practicality in comparison with the state of the art, on highly repetitive text collections.
Natural Language Processing (NLP) for Requirements Engineering: A Systematic Mapping Study
Venue: arXiv cs.SE 2020
Year: 2020

Natural language processing supported requirements engineering is an area of research and development that seeks to apply NLP techniques, tools and resources to a variety of requirements documents or artifacts to support a range of linguistic analysis tasks performed at various RE phases. Such tasks include detecting language issues, identifying key domain concepts and establishing traceability links between requirements. This article surveys the landscape of NLP4RE research to understand the state of the art and identify open problems. The systematic mapping study approach is used to conduct this survey, which identified 404 relevant primary studies and reviewed them according to five research questions, cutting across five aspects of NLP4RE research, concerning the state of the literature, the state of empirical research, the research focus, the state of the practice, and the NLP technologies used. Results: 1) NLP4RE is an active and thriving research area in RE that has amassed a large number of publications and attracted widespread attention from diverse communities; 2) most NLP4RE studies are solution proposals having only been evaluated using a laboratory experiment or an example application; 3) most studies have focused on the analysis phase, with detection as their central linguistic analysis task and requirements specification as their commonly processed document type; 4) 130 new tools have been proposed to support a range of linguistic analysis tasks, but there is little evidence of adoption in the long term, although some industrial applications have been published; 5) 140 NLP techniques, 66 NLP tools and 25 NLP resources are extracted from the selected studies.
Predictive Bandits
Venue: arXiv cs.LG 2020
Year: 2020

We introduce and study a new class of stochastic bandit problems, referred to as predictive bandits. In each round, the decision maker first decides whether to gather information about the rewards of particular arms (so that their rewards in this round can be predicted). These measurements are costly, and may be corrupted by noise. The decision maker then selects an arm to be actually played in the round. Predictive bandits find applications in many areas; e.g. they can be applied to channel selection problems in radio communication systems. In this paper, we provide the first theoretical results about predictive bandits, and focus on scenarios where the decision maker is allowed to measure at most one arm per round. We derive asymptotic instance-specific regret lower bounds for these problems, and develop algorithms whose regret match these fundamental limits. We illustrate the performance of our algorithms through numerical experiments. In particular, we highlight the gains that can be achieved by using reward predictions, and investigate the impact of the noise in the corresponding measurements.
Finding the fixed points of a Boolean network from a positive feedback vertex set
Venue: arXiv cs.DM 2020
Year: 2020

In the modeling of biological systems by Boolean networks a key problem is finding the set of fixed points of a given network. Some constructed algorithms consider certain structural properties of the interaction graph like those proposed by Akutsu et al. in \cite{akutsu1998system,zhang2007algorithms} which consider a feedback vertex set of the graph. However, these methods do not take into account the type of action (activation, inhibition) between its components. In this paper we propose a new algorithm for finding the set of fixed points of a Boolean network, based on a positive feedback vertex set $P$ of its interaction graph and which works, by applying a sequential update schedule, in time $O(2^{|P|} \cdot n^2)$, where $n$ is the number of components. The theoretical foundation of this algorithm is due a nice characterization, that we give, of the dynamical behavior of the Boolean networks without positive cycles and with a fixed point. An executable file of \Afp made in Java and some examples of input files are available at: \href{http://www.inf.udec.cl/~lilian/FPCollector/}{\url{www.inf.udec.cl/~lilian/FPCollector/}}
Mixed Sessions: the Other Side of the Tape
Venue: arXiv cs.PL 2020
Year: 2020

The original paper on Mixed Sessions introduce the side A of the tape: there is an encoding of classical sessions into mixed sessions. Here we present side B: there is a translation of (a subset of) mixed sessions into classical session types. We prove that the translation is a minimal encoding, according to the criteria put forward by Kouzapas, Pérez, and Yoshida.
Omission-based Abstraction for Answer Set Programs
Venue: arXiv cs.LO 2020
Year: 2020

Abstraction is a well-known approach to simplify a complex problem by over-approximating it with a deliberate loss of information. It was not considered so far in Answer Set Programming (ASP), a convenient tool for problem solving. We introduce a method to automatically abstract ASP programs that preserves their structure by reducing the vocabulary while ensuring an over-approximation (i.e., each original answer set maps to some abstract answer set). This allows for generating partial answer set candidates that can help with approximation of reasoning. Computing the abstract answer sets is intuitively easier due to a smaller search space, at the cost of encountering spurious answer sets. Faithful (non-spurious) abstractions may be used to represent projected answer sets and to guide solvers in answer set construction. For dealing with spurious answer sets, we employ an ASP debugging approach to help with abstraction refinement, which determines atoms as badly omitted and adds them back in the abstraction. As a show case, we apply abstraction to explain unsatisfiability of ASP programs in terms of blocker sets, which are the sets of atoms such that abstraction to them preserves unsatisfiability. Their usefulness is demonstrated by experimental results.
Disassembling Object Representations without Labels
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we study a new representation-learning task, which we termed as disassembling object representations. Given an image featuring multiple objects, the goal of disassembling is to acquire a latent representation, of which each part corresponds to one category of objects. Disassembling thus finds its application in a wide domain such as image editing and few- or zero-shot learning, as it enables category-specific modularity in the learned representations. To this end, we propose an unsupervised approach to achieving disassembling, named Unsupervised Disassembling Object Representation (UDOR). UDOR follows a double auto-encoder architecture, in which a fuzzy classification and an object-removing operation are imposed. The fuzzy classification constrains each part of the latent representation to encode features of up to one object category, while the object-removing, combined with a generative adversarial network, enforces the modularity of the representations and integrity of the reconstructed image. Furthermore, we devise two metrics to respectively measure the modularity of disassembled representations and the visual integrity of reconstructed images. Experimental results demonstrate that the proposed UDOR, despited unsupervised, achieves truly encouraging results on par with those of supervised methods.
On the Path to High Precise IP Geolocation: A Self-Optimizing Model
Venue: arXiv cs.NI 2020
Year: 2020

IP Geolocation is a key enabler for the Future Internet to provide geographical location information for application services. For example, this data is used by Content Delivery Networks to assign users to mirror servers, which are close by, hence providing enhanced traffic management. It is still a challenging task to obtain precise and stable location information, whereas proper results are only achieved by the use of active latency measurements. This paper presents an advanced approach for an accurate and self-optimizing model for location determination, including identification of optimized Landmark positions, which are used for probing. Moreover, the selection of correlated data and the estimated target location requires a sophisticated strategy to identify the correct position. We present an improved approximation of network distances of usually unknown TIER infrastructures using the road network. Our concept is evaluated under real-world conditions focusing Europe.
Comparing emotional states induced by 360$^{\circ}$ videos via head-mounted display and computer screen
Venue: arXiv cs.MM 2020
Year: 2020

In recent years 360$^{\circ}$ videos have been becoming more popular. For traditional media presentations, e.g., on a computer screen, a wide range of assessment methods are available. Different constructs, such as perceived quality or the induced emotional state of viewers, can be reliably assessed by subjective scales. Many of the subjective methods have only been validated using stimuli presented on a computer screen. This paper is using 360$^{\circ}$ videos to induce varying emotional states. Videos were presented 1) via a head-mounted display (HMD) and 2) via a traditional computer screen. Furthermore, participants were asked to rate their emotional state 1) in retrospect on the self-assessment manikin scale and 2) continuously on a 2-dimensional arousal-valence plane. In a repeated measures design, all participants (N = 18) used both presentation systems and both rating systems. Results indicate that there is a statistically significant difference in induced presence due to the presentation system. Furthermore, there was no statistically significant difference in ratings gathered with the two presentation systems. Finally, it was found that for arousal measures, a statistically significant difference could be found for the different rating methods, potentially indicating an underestimation of arousal ratings gathered in retrospect for screen presentation. In the future, rating methods such as a 2-dimensional arousal-valence plane could offer the advantage of enabling a reliable measurement of emotional states while being more embedded in the experience itself, enabling a more precise capturing of the emotional states.
Finding Black Cat in a Coal Cellar -- Keyphrase Extraction & Keyphrase-Rubric Relationship Classification from Complex Assignments
Venue: arXiv cs.CL 2020
Year: 2020

Diversity in content and open-ended questions are inherent in complex assignments across online graduate programs. The natural scale of these programs poses a variety of challenges across both peer and expert feedback including rogue reviews. While the identification of relevant content and associating it to predefined rubrics would simplify and improve the grading process, the research to date is still in a nascent stage. As such in this paper we aim to quantify the effectiveness of supervised and unsupervised approaches for the task for keyphrase extraction and generic/specific keyphrase-rubric relationship extraction. Through this study, we find that (i) unsupervised MultiPartiteRank produces the best result for keyphrase extraction (ii) supervised SVM classifier with BERT features that offer the best performance for both generic and specific keyphrase-rubric relationship classification. We finally present a comprehensive analysis and derive useful observations for those interested in these tasks for the future. The source code is released in \url{https://github.com/manikandan-ravikiran/cs6460-proj}.
Impact of Tactile and Visual Feedback on Breathing Rhythm and User Experience in VR Exergaming
Venue: arXiv cs.HC 2020
Year: 2020

Combining interconnected wearables provides fascinating opportunities like augmenting exergaming with virtual coaches, feedback on the execution of sports activities, or how to improve on them. Breathing rhythm is a particularly interesting physiological dimension since it is easy and unobtrusive to measure and gained data provide valuable insights regarding the correct execution of movements, especially when analyzed together with additional movement data in real-time. In this work, we focus on indoor rowing since it is a popular sport that's often done alone without extensive instructions. We compare a visual breathing indication with haptic guidance in order for athletes to maintain a correct, efficient, and healthy breathing-movement-synchronicity (BMS) while working out. Also, user experience and acceptance of the different modalities were measured. The results show a positive and statistically significant impact of purely verbal instructions and purely tactile feedback on BMS and no significant impact of visual feedback. Interestingly, the subjective ratings indicate a strong preference for the visual modality and even an aversion for the haptic feedback, although objectively the performance benefited most from using the latter.