OpenRaiser/Intern-Atlas huggingface dataset:
Seeds Buffering for Information Spreading Processes
Venue: arXiv cs.SI 2017
Year: 2017

Seeding strategies for influence maximization in social networks have been studied for more than a decade. They have mainly relied on the activation of all resources (seeds) simultaneously in the beginning; yet, it has been shown that sequential seeding strategies are commonly better. This research focuses on studying sequential seeding with buffering, which is an extension to basic sequential seeding concept. The proposed method avoids choosing nodes that will be activated through the natural diffusion process, which is leading to better use of the budget for activating seed nodes in the social influence process. This approach was compared with sequential seeding without buffering and single stage seeding. The results on both real and artificial social networks confirm that the buffer-based consecutive seeding is a good trade-off between the final coverage and the time to reach it. It performs significantly better than its rivals for a fixed budget. The gain is obtained by dynamic rankings and the ability to detect network areas with nodes that are not yet activated and have high potential of activating their neighbours.
Structural Resolution for Abstract Compilation of Object-Oriented Languages
Venue: arXiv cs.PL 2017
Year: 2017

We propose abstract compilation for precise static type analysis of object-oriented languages based on coinductive logic programming. Source code is translated to a logic program, then type-checking and inference problems amount to queries to be solved with respect to the resulting logic program. We exploit a coinductive semantics to deal with infinite terms and proofs produced by recursive types and methods. Thanks to the recent notion of structural resolution for coinductive logic programming, we are able to infer very precise type information, including a class of irrational recursive types causing non-termination for previously considered coinductive semantics. We also show how to transform logic programs to make them satisfy the preconditions for the operational semantics of structural resolution, and we prove this step does not affect the semantics of the logic program.
5-DoF Monocular Visual Localization Over Grid Based Floor
Venue: arXiv cs.RO 2017
Year: 2017

Reliable localization is one of the most important parts of an MAV system. Localization in an indoor GPS-denied environment is a relatively difficult problem. Current vision based algorithms track optical features to calculate odometry. We present a novel localization method which can be applied in an environment having orthogonal sets of equally spaced lines to form a grid. With the help of a monocular camera and using the properties of the grid-lines below, the MAV is localized inside each sub-cell of the grid and consequently over the entire grid for a relative localization over the grid. We demonstrate the effectiveness of our system onboard a customized MAV platform. The experimental results show that our method provides accurate 5-DoF localization over grid lines and it can be performed in real-time.
Abstractions for AI-Based User Interfaces and Systems
Venue: arXiv cs.PL 2017
Year: 2017

Novel user interfaces based on artificial intelligence, such as natural-language agents, present new categories of engineering challenges. These systems need to cope with uncertainty and ambiguity, interface with machine learning algorithms, and compose information from multiple users to make decisions. We propose to treat these challenges as language-design problems. We describe three programming language abstractions for three core problems in intelligent system design. First, hypothetical worlds support nondeterministic search over spaces of alternative actions. Second, a feature type system abstracts the interaction between applications and learning algorithms. Finally, constructs for collaborative execution extend hypothetical worlds across multiple machines while controlling access to private data. We envision these features as first steps toward a complete language for implementing AI-based interfaces and applications.
Attack-Graph Threat Modeling Assessment of Ambulatory Medical Devices
Venue: arXiv cs.CR 2017
Year: 2017

The continued integration of technology into all aspects of society stresses the need to identify and understand the risk associated with assimilating new technologies. This necessity is heightened when technology is used for medical purposes like ambulatory devices that monitor a patient's vital signs. This integration creates environments that are conducive to malicious activities. The potential impact presents new challenges for the medical community. Hence, this research presents attack graph modeling as a viable solution to identifying vulnerabilities, assessing risk, and forming mitigation strategies to defend ambulatory medical devices from attackers. Common and frequent vulnerabilities and attack strategies related to the various aspects of ambulatory devices, including Bluetooth enabled sensors and Android applications are identified in the literature. Based on this analysis, this research presents an attack graph modeling example on a theoretical device that highlights vulnerabilities and mitigation strategies to consider when designing ambulatory devices with similar components.
Query-based Attention CNN for Text Similarity Map
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we introduce Query-based Attention CNN(QACNN) for Text Similarity Map, an end-to-end neural network for question answering. This network is composed of compare mechanism, two-staged CNN architecture with attention mechanism, and a prediction layer. First, the compare mechanism compares between the given passage, query, and multiple answer choices to build similarity maps. Then, the two-staged CNN architecture extracts features through word-level and sentence-level. At the same time, attention mechanism helps CNN focus more on the important part of the passage based on the query information. Finally, the prediction layer find out the most possible answer choice. We conduct this model on the MovieQA dataset using Plot Synopses only, and achieve 79.99% accuracy which is the state of the art on the dataset.
Secrecy-Optimized Resource Allocation for Device-to-Device Communication Underlaying Heterogeneous Networks
Venue: arXiv cs.IT 2017
Year: 2017

