OpenRaiser/Intern-Atlas huggingface dataset:
Enrichment of OntoSenseNet: Adding a Sense-annotated Telugu lexicon
Venue: arXiv cs.CL 2018
Year: 2018

The paper describes the enrichment of OntoSenseNet - a verb-centric lexical resource for Indian Languages. This resource contains a newly developed Telugu-Telugu dictionary. It is important because native speakers can better annotate the senses when both the word and its meaning are in Telugu. Hence efforts are made to develop a soft copy of Telugu dictionary. Our resource also has manually annotated gold standard corpus consisting 8483 verbs, 253 adverbs and 1673 adjectives. Annotations are done by native speakers according to defined annotation guidelines. In this paper, we provide an overview of the annotation procedure and present the validation of our resource through inter-annotator agreement. Concepts of sense-class and sense-type are discussed. Additionally, we discuss the potential of lexical sense-annotated corpora in improving word sense disambiguation (WSD) tasks. Telugu WordNet is crowd-sourced for annotation of individual words in synsets and is compared with the developed sense-annotated lexicon (OntoSenseNet) to examine the improvement. Also, we present a special categorization (spatio-temporal classification) of adjectives.
BFS Enumeration for Breaking Symmetries in Graphs
Venue: arXiv cs.DS 2018
Year: 2018

There are numerous NP-hard combinatorial problems which involve searching for an undirected graph satisfying a certain property. One way to solve such problems is to translate a problem into an instance of the boolean satisfiability (SAT) or constraint satisfaction (CSP) problem. Such reduction usually can give rise to numerous isomorphic representations of the same graph. One way to reduce the search space and speed up the search under these conditions is to introduce symmetrybreaking predicates. In this paper we introduce three novel and practically effective symmetry-breaking predicates for an undirected connected graph search based on breadth-first search (BFS) enumeration and compare with existing symmetry-breaking methods on several graph problems.
Probabilistic Value-Deviation-Bounded Integer Codes for Approximate Communication
Venue: arXiv cs.IT 2018
Year: 2018

When computing systems can tolerate the effects of errors or erasures in their communicated data values, they can trade this tolerance for improved resource efficiency. One method for enabling this tradeoff in the I/O subsystems of computing systems, is to use channel codes that reduce the power needed to send bits on a channel in exchange for bounded errors and erasures on numeric program values---value-deviation-bounded (VDB) codes. Unlike rate distortion codes, which guarantee a bound on the expected value of channel distortion, the probabilistic VDB codes we present guarantee any desired tail distribution on integer distances of words transmitted over a channel. We extend prior work to present tighter upper bounds on the efficiency for VDB codes. We present a new probabilistic VDB encoder that lowers power dissipation in exchange for bounded channel integer distortions. The code we present takes the peculiar approach of changing the channel bit error rate across the ordinal bit positions in a word to reduce power dissipation. We implement the code table generator in a software tool built on the dReal SMT solver and we validate the generated codes using Monte Carlo simulation. We present one realization of hardware to implement the technique, requiring 2 mm$^2$ of circuit board area and dissipating less than 0.5 $μ$W.
An Approach to Static Performance Guarantees for Programs with Run-time Checks
Venue: arXiv cs.PL 2018
Year: 2018

Instrumenting programs for performing run-time checking of properties, such as regular shapes, is a common and useful technique that helps programmers detect incorrect program behaviors. This is specially true in dynamic languages such as Prolog. However, such run-time checks inevitably introduce run-time overhead (in execution time, memory, energy, etc.). Several approaches have been proposed for reducing such overhead, such as eliminating the checks that can statically be proved to always succeed, and/or optimizing the way in which the (remaining) checks are performed. However, there are cases in which it is not possible to remove all checks statically (e.g., open libraries which must check their interfaces, complex properties, unknown code, etc.) and in which, even after optimizations, these remaining checks still may introduce an unacceptable level of overhead. It is thus important for programmers to be able to determine the additional cost due to the run-time checks and compare it to some notion of admissible cost. The common practice used for estimating run-time checking overhead is profiling, which is not exhaustive by nature. Instead, we propose a method that uses static analysis to estimate such overhead, with the advantage that the estimations are functions parameterized by input data sizes. Unlike profiling, this approach can provide guarantees for all possible execution traces, and allows assessing how the overhead grows as the size of the input grows. Our method also extends an existing assertion verification framework to express "admissible" overheads, and statically and automatically checks whether the instrumented program conforms with such specifications. Finally, we present an experimental evaluation of our approach that suggests that our method is feasible and promising.
Traceability in the Wild: Automatically Augmenting Incomplete Trace Links
Venue: arXiv cs.SE 2018
Year: 2018

