OpenRaiser/Intern-Atlas huggingface dataset:
Eclipse: Generalizing kNN and Skyline
Venue: arXiv cs.DB 2019
Year: 2019

$k$ nearest neighbor ($k$NN) queries and skyline queries are important operators on multi-dimensional data points. Given a query point, $k$NN query returns the $k$ nearest neighbors based on a scoring function such as a weighted sum of the attributes, which requires predefined attribute weights (or preferences). Skyline query returns all possible nearest neighbors for any monotonic scoring functions without requiring attribute weights but the number of returned points can be prohibitively large. We observe that both $k$NN and skyline are inflexible and cannot be easily customized. In this paper, we propose a novel \emph{eclipse} operator that generalizes the classic $1$NN and skyline queries and provides a more flexible and customizable query solution for users. In eclipse, users can specify rough and customizable attribute preferences and control the number of returned points. We show that both $1$NN and skyline are instantiations of eclipse. To process eclipse queries, we propose a baseline algorithm with time complexity $O(n^22^{d-1})$, and an improved $O(n\log ^{d-1}n)$ time transformation-based algorithm, where $n$ is the number of points and $d$ is the number of dimensions. Furthermore, we propose a novel index-based algorithm utilizing duality transform with much better efficiency. The experimental results on the real NBA dataset and the synthetic datasets demonstrate the effectiveness of the eclipse operator and the efficiency of our eclipse algorithms.
Towards Stable and Efficient Training of Verifiably Robust Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by a factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound propagation (IBP) based training is efficient and significantly outperforms linear relaxation based methods on many tasks, yet it may suffer from stability issues since the bounds are much looser especially at the beginning of training. In this paper, we propose a new certified adversarial training method, CROWN-IBP, by combining the fast IBP bounds in a forward bounding pass and a tight linear relaxation based bound, CROWN, in a backward bounding pass. CROWN-IBP is computationally efficient and consistently outperforms IBP baselines on training verifiably robust neural networks. We conduct large scale experiments on MNIST and CIFAR datasets, and outperform all previous linear relaxation and bound propagation based certified defenses in $\ell_\infty$ robustness. Notably, we achieve 7.02% verified test error on MNIST at $ε=0.3$, and 66.94% on CIFAR-10 with $ε=8/255$. Code is available at https://github.com/deepmind/interval-bound-propagation (TensorFlow) and https://github.com/huanzhang12/CROWN-IBP (PyTorch).
IITP at MEDIQA 2019: Systems Report for Natural Language Inference, Question Entailment and Question Answering
Venue: arXiv cs.CL 2019
Year: 2019

This paper presents the experiments accomplished as a part of our participation in the MEDIQA challenge, an (Abacha et al., 2019) shared task. We participated in all the three tasks defined in this particular shared task. The tasks are viz. i. Natural Language Inference (NLI) ii. Recognizing Question Entailment(RQE) and their application in medical Question Answering (QA). We submitted runs using multiple deep learning based systems (runs) for each of these three tasks. We submitted five system results in each of the NLI and RQE tasks, and four system results for the QA task. The systems yield encouraging results in all three tasks. The highest performance obtained in NLI, RQE and QA tasks are 81.8%, 53.2%, and 71.7%, respectively.
Time Synchronization in 5G Wireless Edge: Requirements and Solutions for Critical-MTC
Venue: arXiv cs.IT 2019
Year: 2019

Wireless edge is about distributing intelligence to the wireless devices wherein the distribution of accurate time reference is essential for time-critical machine-type communication (cMTC). In 5G-based cMTC, enabling time synchronization in the wireless edge means moving beyond the current synchronization needs and solutions in 5G radio access. In this article, we analyze the device-level synchronization needs of potential cMTC applications: industrial automation, power distribution, vehicular communication, and live audio/video production. We present an over-the-air (OTA) synchronization scheme comprised of 5G air interface parameters, and discuss their associated timing errors. We evaluate the estimation error in device-to-base station propagation delay from timing advance (TA) under random errors and show how to reduce the estimation error. In the end, we identify the random errors specific to dense multipath fading environments and discuss countermeasures.
A/B Testing Measurement Framework for Recommendation Models Based on Expected Revenue
Venue: arXiv cs.IR 2019
Year: 2019