Device-to-device (D2D) communications recently have attracted much attention for its potential capability to improve spectral efficiency underlaying the existing heterogeneous networks (HetNets). Due to no sophisticated control, D2D user equipments (DUEs) themselves cannot resist eavesdropping or security attacks. It is urgent to maximize the secure capacity for both cellular users and DUEs. This paper formulates the radio resource allocation problem to maximize the secure capacity of DUEs for the D2D communication underlaying HetNets which consist of high power nodes and low power nodes. The optimization objective function with transmit bit rate and power constraints, which is non-convex and hard to be directly derived, is firstly transformed into matrix form. Then the equivalent convex form of the optimization problem is derived according to the Perron-Frobenius theory. A heuristic iterative algorithm based on the proximal theory is proposed to solve this equivalent convex problem through evaluating the proximal operator of Lagrange function. Numerical results show that the proposed radio resource allocation solution significantly improves the secure capacity with a fast convergence speed.
Deep Reinforcement Learning for Conversational AI
Venue: arXiv cs.AI 2017
Year: 2017

Deep reinforcement learning is revolutionizing the artificial intelligence field. Currently, it serves as a good starting point for constructing intelligent autonomous systems which offer a better knowledge of the visual world. It is possible to scale deep reinforcement learning with the use of deep learning and do amazing tasks such as use of pixels in playing video games. In this paper, key concepts of deep reinforcement learning including reward function, differences between reinforcement learning and supervised learning and models for implementation of reinforcement are discussed. Key challenges related to the implementation of reinforcement learning in conversational AI domain are identified as well as discussed in detail. Various conversational models which are based on deep reinforcement learning (as well as deep learning) are also discussed. In summary, this paper discusses key aspects of deep reinforcement learning which are crucial for designing an efficient conversational AI.
Confluence and Convergence in Probabilistically Terminating Reduction Systems
Venue: arXiv cs.PL 2017
Year: 2017

Convergence of an abstract reduction system (ARS) is the property that any derivation from an initial state will end in the same final state, a.k.a. normal form. We generalize this for probabilistic ARS as almost-sure convergence, meaning that the normal form is reached with probability one, even if diverging derivations may exist. We show and exemplify properties that can be used for proving almost-sure convergence of probabilistic ARS, generalizing known results from ARS.
Open Multi-Agent Systems: Gossiping with Random Arrivals and Departures
Venue: arXiv cs.MA 2017
Year: 2017

We consider open multi-agent systems. Unlike the systems usually studied in the literature, here agents may join or leave while the process studied takes place. The system composition and size evolve thus with time. We focus here on systems where the interactions between agents lead to pairwise gossip averages, and where agents either arrive or are replaced at random times. These events prevent any convergence of the system. Instead, we describe the expected system behavior by showing that the evolution of scaled moments of the state can be characterized by a 2-dimensional (possibly time-varying) linear dynamical system. We apply this technique to two cases : (i) systems with fixed size where leaving agents are immediately replaced, and (ii) systems where new agents keep arriving without ever leaving, and whose size grows thus unbounded.
Performance of Android Forensics Data Recovery Tools
Venue: arXiv cs.CR 2017
Year: 2017

Recovering deleted or hidden data is among most important duties of forensics investigators. Extensive utilisation of smartphones as subject, objects or tools of crime made them an important part of residual forensics. This chapter investigates the effectiveness of mobile forensic data recovery tools in recovering evidences from a Samsung Galaxy S2 i9100 Android phone. We seek to determine the amount of data that could be recovered using Phone image carver, Access data FTK, Foremost, Diskdigger, and Recover My File forensic tools. The findings reflected the difference between recovery capacities of studied tools showing their suitability in their specialised contexts only.
Certified Non-Confluence with ConCon 1.5
Venue: arXiv cs.LO 2017
Year: 2017