Software and systems traceability is widely accepted as an essential element for supporting many software development tasks. Today's version control systems provide inbuilt features that allow developers to tag each commit with one or more issue ID, thereby providing the building blocks from which project-wide traceability can be established between feature requests, bug fixes, commits, source code, and specific developers. However, our analysis of six open source projects showed that on average only 60% of the commits were linked to specific issues. Without these fundamental links the entire set of project-wide links will be incomplete, and therefore not trustworthy. In this paper we address the fundamental problem of missing links between commits and issues. Our approach leverages a combination of process and text-related features characterizing issues and code changes to train a classifier to identify missing issue tags in commit messages, thereby generating the missing links. We conducted a series of experiments to evaluate our approach against six open source projects and showed that it was able to effectively recommend links for tagging issues at an average of 96% recall and 33% precision. In a related task for augmenting a set of existing trace links, the classifier returned precision at levels greater than 89% in all projects and recall of 50%
PRIF: A Privacy-Preserving Interest-Based Forwarding Scheme for Social Internet of Vehicles
Venue: arXiv cs.CR 2018
Year: 2018

Recent advances in Socially Aware Networks (SANs) have allowed its use in many domains, out of which social Internet of vehicles (SIOV) is of prime importance. SANs can provide a promising routing and forwarding paradigm for SIOV by using interest-based communication. Though able to improve the forwarding performance, existing interest-based schemes fail to consider the important issue of protecting users' interest information. In this paper, we propose a PRivacy-preserving Interest-based Forwarding scheme (PRIF) for SIOV, which not only protects the interest information, but also improves the forwarding performance. We propose a privacy-preserving authentication protocol to recognize communities among mobile nodes. During data routing and forwarding, a node can know others' interests only if they are affiliated with the same community. Moreover, to improve forwarding performance, a new metric {\em community energy} is introduced to indicate vehicular social proximity. Community energy is generated when two nodes encounter one another and information is shared among them. PRIF considers this energy metric to select forwarders towards the destination node or the destination community. Security analysis indicates PRIF can protect nodes' interest information. In addition, extensive simulations have been conducted to demonstrate that PRIF outperforms the existing algorithms including the BEEINFO, Epidemic, and PRoPHET.
e-SAFE: Secure, Efficient and Forensics-Enabled Access to Implantable Medical Devices
Venue: arXiv cs.CR 2018
Year: 2018

To facilitate monitoring and management, modern Implantable Medical Devices (IMDs) are often equipped with wireless capabilities, which raise the risk of malicious access to IMDs. Although schemes are proposed to secure the IMD access, some issues are still open. First, pre-sharing a long-term key between a patient's IMD and a doctor's programmer is vulnerable since once the doctor's programmer is compromised, all of her patients suffer; establishing a temporary key by leveraging proximity gets rid of pre-shared keys, but as the approach lacks real authentication, it can be exploited by nearby adversaries or through man-in-the-middle attacks. Second, while prolonging the lifetime of IMDs is one of the most important design goals, few schemes explore to lower the communication and computation overhead all at once. Finally, how to safely record the commands issued by doctors for the purpose of forensics, which can be the last measure to protect the patients' rights, is commonly omitted in the existing literature. Motivated by these important yet open problems, we propose an innovative scheme e-SAFE, which significantly improves security and safety, reduces the communication overhead and enables IMD-access forensics. We present a novel lightweight compressive sensing based encryption algorithm to encrypt and compress the IMD data simultaneously, reducing the data transmission overhead by over 50% while ensuring high data confidentiality and usability. Furthermore, we provide a suite of protocols regarding device pairing, dual-factor authentication, and accountability-enabled access. The security analysis and performance evaluation show the validity and efficiency of the proposed scheme.
Principal Component Analysis: A Natural Approach to Data Exploration
Venue: arXiv cs.CE 2018
Year: 2018

Principal component analysis (PCA) is often used for analyzing data in the most diverse areas. In this work, we report an integrated approach to several theoretical and practical aspects of PCA. We start by providing, in an intuitive and accessible manner, the basic principles underlying PCA and its applications. Next, we present a systematic, though no exclusive, survey of some representative works illustrating the potential of PCA applications to a wide range of areas. An experimental investigation of the ability of PCA for variance explanation and dimensionality reduction is also developed, which confirms the efficacy of PCA and also shows that standardizing or not the original data can have important effects on the obtained results. Overall, we believe the several covered issues can assist researchers from the most diverse areas in using and interpreting PCA.
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Venue: arXiv cs.CC 2018
Year: 2018

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $Δ+1$ to one of product-depth $Δ$ in the multilinear setting. We show that for every positive $Δ= Δ(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(Δ)}$ on $n$ variables that can be computed by a multilinear formula of product-depth $Δ+1$ and size $O(n)$, but not by any multilinear circuit of product-depth $Δ$ and size less than $\exp(n^{Ω(1/Δ)})$. This result is tight up to the constant implicit in the double exponent for all $Δ= o(\log n/\log \log n).$ This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case $Δ= 1.$ Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.
Quootstrap: Scalable Unsupervised Extraction of Quotation-Speaker Pairs from Large News Corpora via Bootstrapping
Venue: arXiv cs.SI 2018
Year: 2018

