OpenRaiser/Intern-Atlas huggingface dataset:
Problem Solving at the Edge of Chaos: Entropy, Puzzles and the Sudoku Freezing Transition
Venue: arXiv cs.CC 2018
Year: 2018

Sudoku is a widely popular $\mathcal{NP}$-Complete combinatorial puzzle whose prospects for studying human computation have recently received attention, but the algorithmic hardness of Sudoku solving is yet largely unexplored. In this paper, we study the statistical mechanical properties of random Sudoku grids, showing that puzzles of varying sizes attain a hardness peak associated with a critical behavior in the constrainedness of random instances. In doing so, we provide the first description of a Sudoku \emph{freezing} transition, showing that the fraction of backbone variables undergoes a phase transition as the density of pre-filled cells is calibrated. We also uncover a variety of critical phenomena in the applicability of Sudoku elimination strategies, providing explanations as to why puzzles become boring outside the typical range of clue densities adopted by Sudoku publishers. We further show that the constrainedness of Sudoku puzzles can be understood in terms of the informational (Shannon) entropy of their solutions, which only increases up to the critical point where variables become frozen. Our findings shed light on the nature of the $k$-coloring transition when the graph topology is fixed, and are an invitation to the study of phase transition phenomena in problems defined over \emph{alldifferent} constraints. They also suggest advantages to studying the statistical mechanics of popular $\mathcal{NP}$-Hard puzzles, which can both aid the design of hard instances and help understand the difficulty of human problem solving.
Knowing Where to Look? Analysis on Attention of Visual Question Answering System
Venue: arXiv cs.CV 2018
Year: 2018

Attention mechanisms have been widely used in Visual Question Answering (VQA) solutions due to their capacity to model deep cross-domain interactions. Analyzing attention maps offers us a perspective to find out limitations of current VQA systems and an opportunity to further improve them. In this paper, we select two state-of-the-art VQA approaches with attention mechanisms to study their robustness and disadvantages by visualizing and analyzing their estimated attention maps. We find that both methods are sensitive to features, and simultaneously, they perform badly for counting and multi-object related questions. We believe that the findings and analytical method will help researchers identify crucial challenges on the way to improve their own VQA systems.
How FAIR can you get? Image Retrieval as a Use Case to calculate FAIR Metrics
Venue: arXiv cs.CY 2018
Year: 2018

A large number of services for research data management strive to adhere to the FAIR guiding principles for scientific data management and stewardship. To evaluate these services and to indicate possible improvements, use-case-centric metrics are needed as an addendum to existing metric frameworks. The retrieval of spatially and temporally annotated images can exemplify such a use case. The prototypical implementation indicates that currently no research data repository achieves the full score. Suggestions on how to increase the score include automatic annotation based on the metadata inside the image file and support for content negotiation to retrieve the images. These and other insights can lead to an improvement of data integration workflows, resulting in a better and more FAIR approach to manage research data.
A Novel Approach to Quality of Service Provisioning in Trusted Relay Quantum Key Distribution Networks
Venue: arXiv cs.NI 2018
Year: 2018

In recent years, noticeable progress has been made in the development of quantum equipment, reflected through the number of successful demonstrations of Quantum Key Distribution (QKD) technology. Although they showcase the great achievements of QKD, many practical difficulties still need to be resolved. Inspired by the significant similarity between mobile ad-hoc networks and QKD technology, we propose a novel quality of service (QoS) model including new metrics for determining the states of public and quantum channels as well as a comprehensive metric of the QKD link. We also propose a novel routing protocol to achieve high-level scalability and minimize consumption of cryptographic keys. Given the limited mobility of nodes in QKD networks, our routing protocol uses the geographical distance and calculated link states to determine the optimal route. It also benefits from a caching mechanism and detection of returning loops to provide effective forwarding while minimizing key consumption and achieving the desired utilization of network links. Simulation results are presented to demonstrate the validity and accuracy of the proposed solutions.
What does my knowing your plans tell me?
Venue: arXiv cs.RO 2018
Year: 2018

For robots acting in the presence of observers, we examine the information that is divulged if the observer is party to the robot's plan. Privacy constraints are specified as the stipulations on what can be inferred during plan execution. We imagine a case in which the robot's plan is divulged beforehand, so that the observer can use this {\em a priori} information along with the disclosed executions. The divulged plan, which can be represented by a procrustean graph, is shown to undermine privacy precisely to the extent that it can eliminate action-observation sequences that will never appear in the plan. Future work will consider how the divulged plan might be sought as the output of a planning procedure.
ns3-gym: Extending OpenAI Gym for Networking Research
Venue: arXiv cs.NI 2018
Year: 2018