We present three methods to check CTRSs for non-confluence: (1) an ad hoc method for 4-CTRSs, (2) a specialized method for unconditional critical pairs, and finally, (3) a method that employs conditional narrowing to find non-confluence witnesses. We shortly describe our implementation of these methods in ConCon, then look into their certification with CeTA, and finally conclude with experiments on the confluence problems database (Cops).
The Dominating Set Problem in Geometric Intersection Graphs
Venue: arXiv cs.CG 2017
Year: 2017

We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.
VST-Flow: Fine-grained low-level reasoning about real-world C code
Venue: arXiv cs.LO 2017
Year: 2017

We show how support for information-flow security proofs could be added on top of the Verified Software Toolchain (VST). We discuss several attempts to define information flow security in a VST-compatible way, and present a statement of information flow security in "continuation-passing" style. Moreover, we present Hoare rules augmented with information flow control assertions, and sketch how these rules could be proven sound with respect to the definition given before. We also discuss how this can be implemented in the Coq proof assistant, and how VST's proof automation framework (VST-Floyd) can be adapted to support convenient information flow security proofs.
Detecting Faces Using Region-based Fully Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Face detection has achieved great success using the region-based methods. In this report, we propose a region-based face detector applying deep networks in a fully convolutional fashion, named Face R-FCN. Based on Region-based Fully Convolutional Networks (R-FCN), our face detector is more accurate and computational efficient compared with the previous R-CNN based face detectors. In our approach, we adopt the fully convolutional Residual Network (ResNet) as the backbone network. Particularly, We exploit several new techniques including position-sensitive average pooling, multi-scale training and testing and on-line hard example mining strategy to improve the detection accuracy. Over two most popular and challenging face detection benchmarks, FDDB and WIDER FACE, Face R-FCN achieves superior performance over state-of-the-arts.
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Venue: arXiv cs.CC 2017
Year: 2017

In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among $n$ Boolean vectors in $d$ dimensions. The OV Conjecture (OVC) posits that OV requires $n^{2-o(1)}$ time to solve, for all $d=ω(\log n)$. Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in $P$. We prove that OVC is true in several computational models of interest: * For all sufficiently large $n$ and $d$, OV for $n$ vectors in $\{0,1\}^d$ has branching program complexity $\tildeΘ(n\cdot \min(n,2^d))$. In particular, the lower bounds match the upper bounds up to polylog factors. * OV has Boolean formula complexity $\tildeΘ(n\cdot \min(n,2^d))$, over all complete bases of $O(1)$ fan-in. * OV requires $\tildeΘ(n\cdot \min(n,2^d))$ wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in. Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV. The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the "average case" even for $AC^0$ formulas: * For every fixed $p \in (0,1)$ there is an $ε_p > 0$ such that for every $n$ and $d$, OV instances where input bits are independently set to $1$ with probability $p$ (and $0$ otherwise) can be solved with $AC^0$ formulas of size $O(n^{2-ε_p})$, on all but a $o_n(1)$ fraction of instances.
Conversational Exploratory Search via Interactive Storytelling
Venue: arXiv cs.HC 2017
Year: 2017

Conversational interfaces are likely to become more efficient, intuitive and engaging way for human-computer interaction than today's text or touch-based interfaces. Current research efforts concerning conversational interfaces focus primarily on question answering functionality, thereby neglecting support for search activities beyond targeted information lookup. Users engage in exploratory search when they are unfamiliar with the domain of their goal, unsure about the ways to achieve their goals, or unsure about their goals in the first place. Exploratory search is often supported by approaches from information visualization. However, such approaches cannot be directly translated to the setting of conversational search. In this paper we investigate the affordances of interactive storytelling as a tool to enable exploratory search within the framework of a conversational interface. Interactive storytelling provides a way to navigate a document collection in the pace and order a user prefers. In our vision, interactive storytelling is to be coupled with a dialogue-based system that provides verbal explanations and responsive design. We discuss challenges and sketch the research agenda required to put this vision into life.
A Fair Individual Rate Comparison between MIMO-NOMA and MIMO-OMA
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we compare the individual rate of MIMO-NOMA and MIMO-OMA when users are paired into clusters. A power allocation (PA) strategy is proposed, which ensures that MIMO-NOMA achieves a higher individual rate for each user than MIMO-OMA with arbitrary PA and optimal degrees of freedom split. In addition, a special case with equal degrees of freedom and arbitrary PA for OMA is considered, for which the individual rate superiority of NOMA still holds. Moreover, it is shown that NOMA can attain better fairness through appropriate PA. Finally, simulations are carried out, which validate the developed analytical results.
Recursive Binary Neural Network Learning Model with 2.28b/Weight Storage Requirement
Venue: arXiv cs.NE 2017
Year: 2017