We provide a method to determine whether a new recommendation system improves the revenue per visit (RPV) compared to the status quo. We achieve our goal by splitting RPV into conversion rate and average order value (AOV). We use the two-part test suggested by Lachenbruch to determine if the data generating process in the new system is different. In cases that this test does not give us a definitive answer about the change in RPV, we propose two alternative tests to determine if RPV has changed. Both of these tests rely on the assumption that non-zero purchase values follow a log-normal distribution. We empirically validate this assumption using data collected at different points in time from Staples.com. On average, our method needs a smaller sample size than other methods. Furthermore, it does not require any subjective outlier removal. Finally, it characterizes the uncertainty around RPV by providing a confidence interval.
ViTa-SLAM: A Bio-inspired Visuo-Tactile SLAM for Navigation while Interacting with Aliased Environments
Venue: arXiv cs.RO 2019
Year: 2019

RatSLAM is a rat hippocampus-inspired visual Simultaneous Localization and Mapping (SLAM) framework capable of generating semi-metric topological representations of indoor and outdoor environments. Whisker-RatSLAM is a 6D extension of the RatSLAM and primarily focuses on object recognition by generating point clouds of objects based on whisking information. This paper introduces a novel extension to both former works that is referred to as ViTa-SLAM that harnesses both vision and tactile information for performing SLAM. This not only allows the robot to perform natural interaction with the environment whilst navigating, as is normally seen in nature, but also provides a mechanism to fuse non-unique tactile and unique visual data. Compared to the former works, our approach can handle ambiguous scenes in which one sensor alone is not capable of identifying false-positive loop-closures.
User Curated Shaping of Expressive Performances
Venue: arXiv cs.SD 2019
Year: 2019

Musicians produce individualized, expressive performances by manipulating parameters such as dynamics, tempo and articulation. This manipulation of expressive parameters is informed by elements of score information such as pitch, meter, and tempo and dynamics markings (among others). In this paper we present an interactive interface that gives users the opportunity to explore the relationship between structural elements of a score and expressive parameters. This interface draws on the basis function models, a data-driven framework for expressive performance. In this framework, expressive parameters are modeled as a function of score features, i.e., numerical encodings of specific aspects of a musical score, using neural networks. With the proposed interface, users are able to weight the contribution of individual score features and understand how an expressive performance is constructed.
A New Family of Tractable Ising Models
Venue: arXiv cs.DS 2019
Year: 2019

We present a new family of zero-field Ising models over N binary variables/spins obtained by consecutive "gluing" of planar and $O(1)$-sized components along with subsets of at most three vertices into a tree. The polynomial time algorithm of the dynamic programming type for solving exact inference (partition function computation) and sampling consists of a sequential application of an efficient (for planar) or brute-force (for $O(1)$-sized) inference and sampling to the components as a black box. To illustrate the utility of the new family of tractable graphical models, we first build an $O(N^{3/2})$ algorithm for inference and sampling of the K5-minor-free zero-field Ising models - an extension of the planar zero-field Ising models - which is neither genus- nor treewidth-bounded. Second, we demonstrate empirically an improvement in the approximation quality of the NP-hard problem of the square-grid Ising model (with non-zero field) inference.
Linear-time Hierarchical Community Detection
Venue: arXiv cs.SI 2019
Year: 2019

Community detection in graphs has many important and fundamental applications including in distributed systems, compression, image segmentation, divide-and-conquer graph algorithms such as nested dissection, document and word clustering, circuit design, among many others. Finding these densely connected regions of graphs remains an important and challenging problem. Most work has focused on scaling up existing methods to handle large graphs. These methods often partition the graph into two or more communities. In this work, we focus on the problem of hierarchical community detection (i.e., finding a hierarchy of dense community structures going from the lowest granularity to the largest) and describe an approach that runs in linear time with respect to the number of edges and thus fast and efficient for large-scale networks. The experiments demonstrate the effectiveness of the approach quantitatively. Finally, we show an application of it for visualizing large networks with hundreds of thousands of nodes/links.
Can neural networks understand monotonicity reasoning?
Venue: arXiv cs.CL 2019
Year: 2019

Monotonicity reasoning is one of the important reasoning skills for any intelligent natural language inference (NLI) model in that it requires the ability to capture the interaction between lexical and syntactic structures. Since no test set has been developed for monotonicity reasoning with wide coverage, it is still unclear whether neural models can perform monotonicity reasoning in a proper way. To investigate this issue, we introduce the Monotonicity Entailment Dataset (MED). Performance by state-of-the-art NLI models on the new test set is substantially worse, under 55%, especially on downward reasoning. In addition, analysis using a monotonicity-driven data augmentation method showed that these models might be limited in their generalization ability in upward and downward reasoning.
Approximate Normalization for Gradual Dependent Types
Venue: arXiv cs.PL 2019
Year: 2019