OpenAI Gym is a toolkit for reinforcement learning (RL) research. It includes a large number of well-known problems that expose a common interface allowing to directly compare the performance results of different RL algorithms. Since many years, the ns-3 network simulation tool is the de-facto standard for academic and industry research into networking protocols and communications technology. Numerous scientific papers were written reporting results obtained using ns-3, and hundreds of models and modules were written and contributed to the ns-3 code base. Today as a major trend in network research we see the use of machine learning tools like RL. What is missing is the integration of a RL framework like OpenAI Gym into the network simulator ns-3. This paper presents the ns3-gym framework. First, we discuss design decisions that went into the software. Second, two illustrative examples implemented using ns3-gym are presented. Our software package is provided to the community as open source under a GPL license and hence can be easily extended.
A Generative Adversarial Model for Right Ventricle Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

The clinical management of several cardiovascular conditions, such as pulmonary hypertension, require the assessment of the right ventricular (RV) function. This work addresses the fully automatic and robust access to one of the key RV biomarkers, its ejection fraction, from the gold standard imaging modality, MRI. The problem becomes the accurate segmentation of the RV blood pool from cine MRI sequences. This work proposes a solution based on Fully Convolutional Neural Networks (FCNN), where our first contribution is the optimal combination of three concepts (the convolution Gated Recurrent Units (GRU), the Generative Adversarial Networks (GAN), and the L1 loss function) that achieves an improvement of 0.05 and 3.49 mm in Dice Index and Hausdorff Distance respectively with respect to the baseline FCNN. This improvement is then doubled by our second contribution, the ROI-GAN, that sets two GANs to cooperate working at two fields of view of the image, its full resolution and the region of interest (ROI). Our rationale here is to better guide the FCNN learning by combining global (full resolution) and local Region Of Interest (ROI) features. The study is conducted in a large in-house dataset of $\sim$ 23.000 segmented MRI slices, and its generality is verified in a publicly available dataset.
Collective evolution of weights in wide neural networks
Venue: arXiv cs.NE 2018
Year: 2018

We derive a nonlinear integro-differential transport equation describing collective evolution of weights under gradient descent in large-width neural-network-like models. We characterize stationary points of the evolution and analyze several scenarios where the transport equation can be solved approximately. We test our general method in the special case of linear free-knot splines, and find good agreement between theory and experiment in observations of global optima, stability of stationary points, and convergence rates.
Solving the clustered traveling salesman problem with d-relaxed priority rule
Venue: arXiv cs.AI 2018
Year: 2018

The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into clusters with different urgency levels and more urgent locations must be visited before less urgent ones. However, this could lead to an inefficient route in terms of traveling cost. This priority-oriented constraint can be relaxed by a rule called d-relaxed priority that provides a trade-off between transportation cost and emergency level. Our research proposes two approaches to solve the problem with d-relaxed priority rule. We improve the mathematical formulation proposed in the literature to construct an exact solution method. A meta-heuristic method based on the framework of Iterated Local Search with problem-tailored operators is also introduced to find approximate solutions. Experimental results show the effectiveness of our methods.
Glioma Segmentation with Cascaded Unet
Venue: arXiv cs.CV 2018
Year: 2018

MRI analysis takes central position in brain tumor diagnosis and treatment, thus it's precise evaluation is crucially important. However, it's 3D nature imposes several challenges, so the analysis is often performed on 2D projections that reduces the complexity, but increases bias. On the other hand, time consuming 3D evaluation, like, segmentation, is able to provide precise estimation of a number of valuable spatial characteristics, giving us understanding about the course of the disease.\newline Recent studies, focusing on the segmentation task, report superior performance of Deep Learning methods compared to classical computer vision algorithms. But still, it remains a challenging problem. In this paper we present deep cascaded approach for automatic brain tumor segmentation. Similar to recent methods for object detection, our implementation is based on neural networks; we propose modifications to the 3D UNet architecture and augmentation strategy to efficiently handle multimodal MRI input, besides this we introduce approach to enhance segmentation quality with context obtained from models of the same topology operating on downscaled data. We evaluate presented approach on BraTS 2018 dataset and discuss results.
Event Coreference Resolution Using Neural Network Classifiers
Venue: arXiv cs.CL 2018
Year: 2018

This paper presents a neural network classifier approach to detecting both within- and cross- document event coreference effectively using only event mention based features. Our approach does not (yet) rely on any event argument features such as semantic roles or spatiotemporal arguments. Experimental results on the ECB+ dataset show that our approach produces F1 scores that significantly outperform the state-of-the-art methods for both within-document and cross-document event coreference resolution when we use B3 and CEAFe evaluation measures, but gets worse F1 score with the MUC measure. However, when we use the CoNLL measure, which is the average of these three scores, our approach has slightly better F1 for within- document event coreference resolution but is significantly better for cross-document event coreference resolution.
Efficient Trajectory Optimization for Robot Motion Planning
Venue: arXiv cs.RO 2018
Year: 2018