We propose Quootstrap, a method for extracting quotations, as well as the names of the speakers who uttered them, from large news corpora. Whereas prior work has addressed this problem primarily with supervised machine learning, our approach follows a fully unsupervised bootstrapping paradigm. It leverages the redundancy present in large news corpora, more precisely, the fact that the same quotation often appears across multiple news articles in slightly different contexts. Starting from a few seed patterns, such as ["Q", said S.], our method extracts a set of quotation-speaker pairs (Q, S), which are in turn used for discovering new patterns expressing the same quotations; the process is then repeated with the larger pattern set. Our algorithm is highly scalable, which we demonstrate by running it on the large ICWSM 2011 Spinn3r corpus. Validating our results against a crowdsourced ground truth, we obtain 90% precision at 40% recall using a single seed pattern, with significantly higher recall values for more frequently reported (and thus likely more interesting) quotations. Finally, we showcase the usefulness of our algorithm's output for computational social science by analyzing the sentiment expressed in our extracted quotations.
Visual Analytics for Explainable Deep Learning
Venue: arXiv cs.HC 2018
Year: 2018

Recently, deep learning has been advancing the state of the art in artificial intelligence to a new level, and humans rely on artificial intelligence techniques more than ever. However, even with such unprecedented advancements, the lack of explanation regarding the decisions made by deep learning models and absence of control over their internal processes act as major drawbacks in critical decision-making processes, such as precision medicine and law enforcement. In response, efforts are being made to make deep learning interpretable and controllable by humans. In this paper, we review visual analytics, information visualization, and machine learning perspectives relevant to this aim, and discuss potential challenges and future research directions.
ANNETT-O: An Ontology for Describing Artificial Neural Network Evaluation, Topology and Training
Venue: arXiv cs.AI 2018
Year: 2018

Deep learning models, while effective and versatile, are becoming increasingly complex, often including multiple overlapping networks of arbitrary depths, multiple objectives and non-intuitive training methodologies. This makes it increasingly difficult for researchers and practitioners to design, train and understand them. In this paper we present ANNETT-O, a much-needed, generic and computer-actionable vocabulary for researchers and practitioners to describe their deep learning configurations, training procedures and experiments. The proposed ontology focuses on topological, training and evaluation aspects of complex deep neural configurations, while keeping peripheral entities more succinct. Knowledge bases implementing ANNETT-O can support a wide variety of queries, providing relevant insights to users. In addition to a detailed description of the ontology, we demonstrate its suitability to the task via a number of hypothetical use-cases of increasing complexity.
Not quite unreasonable effectiveness of machine learning algorithms
Venue: arXiv cs.CV 2018
Year: 2018

State-of-the-art machine learning algorithms demonstrate close to absolute performance in selected challenges. We provide arguments that the reason can be in low variability of the samples and high effectiveness in learning typical patterns. Due to this fact, standard performance metrics do not reveal model capacity and new metrics are required for the better understanding of state-of-the-art.
Coalgebraic Determinization of Alternating Automata
Venue: arXiv cs.LO 2018
Year: 2018

Coalgebra is a currently quite active field, which aims to look at generic state-based systems (most prominently automata) from a very abstract point of view, mainly using tools from category theory. One of its achievements is to give a completely generic approach of determinization, unifying in an elegant manner non-deterministic automata, probabilistic automata or non-deterministic pushdown automata in one and the same model. However, the case of alternating automata fails to easily fit in this model. The aim of this internship was therefore to tackle this problem: can alternating automata also be determinized in the coalgebraic way? Does this give semantics that coincides with the concretely defined one? In this report, we give a positive answer to both questions. The main element of our construction is a distributive law, the definition of which has been for some time an open question.
A Machine Learning Approach To Prevent Malicious Calls Over Telephony Networks
Venue: arXiv cs.CR 2018
Year: 2018

