OpenRaiser/Intern-Atlas huggingface dataset:
Automated Extraction of Socio-political Events from News (AESPEN): Workshop and Shared Task Report
Venue: arXiv cs.CL 2020
Year: 2020

We describe our effort on automated extraction of socio-political events from news in the scope of a workshop and a shared task we organized at Language Resources and Evaluation Conference (LREC 2020). We believe the event extraction studies in computational linguistics and social and political sciences should further support each other in order to enable large scale socio-political event information collection across sources, countries, and languages. The event consists of regular research papers and a shared task, which is about event sentence coreference identification (ESCI), tracks. All submissions were reviewed by five members of the program committee. The workshop attracted research papers related to evaluation of machine learning methodologies, language resources, material conflict forecasting, and a shared task participation report in the scope of socio-political event information collection. It has shown us the volume and variety of both the data sources and event information collection approaches related to socio-political events and the need to fill the gap between automated text processing techniques and requirements of social and political sciences.
Stabilizing Congestion in Decentralized Record-Keepers
Venue: arXiv cs.CR 2020
Year: 2020

We argue that recent developments in proof-of-work consensus mechanisms can be used in accordance with advancements in formal verification techniques to build a distributed payment protocol that addresses important economic drawbacks from cost efficiency, scalability and adaptablity common to current decentralized record-keeping systems. We enable the protocol to autonomously adjust system throughput according to a feasibly computable statistic - system difficulty. We then provide a formal economic analysis of a decentralized market place for record-keeping that is consistent with our protocol design and show that, when block rewards are zero, the system admits stable, self-regulating levels of transaction fees and wait-times across varying levels of demand. We also provide an analysis of the various technological requirements needed to instantiate such a system in a commercially viable setting, and identify relevant research directions.
Probabilistic Hyperproperties with Nondeterminism
Venue: arXiv cs.LO 2020
Year: 2020

We study the problem of formalizing and checking probabilistic hyperproperties for models that allow nondeterminism in actions. We extend the temporal logic \HyperPCTL, which has been previously introduced for discrete-time Markov chains, to enable the specification of hyperproperties also for Markov decision processes. We generalize HyperPCTL by allowing explicit and simultaneous quantification over schedulers and probabilistic computation trees and show that it can express important quantitative requirements in security and privacy. We show that HyperPCTL model checking over MDPs is in general undecidable for quantification over probabilistic schedulers with memory, but restricting the domain to memoryless non-probabilistic schedulers turns the model checking problem decidable. Subsequently, we propose an SMT-based encoding for model checking this language and evaluate its performance.
Improved Computation-Communication Trade-Off for Coded Distributed Computing using Linear Dependence of Intermediate Values
Venue: arXiv cs.IT 2020
Year: 2020

In large scale distributed computing systems, communication overhead is one of the major bottlenecks. In the map-shuffle-reduce framework, which is one of the major distributed computing frameworks, the communication load among servers can be reduced by increasing the computation load of each server, that is, there is a trade-off between computation load and communication load. Recently, it has been shown that coded distributed computing (CDC) improves this trade-off relationship by letting servers encode their intermediate computation results. The original CDC scheme does not assume any special structures on the functions that servers compute. However, in actual problems, these functions often have some structures, and the trade-off relation may be further improved by using that structures. In this paper, we propose a new scheme that further improves the trade-off relationship by utilizing the linear dependency structure of the intermediate computation results. The intermediate values computed in the map phase can be considered as vectors on $\mathbb{F}_{2}$. In some applications, these intermediate values have a linear dependency and in such cases, it is sufficient for each server to send a basis of the linear subspace and linear combination coefficients. As a result, the proposed approach improves over the best-known computation-communication overhead trade-off in some applications.
Adaptive Rule Discovery for Labeling Text Data
Venue: arXiv cs.DB 2020
Year: 2020

Creating and collecting labeled data is one of the major bottlenecks in machine learning pipelines and the emergence of automated feature generation techniques such as deep learning, which typically requires a lot of training data, has further exacerbated the problem. While weak-supervision techniques have circumvented this bottleneck, existing frameworks either require users to write a set of diverse, high-quality rules to label data (e.g., Snorkel), or require a labeled subset of the data to automatically mine rules (e.g., Snuba). The process of manually writing rules can be tedious and time consuming. At the same time, creating a labeled subset of the data can be costly and even infeasible in imbalanced settings. This is due to the fact that a random sample in imbalanced settings often contains only a few positive instances. To address these shortcomings, we present Darwin, an interactive system designed to alleviate the task of writing rules for labeling text data in weakly-supervised settings. Given an initial labeling rule, Darwin automatically generates a set of candidate rules for the labeling task at hand, and utilizes the annotator's feedback to adapt the candidate rules. We describe how Darwin is scalable and versatile. It can operate over large text corpora (i.e., more than 1 million sentences) and supports a wide range of labeling functions (i.e., any function that can be specified using a context free grammar). Finally, we demonstrate with a suite of experiments over five real-world datasets that Darwin enables annotators to generate weakly-supervised labels efficiently and with a small cost. In fact, our experiments show that rules discovered by Darwin on average identify 40% more positive instances compared to Snuba even when it is provided with 1000 labeled instances.
Towards Interpretable Deep Learning Models for Knowledge Tracing
Venue: arXiv cs.LG 2020
Year: 2020