Motion planning for multi-jointed robots is challenging. Due to the inherent complexity of the problem, most existing works decompose motion planning as easier subproblems. However, because of the inconsistent performance metrics, only sub-optimal solution can be found by decomposition based approaches. This paper presents an optimal control based approach to address the path planning and trajectory planning subproblems simultaneously. Unlike similar works which either ignore robot dynamics or require long computation time, an efficient numerical method for trajectory optimization is presented in this paper for motion planning involving complicated robot dynamics. The efficiency and effectiveness of the proposed approach is shown by numerical results. Experimental results are used to show the feasibility of the presented planning algorithm.
Current Trends and Future Research Directions for Interactive Music
Venue: arXiv cs.SD 2018
Year: 2018

In this review, it is explained and compared different software and formalisms used in music interaction: sequencers, computer-assisted improvisation, meta- instruments, score-following, asynchronous dataflow languages, synchronous dataflow languages, process calculi, temporal constraints and interactive scores. Formal approaches have the advantage of providing rigorous semantics of the behavior of the model and proving correctness during execution. The main disadvantage of formal approaches is lack of commercial tools.
Batch Active Preference-Based Learning of Reward Functions
Venue: arXiv cs.LG 2018
Year: 2018

Data generation and labeling are usually an expensive part of learning for robotics. While active learning methods are commonly used to tackle the former problem, preference-based learning is a concept that attempts to solve the latter by querying users with preference questions. In this paper, we will develop a new algorithm, batch active preference-based learning, that enables efficient learning of reward functions using as few data samples as possible while still having short query generation times. We introduce several approximations to the batch active learning problem, and provide theoretical guarantees for the convergence of our algorithms. Finally, we present our experimental results for a variety of robotics tasks in simulation. Our results suggest that our batch active learning algorithm requires only a few queries that are computed in a short amount of time. We then showcase our algorithm in a study to learn human users' preferences.
Real Vector Spaces and the Cauchy-Schwarz Inequality in ACL2(r)
Venue: arXiv cs.LO 2018
Year: 2018

We present a mechanical proof of the Cauchy-Schwarz inequality in ACL2(r) and a formalisation of the necessary mathematics to undertake such a proof. This includes the formalisation of $\mathbb{R}^n$ as an inner product space. We also provide an application of Cauchy-Schwarz by formalising $\mathbb R^n$ as a metric space and exhibiting continuity for some simple functions $\mathbb R^n\to\mathbb R$. The Cauchy-Schwarz inequality relates the magnitude of a vector to its projection (or inner product) with another: \[|\langle u,v\rangle| \leq \|u\| \|v\|\] with equality iff the vectors are linearly dependent. It finds frequent use in many branches of mathematics including linear algebra, real analysis, functional analysis, probability, etc. Indeed, the inequality is considered to be among "The Hundred Greatest Theorems" and is listed in the "Formalizing 100 Theorems" project. To the best of our knowledge, our formalisation is the first published proof using ACL2(r) or any other first-order theorem prover.
Smtlink 2.0
Venue: arXiv cs.LO 2018
Year: 2018

Smtlink is an extension of ACL2 with Satisfiability Modulo Theories (SMT) solvers. We presented an earlier version at ACL2'2015. Smtlink 2.0 makes major improvements over the initial version with respect to soundness, extensibility, ease-of-use, and the range of types and associated theory-solvers supported. Most theorems that one would want to prove using an SMT solver must first be translated to use only the primitive operations supported by the SMT solver -- this translation includes function expansion and type inference. Smtlink 2.0 performs this translation using a sequence of steps performed by verified clause processors and computed hints. These steps are ensured to be sound. The final transliteration from ACL2 to Z3's Python interface requires a trusted clause processor. This is a great improvement in soundness and extensibility over the original Smtlink which was implemented as a single, monolithic, trusted clause processor. Smtlink 2.0 provides support for FTY defprod, deflist, defalist, and defoption types by using Z3's arrays and user-defined data types. We have identified common usage patterns and simplified the configuration and hint information needed to use Smtlink.
Semi-supervised clustering for de-duplication
Venue: arXiv cs.LG 2018
Year: 2018