This paper presents a storage-efficient learning model titled Recursive Binary Neural Networks for sensing devices having a limited amount of on-chip data storage such as < 100's kilo-Bytes. The main idea of the proposed model is to recursively recycle data storage of synaptic weights (parameters) during training. This enables a device with a given storage constraint to train and instantiate a neural network classifier with a larger number of weights on a chip and with a less number of off-chip storage accesses. This enables higher classification accuracy, shorter training time, less energy dissipation, and less on-chip storage requirement. We verified the training model with deep neural network classifiers and the permutation-invariant MNIST benchmark. Our model uses only 2.28 bits/weight while for the same data storage constraint achieving ~1% lower classification error as compared to the conventional binary-weight learning model which yet has to use 8 to 16 bit storage per weight. To achieve the similar classification error, the conventional binary model requires ~4x more data storage for weights than the proposed model.
Understanding System Characteristics of Online Erasure Coding on Scalable, Distributed and Large-Scale SSD Array Systems
Venue: arXiv cs.DC 2017
Year: 2017

Large-scale systems with arrays of solid state disks (SSDs) have become increasingly common in many computing segments. To make such systems resilient, we can adopt erasure coding such as Reed-Solomon (RS) code as an alternative to replication because erasure coding can offer a significantly lower storage cost than replication. To understand the impact of using erasure coding on system performance and other system aspects such as CPU utilization and network traffic, we build a storage cluster consisting of approximately one hundred processor cores with more than fifty high-performance SSDs, and evaluate the cluster with a popular open-source distributed parallel file system, Ceph. Then we analyze behaviors of systems adopting erasure coding from the following five viewpoints, compared with those of systems using replication: (1) storage system I/O performance; (2) computing and software overheads; (3) I/O amplification; (4) network traffic among storage nodes; (5) the impact of physical data layout on performance of RS-coded SSD arrays. For all these analyses, we examine two representative RS configurations, which are used by Google and Facebook file systems, and compare them with triple replication that a typical parallel file system employs as a default fault tolerance mechanism. Lastly, we collect 54 block-level traces from the cluster and make them available for other researchers.
One Leak Will Sink A Ship: WebRTC IP Address Leaks
Venue: arXiv cs.CR 2017
Year: 2017

The introduction of the WebRTC API to modern browsers has brought about a new threat to user privacy. This API causes a range of client IP addresses to become available to a visited website via JavaScript even if a VPN is in use. This a potentially serious problem for users utilizing VPN services for anonymity. In order to better understand the magnitude of this issue, we tested widely used browsers and VPN services to discover which client IP addresses can be revealed and in what circumstances. In most cases, at least one of the client addresses is leaked. The number and type of leaked IP addresses are affected by the choices of browser and VPN service, meaning that privacy-sensitive users should choose their browser and their VPN provider with care. We conclude by proposing countermeasures which can be used to help mitigate this issue.
"How May I Help You?": Modeling Twitter Customer Service Conversations Using Fine-Grained Dialogue Acts
Venue: arXiv cs.CL 2017
Year: 2017

Given the increasing popularity of customer service dialogue on Twitter, analysis of conversation data is essential to understand trends in customer and agent behavior for the purpose of automating customer service interactions. In this work, we develop a novel taxonomy of fine-grained "dialogue acts" frequently observed in customer service, showcasing acts that are more suited to the domain than the more generic existing taxonomies. Using a sequential SVM-HMM model, we model conversation flow, predicting the dialogue act of a given turn in real-time. We characterize differences between customer and agent behavior in Twitter customer service conversations, and investigate the effect of testing our system on different customer service industries. Finally, we use a data-driven approach to predict important conversation outcomes: customer satisfaction, customer frustration, and overall problem resolution. We show that the type and location of certain dialogue acts in a conversation have a significant effect on the probability of desirable and undesirable outcomes, and present actionable rules based on our findings. The patterns and rules we derive can be used as guidelines for outcome-driven automated customer service platforms.
Multivariable codes in principal ideal polynomial quotient rings with applications to additive modular bivariate codes over $\mathbb{F}_4$
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we study the structure of multivariable modular codes over finite chain rings when the ambient space is a principal ideal ring. We also provide some applications to additive modular codes over the finite field $\mathbb{F}_4$.