As an important technique for modeling the knowledge states of learners, the traditional knowledge tracing (KT) models have been widely used to support intelligent tutoring systems and MOOC platforms. Driven by the fast advancements of deep learning techniques, deep neural network has been recently adopted to design new KT models for achieving better prediction performance. However, the lack of interpretability of these models has painfully impeded their practical applications, as their outputs and working mechanisms suffer from the intransparent decision process and complex inner structures. We thus propose to adopt the post-hoc method to tackle the interpretability issue for deep learning based knowledge tracing (DLKT) models. Specifically, we focus on applying the layer-wise relevance propagation (LRP) method to interpret RNN-based DLKT model by backpropagating the relevance from the model's output layer to its input layer. The experiment results show the feasibility using the LRP method for interpreting the DLKT model's predictions, and partially validate the computed relevance scores from both question level and concept level. We believe it can be a solid step towards fully interpreting the DLKT models and promote their practical applications in the education domain.
Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
Venue: arXiv cs.DM 2020
Year: 2020

An acyclic edge coloring of a graph $G$ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiam{č}ik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree $Δ$ is acyclically edge $(Δ+ 2)$-colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph.
Panda: Partitioned Data Security on Outsourced Sensitive and Non-sensitive Data
Venue: arXiv cs.DB 2020
Year: 2020

Despite extensive research on cryptography, secure and efficient query processing over outsourced data remains an open challenge. This paper continues along with the emerging trend in secure data processing that recognizes that the entire dataset may not be sensitive, and hence, non-sensitivity of data can be exploited to overcome limitations of existing encryption-based approaches. We, first, provide a new security definition, entitled partitioned data security for guaranteeing that the joint processing of non-sensitive data (in cleartext) and sensitive data (in encrypted form) does not lead to any leakage. Then, this paper proposes a new secure approach, entitled query binning (QB) that allows secure execution of queries over non-sensitive and sensitive parts of the data. QB maps a query to a set of queries over the sensitive and non-sensitive data in a way that no leakage will occur due to the joint processing over sensitive and non-sensitive data. In particular, we propose secure algorithms for selection, range, and join queries to be executed over encrypted sensitive and cleartext non-sensitive datasets. Interestingly, in addition to improving performance, we show that QB actually strengthens the security of the underlying cryptographic technique by preventing size, frequency-count, and workload-skew attacks.
Robust asymptotic stability of two-wheels differential drive mobile robot
Venue: arXiv cs.RO 2020
Year: 2020

The paper proposes the stable motion control law design method for non-honomic differential-drive mobile robot with system and measurement noise in discrete time domain. This method is performed basing on dividing operating configuration of robot into two parts: glocal and local configuration then the control law is designed following Lyapunov stable theory for two configuration. The proposed stable control laws is able to reach asymptotically stably to target position and orientation from any initial conditions even existing noise in the system. Some simulation results have demonstrated the effect of proposed method.
Low-Resolution ADC Quantized Full-Duplex Massive MIMO-Enabled Wireless Backhaul in Heterogeneous Networks Over Rician Channels
Venue: arXiv cs.IT 2020
Year: 2020

This paper studies the spectral/energy efficiency (SE/EE) of a heterogeneous network with the backhaul enabled by low-resolution analog-to-digital converters (ADCs) quantized full-duplex massive multiple-input multiple-output (MIMO) over Rician channels. Backhaul communication is completed over two phases. During the first phase, the macro-cell (MC) base station (BS) deploys massive receive antennas and a few transmit antennas; the small-cell (SC) BSs employ large-scale receive antennas and a single transmit antenna. For the second phase, the roles of the transmit and receive antennas are switched. Due to the low-resolution ADCs, we account for quantization noise (QN). We characterize the joint impact of the number of antennas, self-interference, SC-to-SC interference, QN, and Rician K-factor. For the first phase, the SE is enhanced with the massive receive antennas and the loss due to QN is limited. For the second phase, the desired signal and QN have the same order. Therefore, the SE saturates with the massive transmit antennas. As the Rician K-factor increases, the SE converges. Power scaling laws are derived to demonstrate that the transmit power can be scaled down proportionally to the massive antennas. We investigate the EE/SE trade-offs. The envelope of the EE/SE region grows with increase in the Rician K-factor.
DREAM Architecture: a Developmental Approach to Open-Ended Learning in Robotics
Venue: arXiv cs.AI 2020
Year: 2020