Data de-duplication is the task of detecting multiple records that correspond to the same real-world entity in a database. In this work, we view de-duplication as a clustering problem where the goal is to put records corresponding to the same physical entity in the same cluster and putting records corresponding to different physical entities into different clusters. We introduce a framework which we call promise correlation clustering. Given a complete graph $G$ with the edges labelled $0$ and $1$, the goal is to find a clustering that minimizes the number of $0$ edges within a cluster plus the number of $1$ edges across different clusters (or correlation loss). The optimal clustering can also be viewed as a complete graph $G^*$ with edges corresponding to points in the same cluster being labelled $0$ and other edges being labelled $1$. Under the promise that the edge difference between $G$ and $G^*$ is "small", we prove that finding the optimal clustering (or $G^*$) is still NP-Hard. [Ashtiani et. al, 2016] introduced the framework of semi-supervised clustering, where the learning algorithm has access to an oracle, which answers whether two points belong to the same or different clusters. We further prove that even with access to a same-cluster oracle, the promise version is NP-Hard as long as the number queries to the oracle is not too large ($o(n)$ where $n$ is the number of vertices). Given these negative results, we consider a restricted version of correlation clustering. As before, the goal is to find a clustering that minimizes the correlation loss. However, we restrict ourselves to a given class $\mathcal F$ of clusterings. We offer a semi-supervised algorithmic approach to solve the restricted variant with success guarantees.
Receding horizon estimation and control with structured noise blocking for mobile robot slip compensation
Venue: arXiv cs.RO 2018
Year: 2018

The control of field robots in varying and uncertain terrain conditions presents a challenge for autonomous navigation. Online estimation of the wheel-terrain slip characteristics is essential for generating the accurate control predictions necessary for tracking trajectories in off-road environments. Receding horizon estimation (RHE) provides a powerful framework for constrained estimation, and when combined with receding horizon control (RHC), yields an adaptive optimisation-based control method. Presently, such methods assume slip to be constant over the estimation horizon, while our proposed structured blocking approach relaxes this assumption, resulting in improved state and parameter estimation. We demonstrate and compare the performance of this method in simulation, and propose an overlapping-block strategy to ameliorate some of the limitations encountered in applying noise-blocking in a receding horizon estimation and control (RHEC) context.
Improving Neural Text Simplification Model with Simplified Corpora
Venue: arXiv cs.CL 2018
Year: 2018

Text simplification (TS) can be viewed as monolingual translation task, translating between text variations within a single language. Recent neural TS models draw on insights from neural machine translation to learn lexical simplification and content reduction using encoder-decoder model. But different from neural machine translation, we cannot obtain enough ordinary and simplified sentence pairs for TS, which are expensive and time-consuming to build. Target-side simplified sentences plays an important role in boosting fluency for statistical TS, and we investigate the use of simplified sentences to train, with no changes to the network architecture. We propose to pair simple training sentence with a synthetic ordinary sentence via back-translation, and treating this synthetic data as additional training data. We train encoder-decoder model using synthetic sentence pairs and original sentence pairs, which can obtain substantial improvements on the available WikiLarge data and WikiSmall data compared with the state-of-the-art methods.
New Vistas to study Bhartrhari: Cognitive NLP
Venue: arXiv cs.CL 2018
Year: 2018

The Sanskrit grammatical tradition which has commenced with Panini's Astadhyayi mostly as a Padasastra has culminated as a Vakyasastra, at the hands of Bhartrhari. The grammarian-philosopher Bhartrhari and his authoritative work 'Vakyapadiya' have been a matter of study for modern scholars, at least for more than 50 years, since Ashok Aklujkar submitted his Ph.D. dissertation at Harvard University. The notions of a sentence and a word as a meaningful linguistic unit in the language have been a subject matter for the discussion in many works that followed later on. While some scholars have applied philological techniques to critically establish the text of the works of Bhartrhari, some others have devoted themselves to exploring philosophical insights from them. Some others have studied his works from the point of view of modern linguistics, and psychology. Few others have tried to justify the views by logical discussions. In this paper, we present a fresh view to study Bhartrhari, and his works, especially the 'Vakyapadiya'. This view is from the field of Natural Language Processing (NLP), more specifically, what is called as Cognitive NLP. We have studied the definitions of a sentence given by Bhartrhari at the beginning of the second chapter of 'Vakyapadiya'. We have researched one of these definitions by conducting an experiment and following the methodology of silent-reading of Sanskrit paragraphs. We collect the Gaze-behavior data of participants and analyze it to understand the underlying comprehension procedure in the human mind and present our results. We evaluate the statistical significance of our results using T-test, and discuss the caveats of our work. We also present some general remarks on this experiment and usefulness of this method for gaining more insights in the work of Bhartrhari.
Is your Statement Purposeless? Predicting Computer Science Graduation Admission Acceptance based on Statement Of Purpose
Venue: arXiv cs.IR 2018
Year: 2018

We present a quantitative, data-driven machine learning approach to mitigate the problem of unpredictability of Computer Science Graduate School Admissions. In this paper, we discuss the possibility of a system which may help prospective applicants evaluate their Statement of Purpose (SOP) based on our system output. We, then, identify feature sets which can be used to train a predictive model. We train a model over fifty manually verified SOPs for which it uses an SVM classifier and achieves the highest accuracy of 92% with 10-fold cross-validation. We also perform experiments to establish that Word Embedding based features and Document Similarity-based features outperform other identified feature combinations. We plan to deploy our application as a web service and release it as a FOSS service.