Malicious calls, i.e., telephony spams and scams, have been a long-standing challenging issue that causes billions of dollars of annual financial loss worldwide. This work presents the first machine learning-based solution without relying on any particular assumptions on the underlying telephony network infrastructures. The main challenge of this decade-long problem is that it is unclear how to construct effective features without the access to the telephony networks' infrastructures. We solve this problem by combining several innovations. We first develop a TouchPal user interface on top of a mobile App to allow users tagging malicious calls. This allows us to maintain a large-scale call log database. We then conduct a measurement study over three months of call logs, including 9 billion records. We design 29 features based on the results, so that machine learning algorithms can be used to predict malicious calls. We extensively evaluate different state-of-the-art machine learning approaches using the proposed features, and the results show that the best approach can reduce up to 90% unblocked malicious calls while maintaining a precision over 99.99% on the benign call traffic. The results also show the models are efficient to implement without incurring a significant latency overhead. We also conduct ablation analysis, which reveals that using 10 out of the 29 features can reach a performance comparable to using all features.
Semi-Supervised Multi-Organ Segmentation via Deep Multi-Planar Co-Training
Venue: arXiv cs.CV 2018
Year: 2018

In multi-organ segmentation of abdominal CT scans, most existing fully supervised deep learning algorithms require lots of voxel-wise annotations, which are usually difficult, expensive, and slow to obtain. In comparison, massive unlabeled 3D CT volumes are usually easily accessible. Current mainstream works to address the semi-supervised biomedical image segmentation problem are mostly graph-based. By contrast, deep network based semi-supervised learning methods have not drawn much attention in this field. In this work, we propose Deep Multi-Planar Co-Training (DMPCT), whose contributions can be divided into two folds: 1) The deep model is learned in a co-training style which can mine consensus information from multiple planes like the sagittal, coronal, and axial planes; 2) Multi-planar fusion is applied to generate more reliable pseudo-labels, which alleviates the errors occurring in the pseudo-labels and thus can help to train better segmentation networks. Experiments are done on our newly collected large dataset with 100 unlabeled cases as well as 210 labeled cases where 16 anatomical structures are manually annotated by four radiologists and confirmed by a senior expert. The results suggest that DMPCT significantly outperforms the fully supervised method by more than 4% especially when only a small set of annotations is used.
IDEBench: A Benchmark for Interactive Data Exploration
Venue: arXiv cs.DB 2018
Year: 2018

Existing benchmarks for analytical database systems such as TPC-DS and TPC-H are designed for static reporting scenarios. The main metric of these benchmarks is the performance of running individual SQL queries over a synthetic database. In this paper, we argue that such benchmarks are not suitable for evaluating database workloads originating from interactive data exploration (IDE) systems where most queries are ad-hoc, not based on predefined reports, and built incrementally. As a main contribution, we present a novel benchmark called IDEBench that can be used to evaluate the performance of database systems for IDE workloads. As opposed to traditional benchmarks for analytical database systems, our goal is to provide more meaningful workloads and datasets that can be used to benchmark IDE query engines, with a particular focus on metrics that capture the trade-off between query performance and quality of the result. As a second contribution, this paper evaluates and discusses the performance results of selected IDE query engines using our benchmark. The study includes two commercial systems, as well as two research prototypes (IDEA, approXimateDB/XDB), and one traditional analytical database system (MonetDB).
Clustering and Retrieval Method of Immunological Memory Cell in Clonal Selection Algorithm
Venue: arXiv cs.NE 2018
Year: 2018

The clonal selection principle explains the basic features of an adaptive immune response to a antigenic stimulus. It established the idea that only those cells that recognize the antigens are selected to proliferate and differentiate. This paper explains a computational implementation of the clonal selection principle that explicitly takes into account the affinity maturation of the immune response. Antibodies generated by the clonal selection algorithm are clustered in some categories according to the affinity maturation, so that immunological memory cells which respond to the specified pathogen are created. Experimental results to classify the medical database of Coronary Heart Disease databases are reported. For the dataset, our proposed method shows the 99.6\% classification capability of training data.
An Adaptive Observer for Sensorless Control of the Levitated Ball Using Signal Injection
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we address the problem of sensorless control of the 1-DOF magnetic levitation system. Assuming that only the current and the voltage are measurable, we design an adaptive state observer using the technique of signal injection. Our main contribution is to propose a new filter to identify the virtual output generated by the signal injection. It is shown that this filter, designed using the dynamic regressor extension and mixing estimator, outperforms the classical one. Two additional features of the proposed observer are that (i) it does not require the knowledge of the electrical resistance, which is also estimated on-line and (ii) exponential convergence to a tunable residual set is guaranteed without excitation assumptions. The observer is then applied, in a certainty equivalent way, to a full state-feedback control law to obtain the sensorless controller, whose performance is assessed via simulations and experiments.