Robots are still limited to controlled conditions, that the robot designer knows with enough details to endow the robot with the appropriate models or behaviors. Learning algorithms add some flexibility with the ability to discover the appropriate behavior given either some demonstrations or a reward to guide its exploration with a reinforcement learning algorithm. Reinforcement learning algorithms rely on the definition of state and action spaces that define reachable behaviors. Their adaptation capability critically depends on the representations of these spaces: small and discrete spaces result in fast learning while large and continuous spaces are challenging and either require a long training period or prevent the robot from converging to an appropriate behavior. Beside the operational cycle of policy execution and the learning cycle, which works at a slower time scale to acquire new policies, we introduce the redescription cycle, a third cycle working at an even slower time scale to generate or adapt the required representations to the robot, its environment and the task. We introduce the challenges raised by this cycle and we present DREAM (Deferred Restructuring of Experience in Autonomous Machines), a developmental cognitive architecture to bootstrap this redescription process stage by stage, build new state representations with appropriate motivations, and transfer the acquired knowledge across domains or tasks or even across robots. We describe results obtained so far with this approach and end up with a discussion of the questions it raises in Neuroscience.
R2RML and RML Comparison for RDF Generation, their Rules Validation and Inconsistency Resolution
Venue: arXiv cs.AI 2020
Year: 2020

In this paper, an overview of the state of the art on knowledge graph generation is provided, with focus on the two prevalent mapping languages: the W3C recommended R2RML and its generalisation RML. We look into details on their differences and explain how knowledge graphs, in the form of RDF graphs, can be generated with each one of the two mapping languages. Then we assess if the vocabulary terms were properly applied to the data and no violations occurred on their use, either using R2RML or RML to generate the desired knowledge graph.
Fully Online Matching II: Beating Ranking and Water-filling
Venue: arXiv cs.DS 2020
Year: 2020

Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance are the Ranking algorithm for integral matching and the Water-filling algorithm for fractional matching. Most algorithms in the literature can be viewed as adaptations of these two in the corresponding models. Recently, Huang et al.~(STOC 2018, SODA 2019) introduced a more general model called \emph{fully online matching}, which considers general graphs and allows all vertices to arrive online. They also generalized Ranking and Water-filling to fully online matching and gave some tight analysis: Ranking is $Ω\approx 0.567$-competitive on bipartite graphs where the $Ω$-constant satisfies $Ωe^Ω= 1$, and Water-filling is $2-\sqrt{2} \approx 0.585$-competitive on general graphs. We propose fully online matching algorithms strictly better than Ranking and Water-filling. For integral matching on bipartite graphs, we build on the online primal dual analysis of Ranking and Water-filling to design a $0.569$-competitive hybrid algorithm called Balanced Ranking. To our knowledge, it is the first integral algorithm in the online matching literature that successfully integrates ideas from Water-filling. For fractional matching on general graphs, we give a $0.592$-competitive algorithm called Eager Water-filling, which may match a vertex on its arrival. By contrast, the original Water-filling algorithm always matches vertices at their deadlines. Our result for fractional matching further shows a separation between fully online matching and the general vertex arrival model by Wang and Wong (ICALP 2015), due to an upper bound of $0.5914$ in the latter model by Buchbinder, Segev, and Tkach (ESA 2017).
A 28-nm Convolutional Neuromorphic Processor Enabling Online Learning with Spike-Based Retinas
Venue: arXiv cs.NE 2020
Year: 2020

In an attempt to follow biological information representation and organization principles, the field of neuromorphic engineering is usually approached bottom-up, from the biophysical models to large-scale integration in silico. While ideal as experimentation platforms for cognitive computing and neuroscience, bottom-up neuromorphic processors have yet to demonstrate an efficiency advantage compared to specialized neural network accelerators for real-world problems. Top-down approaches aim at answering this difficulty by (i) starting from the applicative problem and (ii) investigating how to make the associated algorithms hardware-efficient and biologically-plausible. In order to leverage the data sparsity of spike-based neuromorphic retinas for adaptive edge computing and vision applications, we follow a top-down approach and propose SPOON, a 28-nm event-driven CNN (eCNN). It embeds online learning with only 16.8-% power and 11.8-% area overheads with the biologically-plausible direct random target projection (DRTP) algorithm. With an energy per classification of 313nJ at 0.6V and a 0.32-mm$^2$ area for accuracies of 95.3% (on-chip training) and 97.5% (off-chip training) on MNIST, we demonstrate that SPOON reaches the efficiency of conventional machine learning accelerators while embedding on-chip learning and being compatible with event-based sensors, a point that we further emphasize with N-MNIST benchmarking.
Multi-modal Embedding Fusion-based Recommender
Venue: arXiv cs.IR 2020
Year: 2020