Dependent types help programmers write highly reliable code. However, this reliability comes at a cost: it can be challenging to write new prototypes in (or migrate old code to) dependently-typed programming languages. Gradual typing makes static type disciplines more flexible, so an appropriate notion of gradual dependent types could fruitfully lower this cost. However, dependent types raise unique challenges for gradual typing. Dependent typechecking involves the execution of program code, but gradually-typed code can signal runtime type errors or diverge. These runtime errors threaten the soundness guarantees that make dependent types so attractive, while divergence spoils the type-driven programming experience. This paper presents GDTL, a gradual dependently-typed language that emphasizes pragmatic dependently-typed programming. GDTL fully embeds both an untyped and dependently-typed language, and allows for smooth transitions between the two. In addition to gradual types we introduce gradual terms , which allow the user to be imprecise in type indices and to omit proof terms; runtime checks ensure type safety . To account for nontermination and failure, we distinguish between compile-time normalization and run-time execution: compile-time normalization is approximate but total, while runtime execution is exact , but may fail or diverge. We prove that GDTL has decidable typechecking and satisfies all the expected properties of gradual languages. In particular, GDTL satisfies the static and dynamic gradual guarantees: reducing type precision preserves typedness, and altering type precision does not change program behavior outside of dynamic type failures. To prove these properties, we were led to establish a novel normalization gradual guarantee that captures the monotonicity of approximate normalization with respect to imprecision.
Physical Integrity Attack Detection of Surveillance Camera with Deep Learning Based Video Frame Interpolation
Venue: arXiv cs.CR 2019
Year: 2019

Surveillance cameras, which is a form of Cyber Physical System, are deployed extensively to provide visual surveillance monitoring of activities of interest or anomalies. However, these cameras are at risks of physical security attacks against their physical attributes or configuration like tampering of their recording coverage, camera positions or recording configurations like focus and zoom factors. Such adversarial alteration of physical configuration could also be invoked through cyber security attacks against the camera's software vulnerabilities to administratively change the camera's physical configuration settings. When such Cyber Physical attacks occur, they affect the integrity of the targeted cameras that would in turn render these cameras ineffective in fulfilling the intended security functions. There is a significant measure of research work in detection mechanisms of cyber-attacks against these Cyber Physical devices, however it is understudied area with such mechanisms against integrity attacks on physical configuration. This research proposes the use of the novel use of deep learning algorithms to detect such physical attacks originating from cyber or physical spaces. Additionally, we proposed the novel use of deep learning-based video frame interpolation for such detection that has comparatively better performance to other anomaly detectors in spatiotemporal environments.
A Secure Consensus Protocol for Sidechains
Venue: arXiv cs.CR 2019
Year: 2019

Sidechain technology has been envisioned as a promising solution to accelerate today's public blockchains in terms of scalability and interoperability. By relying on the mainchain for security, different sidechains can formulate their own rules to reach consensus. Although the literature has considered the possibility of using consensus protocols in the sidechain, so far a tailor-made consensus protocol for sidechains with high performance and formal security proof has not been attempted. To fill this gap, we introduce Cumulus, a low overhead, highly efficient, security provable sidechain protocol. Cumulus makes use of smart contracts to ensure that only one block proposed in the sidechain will be enforced on the mainchain in each round, thereby achieving consensus in an efficient manner. We give a formal specification of Cumulus which ensures safety and liveness without any online requirements of clients. For security analysis, we provide formal security definitions and proofs under Universally Composable Security (UCS) model. As a proof of concept, we implement Cumulus and evaluate it in an Ethereum testnet.
Image-based 3D Object Reconstruction: State-of-the-Art and Trends in the Deep Learning Era
Venue: arXiv cs.CV 2019
Year: 2019

3D reconstruction is a longstanding ill-posed problem, which has been explored for decades by the computer vision, computer graphics, and machine learning communities. Since 2015, image-based 3D reconstruction using convolutional neural networks (CNN) has attracted increasing interest and demonstrated an impressive performance. Given this new era of rapid evolution, this article provides a comprehensive survey of the recent developments in this field. We focus on the works which use deep learning techniques to estimate the 3D shape of generic objects either from a single or multiple RGB images. We organize the literature based on the shape representations, the network architectures, and the training mechanisms they use. While this survey is intended for methods which reconstruct generic objects, we also review some of the recent works which focus on specific object classes such as human body shapes and faces. We provide an analysis and comparison of the performance of some key papers, summarize some of the open problems in this field, and discuss promising directions for future research.
Assessment of Urban Ecological Service value used in Urban Rail Transit Project
Venue: arXiv cs.OH 2019
Year: 2019