Recommendation systems have lately been popularized globally, with primary use cases in online interaction systems, with significant focus on e-commerce platforms. We have developed a machine learning-based recommendation platform, which can be easily applied to almost any items and/or actions domain. Contrary to existing recommendation systems, our platform supports multiple types of interaction data with multiple modalities of metadata natively. This is achieved through multi-modal fusion of various data representations. We deployed the platform into multiple e-commerce stores of different kinds, e.g. food and beverages, shoes, fashion items, telecom operators. Here, we present our system, its flexibility and performance. We also show benchmark results on open datasets, that significantly outperform state-of-the-art prior work.
Sanskrit Segmentation Revisited
Venue: arXiv cs.CL 2020
Year: 2020

Computationally analyzing Sanskrit texts requires proper segmentation in the initial stages. There have been various tools developed for Sanskrit text segmentation. Of these, Gérard Huet's Reader in the Sanskrit Heritage Engine analyzes the input text and segments it based on the word parameters - phases like iic, ifc, Pr, Subst, etc., and sandhi (or transition) that takes place at the end of a word with the initial part of the next word. And it enlists all the possible solutions differentiating them with the help of the phases. The phases and their analyses have their use in the domain of sentential parsers. In segmentation, though, they are not used beyond deciding whether the words formed with the phases are morphologically valid. This paper tries to modify the above segmenter by ignoring the phase details (except for a few cases), and also proposes a probability function to prioritize the list of solutions to bring up the most valid solutions at the top.
Robustly Learning any Clusterable Mixture of Gaussians
Venue: arXiv cs.DS 2020
Year: 2020

We study the efficient learnability of high-dimensional Gaussian mixtures in the outlier-robust setting, where a small constant fraction of the data is adversarially corrupted. We resolve the polynomial learnability of this problem when the components are pairwise separated in total variation distance. Specifically, we provide an algorithm that, for any constant number of components $k$, runs in polynomial time and learns the components of an $ε$-corrupted $k$-mixture within information theoretically near-optimal error of $\tilde{O}(ε)$, under the assumption that the overlap between any pair of components $P_i, P_j$ (i.e., the quantity $1-TV(P_i, P_j)$) is bounded by $\mathrm{poly}(ε)$. Our separation condition is the qualitatively weakest assumption under which accurate clustering of the samples is possible. In particular, it allows for components with arbitrary covariances and for components with identical means, as long as their covariances differ sufficiently. Ours is the first polynomial time algorithm for this problem, even for $k=2$. Our algorithm follows the Sum-of-Squares based proofs to algorithms approach. Our main technical contribution is a new robust identifiability proof of clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system. The key ingredients of this proof are a novel use of SoS-certifiable anti-concentration and a new characterization of pairs of Gaussians with small (dimension-independent) overlap in terms of their parameter distance.
Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Venue: arXiv cs.CC 2020
Year: 2020

A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses $O(g^{1/2}n^{1/2}\log n)$-space to find an $O(g^{1/2}n^{1/2})$-sized separator of a graph having $n$ vertices and embedded on a surface of genus $g$.
Finite-Blocklength and Error-Exponent Analyses for LDPC Codes in Point-to-Point and Multiple Access Communication
Venue: arXiv cs.IT 2020
Year: 2020

This paper applies error-exponent and dispersion-style analyses to derive finite-blocklength achievability bounds for low-density parity-check (LDPC) codes over the point-to-point channel (PPC) and multiple access channel (MAC). The error-exponent analysis applies Gallager's error exponent to bound achievable symmetrical and asymmetrical rates in the MAC. The dispersion-style analysis begins with a generalization of the random coding union (RCU) bound from random code ensembles with i.i.d. codewords to random code ensembles in which codewords may be statistically dependent; this generalization is useful since the codewords of random linear codes such as random LDPC codes are dependent. Application of the RCU bound yields improved finite-blocklength error bounds and asymptotic achievability results for i.i.d. random codes and new finite-blocklength error bounds and achievability results for LDPC codes. For discrete, memoryless channels, these results show that LDPC codes achieve first- and second-order performance that is optimal for the PPC and identical to the best-prior results for the MAC.