Ecosystem services refer to the ones human beings often obtain from the natural environment ecosystem. In order to solve the problem of environmental degradation, based on the Integrated Valuation of Ecosystem Services and Trade-offs (InVEST model), this paper makes innovation by adding the urban module that was not in the previous models, which can better deal with the evaluation of ecosystem services in urban scenarios.
Technical Report: Optimizing Human Involvement for Entity Matching and Consolidation
Venue: arXiv cs.DB 2019
Year: 2019

An end-to-end data integration system requires human feedback in several phases, including collecting training data for entity matching, debugging the resulting clusters, confirming transformations applied on these clusters for data standardization, and finally, reducing each cluster to a single, canonical representation (or "golden record"). The traditional wisdom is to sequentially apply the human feedback, obtained by asking specific questions, within some budget in each phase. However, these questions are highly correlated; the answer to one can influence the outcome of any of the phases of the pipeline. Hence, interleaving them has the potential to offer significant benefits. In this paper, we propose a human-in-the-loop framework that interleaves different types of questions to optimize human involvement. We propose benefit models to measure the quality improvement from asking a question, and cost models to measure the human time it takes to answer a question. We develop a question scheduling framework that judiciously selects questions to maximize the accuracy of the final golden records. Experimental results on three real-world datasets show that our holistic method significantly improves the quality of golden records from 70% to 90%, compared with the state-of-the-art approaches.
Large Intelligent Surface/Antennas (LISA): Making Reflective Radios Smart
Venue: arXiv cs.IT 2019
Year: 2019

Large intelligent surface/antennas (LISA), a two-dimensional artificial structure with a large number of reflective-surface/antenna elements, is a promising reflective radio technology to construct programmable wireless environments in a smart way. Specifically, each element of the LISA adjusts the reflection of the incident electromagnetic waves with unnatural properties, such as negative refraction, perfect absorption, and anomalous reflection, thus the wireless environments can be software-defined according to various design objectives. In this paper, we introduce the reflective radio basics, including backscattering principles, backscatter communication, and reflective relay, and the fundamentals and implementations of LISA technology. Then, we present an overview of the state-of-the-art research on emerging applications of LISA-aided wireless networks. Finally, the limitations, challenges, and open issues associated with LISA for future wireless applications are discussed.
Practical User Feedback-driven Internal Search Using Online Learning to Rank
Venue: arXiv cs.CL 2019
Year: 2019

We present a system, Spoke, for creating and searching internal knowledge base (KB) articles for organizations. Spoke is available as a SaaS (Software-as-a-Service) product deployed across hundreds of organizations with a diverse set of domains. Spoke continually improves search quality using conversational user feedback which allows it to provide better search experience than standard information retrieval systems without encoding any explicit domain knowledge. We achieve this by using a real-time online learning-to-rank (L2R) algorithm that automatically customizes relevance scoring for each organization deploying Spoke by using a query similarity kernel. The focus of this paper is on incorporating practical considerations into our relevance scoring function and algorithm that make Spoke easy to deploy and suitable for handling events that naturally happen over the life-cycle of any KB deployment. We show that Spoke outperforms competitive baselines by up to 41% in offline F1 comparisons.
A Computational-Hermeneutic Approach for Conceptual Explicitation
Venue: arXiv cs.AI 2019
Year: 2019

We present a computer-supported approach for the logical analysis and conceptual explicitation of argumentative discourse. Computational hermeneutics harnesses recent progresses in automated reasoning for higher-order logics and aims at formalizing natural-language argumentative discourse using flexible combinations of expressive non-classical logics. In doing so, it allows us to render explicit the tacit conceptualizations implicit in argumentative discursive practices. Our approach operates on networks of structured arguments and is iterative and two-layered. At one layer we search for logically correct formalizations for each of the individual arguments. At the next layer we select among those correct formalizations the ones which honor the argument's dialectic role, i.e. attacking or supporting other arguments as intended. We operate at these two layers in parallel and continuously rate sentences' formalizations by using, primarily, inferential adequacy criteria. An interpretive, logical theory will thus gradually evolve. This theory is composed of meaning postulates serving as explications for concepts playing a role in the analyzed arguments. Such a recursive, iterative approach to interpretation does justice to the inherent circularity of understanding: the whole is understood compositionally on the basis of its parts, while each part is understood only in the context of the whole (hermeneutic circle). We summarily discuss previous work on exemplary applications of human-in-the-loop computational hermeneutics in metaphysical discourse. We also discuss some of the main challenges involved in fully-automating our approach. By sketching some design ideas and reviewing relevant technologies, we argue for the technological feasibility of a highly-automated computational hermeneutics.