OpenRaiser/Intern-Atlas huggingface dataset:
On the Complexity of Opinions and Online Discussions
Venue: arXiv cs.SI 2018
Year: 2018

In an increasingly polarized world, demagogues who reduce complexity down to simple arguments based on emotion are gaining in popularity. Are opinions and online discussions falling into demagoguery? In this work, we aim to provide computational tools to investigate this question and, by doing so, explore the nature and complexity of online discussions and their space of opinions, uncovering where each participant lies. More specifically, we present a modeling framework to construct latent representations of opinions in online discussions which are consistent with human judgements, as measured by online voting. If two opinions are close in the resulting latent space of opinions, it is because humans think they are similar. Our modeling framework is theoretically grounded and establishes a surprising connection between opinions and voting models and the sign-rank of a matrix. Moreover, it also provides a set of practical algorithms to both estimate the dimension of the latent space of opinions and infer where opinions expressed by the participants of an online discussion lie in this space. Experiments on a large dataset from Yahoo! News, Yahoo! Finance, Yahoo! Sports, and the Newsroom app suggest that unidimensional opinion models may often be unable to accurately represent online discussions, provide insights into human judgements and opinions, and show that our framework is able to circumvent language nuances such as sarcasm or humor by relying on human judgements instead of textual analysis.
Comments on: "Lyapunov matrices for a class of time delay systems" by V. L. Kharitonov
Venue: arXiv cs.SY 2018
Year: 2018

We prove that an auxiliary two-point boundary value problem presented in V. L. Kharitonov, Lyapunov matrices for a class of time delay systems, Systems & Control Letters 55 (2006) 610-617 has linearly dependent boundary conditions, and consequently a unique solution does not exist. Therefore, the two-point boundary value problem presented therein fails to be a basis for constructing Lyapunov matrices for the class of time delay systems investigated.
Predicting Metamorphic Relation for Matrix Calculation Programs
Venue: arXiv cs.SE 2018
Year: 2018

Matrices often represent important information in scientific applications and are involved in performing complex calculations. But systematically testing these applications is hard due to the oracle problem. Metamorphic testing is an effective approach to test such applications because it uses metamorphic relations to determine whether test cases have passed or failed. Metamorphic relations are typically identified with the help of a domain expert and is a labor intensive task. In this work we use a graph kernel based machine learning approach to predict metamorphic relations for matrix calculation programs. Previously, this graph kernel based machine learning approach was used to successfully predict metamorphic relations for programs that perform numerical calculations. Results of this study show that this approach can be used to predict metamorphic relations for matrix calculation programs as well.
Automated soft tissue lesion detection and segmentation in digital mammography using a u-net deep learning network
Venue: arXiv cs.CV 2018
Year: 2018

Computer-aided detection or decision support systems aim to improve breast cancer screening programs by helping radiologists to evaluate digital mammography (DM) exams. Commonly such methods proceed in two steps: selection of candidate regions for malignancy, and later classification as either malignant or not. In this study, we present a candidate detection method based on deep learning to automatically detect and additionally segment soft tissue lesions in DM. A database of DM exams (mostly bilateral and two views) was collected from our institutional archive. In total, 7196 DM exams (28294 DM images) acquired with systems from three different vendors (General Electric, Siemens, Hologic) were collected, of which 2883 contained malignant lesions verified with histopathology. Data was randomly split on an exam level into training (50\%), validation (10\%) and testing (40\%) of deep neural network with u-net architecture. The u-net classifies the image but also provides lesion segmentation. Free receiver operating characteristic (FROC) analysis was used to evaluate the model, on an image and on an exam level. On an image level, a maximum sensitivity of 0.94 at 7.93 false positives (FP) per image was achieved. Similarly, per exam a maximum sensitivity of 0.98 at 7.81 FP per image was achieved. In conclusion, the method could be used as a candidate selection model with high accuracy and with the additional information of lesion segmentation.
Superrational types
Venue: arXiv cs.AI 2018
Year: 2018

We present a formal analysis of Douglas Hofstadter's concept of \emph{superrationality}. We start by defining superrationally justifiable actions, and study them in symmetric games. We then model the beliefs of the players, in a way that leads them to different choices than the usual assumption of rationality by restricting the range of conceivable choices. These beliefs are captured in the formal notion of \emph{type} drawn from epistemic game theory. The theory of coalgebras is used to frame type spaces and to account for the existence of some of them. We find conditions that guarantee superrational outcomes.
Real World Evaluation of Approaches to Research Paper Recommendation
Venue: arXiv cs.IR 2018
Year: 2018

In this work, we have identified the need for choosing baseline approaches for research-paper recommendation systems. Following a literature survey of all research paper recommendation approaches described over the last four years, we framed criteria that makes for a well-rounded set of baselines. These are implemented on Mr. DLib a literature recommendation platform. User click data was collected as part of an ongoing experiment in collaboration with our partner Gesis. We reported the results from our evaluation for the experiments. We will be able to draw clearer conclusions as time passes. We find that a term based similarity search performs better than keyword based approaches. These results are a good starting point in finding performance improvements for related document searches.
Communication-Optimal Convolutional Neural Nets
Venue: arXiv cs.DS 2018
Year: 2018

Efficiently executing convolutional neural nets (CNNs) is important in many machine-learning tasks. Since the cost of moving a word of data, either between levels of a memory hierarchy or between processors over a network, is much higher than the cost of an arithmetic operation, minimizing data movement is critical to performance optimization. In this paper, we present both new lower bounds on data movement needed for CNNs, and optimal sequential algorithms that attain these lower bounds. In most common cases, our optimal algorithms can attain significantly more data reuse than matrix multiplication.
Efficient Embedding of MPI Collectives in MXNET DAGs for scaling Deep Learning
Venue: arXiv cs.DC 2018
Year: 2018

Availability of high performance computing infrastructures such as clusters of GPUs and CPUs have fueled the growth of distributed learning systems. Deep Learning frameworks express neural nets as DAGs and execute these DAGs on computation resources such as GPUs. In this paper, we propose efficient designs of embedding MPI collective operations into data parallel DAGs. Incorrect designs can easily lead to deadlocks or program crashes. In particular, we demonstrate three designs: Funneled, Concurrent communication and Dependency chaining of using MPI collectives with DAGs. These designs automatically enable overlap of computation with communication by allowing for concurrent execution with the other tasks. We directly implement these designs into the KVStore API of the MXNET. This allows us to directly leverage the rest of the infrastructure. Using ImageNet and CIFAR data sets, we show the potential of our designs. In particular, our designs scale to 256 GPUs with as low as 50 seconds of epoch times for ImageNet 1K datasets.
TAP-DLND 1.0 : A Corpus for Document Level Novelty Detection
Venue: arXiv cs.CL 2018
Year: 2018

Detecting novelty of an entire document is an Artificial Intelligence (AI) frontier problem that has widespread NLP applications, such as extractive document summarization, tracking development of news events, predicting impact of scholarly articles, etc. Important though the problem is, we are unaware of any benchmark document level data that correctly addresses the evaluation of automatic novelty detection techniques in a classification framework. To bridge this gap, we present here a resource for benchmarking the techniques for document level novelty detection. We create the resource via event-specific crawling of news documents across several domains in a periodic manner. We release the annotated corpus with necessary statistics and show its use with a developed system for the problem in concern.
Recurrent Residual Convolutional Neural Network based on U-Net (R2U-Net) for Medical Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning (DL) based semantic segmentation methods have been providing state-of-the-art performance in the last few years. More specifically, these techniques have been successfully applied to medical image classification, segmentation, and detection tasks. One deep learning technique, U-Net, has become one of the most popular for these applications. In this paper, we propose a Recurrent Convolutional Neural Network (RCNN) based on U-Net as well as a Recurrent Residual Convolutional Neural Network (RRCNN) based on U-Net models, which are named RU-Net and R2U-Net respectively. The proposed models utilize the power of U-Net, Residual Network, as well as RCNN. There are several advantages of these proposed architectures for segmentation tasks. First, a residual unit helps when training deep architecture. Second, feature accumulation with recurrent residual convolutional layers ensures better feature representation for segmentation tasks. Third, it allows us to design better U-Net architecture with same number of network parameters with better performance for medical image segmentation. The proposed models are tested on three benchmark datasets such as blood vessel segmentation in retina images, skin cancer segmentation, and lung lesion segmentation. The experimental results show superior performance on segmentation tasks compared to equivalent models including U-Net and residual U-Net (ResU-Net).
Reachable Set Estimation and Safety Verification for Piecewise Linear Systems with Neural Network Controllers
Venue: arXiv cs.SY 2018
Year: 2018

In this work, the reachable set estimation and safety verification problems for a class of piecewise linear systems equipped with neural network controllers are addressed. The neural network is considered to consist of Rectified Linear Unit (ReLU) activation functions. A layer-by-layer approach is developed for the output reachable set computation of ReLU neural networks. The computation is formulated in the form of a set of manipulations for a union of polytopes. Based on the output reachable set for neural network controllers, the output reachable set for a piecewise linear feedback control system can be estimated iteratively for a given finite-time interval. With the estimated output reachable set, the safety verification for piecewise linear systems with neural network controllers can be performed by checking the existence of intersections of unsafe regions and output reach set. A numerical example is presented to illustrate the effectiveness of our approach.
Categorizing the Content of GitHub README Files
Venue: arXiv cs.SE 2018
Year: 2018

README files play an essential role in shaping a developer's first impression of a software repository and in documenting the software project that the repository hosts. Yet, we lack a systematic understanding of the content of a typical README file as well as tools that can process these files automatically. To close this gap, we conduct a qualitative study involving the manual annotation of 4,226 README file sections from 393 randomly sampled GitHub repositories and we design and evaluate a classifier and a set of features that can categorize these sections automatically. We find that information discussing the `What' and `How' of a repository is very common, while many README files lack information regarding the purpose and status of a repository. Our multi-label classifier which can predict eight different categories achieves an F1 score of 0.746. To evaluate the usefulness of the classification, we used the automatically determined classes to label sections in GitHub README files using badges and showed files with and without these badges to twenty software professionals. The majority of participants perceived the automated labeling of sections based on our classifier to ease information discovery. This work enables the owners of software repositories to improve the quality of their documentation and it has the potential to make it easier for the software development community to discover relevant information in GitHub README files.
Fusing Video and Inertial Sensor Data for Walking Person Identification
Venue: arXiv cs.CV 2018
Year: 2018

An autonomous computer system (such as a robot) typically needs to identify, locate, and track persons appearing in its sight. However, most solutions have their limitations regarding efficiency, practicability, or environmental constraints. In this paper, we propose an effective and practical system which combines video and inertial sensors for person identification (PID). Persons who do different activities are easy to identify. To show the robustness and potential of our system, we propose a walking person identification (WPID) method to identify persons walking at the same time. By comparing features derived from both video and inertial sensor data, we can associate sensors in smartphones with human objects in videos. Results show that the correctly identified rate of our WPID method can up to 76% in 2 seconds.
Memetic Graph Clustering
Venue: arXiv cs.NE 2018
Year: 2018

It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation~challenge under consideration using a small amount of time.
Latent RANSAC
Venue: arXiv cs.CV 2018
Year: 2018

We present a method that can evaluate a RANSAC hypothesis in constant time, i.e. independent of the size of the data. A key observation here is that correct hypotheses are tightly clustered together in the latent parameter domain. In a manner similar to the generalized Hough transform we seek to find this cluster, only that we need as few as two votes for a successful detection. Rapidly locating such pairs of similar hypotheses is made possible by adapting the recent "Random Grids" range-search technique. We only perform the usual (costly) hypothesis verification stage upon the discovery of a close pair of hypotheses. We show that this event rarely happens for incorrect hypotheses, enabling a significant speedup of the RANSAC pipeline. The suggested approach is applied and tested on three robust estimation problems: camera localization, 3D rigid alignment and 2D-homography estimation. We perform rigorous testing on both synthetic and real datasets, demonstrating an improvement in efficiency without a compromise in accuracy. Furthermore, we achieve state-of-the-art 3D alignment results on the challenging "Redwood" loop-closure challenge.
Relative Worst-Order Analysis: A Survey
Venue: arXiv cs.DS 2018
Year: 2018

Relative worst-order analysis is a technique for assessing the relative quality of online algorithms. We survey the most important results obtained with this technique and compare it with other quality measures.
The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments
Venue: arXiv cs.DS 2018
Year: 2018

Given a directed graph $D$ on $n$ vertices and a positive integer $k$, the Arc-Disjoint Cycle Packing problem is to determine whether $D$ has $k$ arc-disjoint cycles. This problem is known to be W[1]-hard in general directed graphs. In this paper, we initiate a systematic study on the parameterized complexity of the problem restricted to tournaments. We show that the problem is fixed-parameter tractable and admits a polynomial kernel when parameterized by the solution size $k$. In particular, we show that it can be solved in $2^{\mathcal{O}(k \log k)} n^{\mathcal{O}(1)}$ time and has a kernel with $\mathcal{O}(k)$ vertices. The primary ingredient in both these results is a min-max theorem that states that every tournament either contains $k$ arc-disjoint triangles or has a feedback arc set of size at most $6k$. Our belief is that this combinatorial result is of independent interest and could be useful in other problems related to cycles in tournaments.
Learning of Optimal Forecast Aggregation in Partial Evidence Environments
Venue: arXiv cs.LG 2018
Year: 2018

We consider the forecast aggregation problem in repeated settings, where the forecasts are done on a binary event. At each period multiple experts provide forecasts about an event. The goal of the aggregator is to aggregate those forecasts into a subjective accurate forecast. We assume that experts are Bayesian; namely they share a common prior, each expert is exposed to some evidence, and each expert applies Bayes rule to deduce his forecast. The aggregator is ignorant with respect to the information structure (i.e., distribution over evidence) according to which experts make their prediction. The aggregator observes the experts' forecasts only. At the end of each period the actual state is realized. We focus on the question whether the aggregator can learn to aggregate optimally the forecasts of the experts, where the optimal aggregation is the Bayesian aggregation that takes into account all the information (evidence) in the system. We consider the class of partial evidence information structures, where each expert is exposed to a different subset of conditionally independent signals. Our main results are positive; We show that optimal aggregation can be learned in polynomial time in a quite wide range of instances of the partial evidence environments. We provide a tight characterization of the instances where learning is possible and impossible.
A Social Network Analysis Framework for Modeling Health Insurance Claims Data
Venue: arXiv cs.SI 2018
Year: 2018

Health insurance companies in Brazil have their data about claims organized having the view only for providers. In this way, they loose the physician view and how they share patients. Partnership between physicians can view as a fruitful work in most of the cases but sometimes this could be a problem for health insurance companies and patients, for example a recommendation to visit another physician only because they work in same clinic. The focus of the work is to better understand physicians activities and how these activities are represented in the data. Our approach considers three aspects: the relationships among physicians, the relationships between physicians and patients, and the relationships between physicians and health providers. We present the results of an analysis of a claims database (detailing 18 months of activity) from a large health insurance company in Brazil. The main contribution presented in this paper is a set of models to represent: mutual referral between physicians, patient retention, and physician centrality in the health insurance network. Our results show the proposed models based on social network frameworks, extracted surprising insights about physicians from real health insurance claims data.
Breaking the Loop: Recursive Proofs for Coinductive Predicates in Fibrations
Venue: arXiv cs.LO 2018
Year: 2018

The purpose of this paper is to develop and study recursive proofs of coinductive predicates. Such recursive proofs allow one to discover proof goals in the construction of a proof of a coinductive predicate, while still allowing the use of up-to techniques. This approach lifts the burden to guess invariants, like bisimulation relations, beforehand. Rather, they allow one to start with the sought-after proof goal and develop the proof from there until a point is reached, at which the proof can be closed through a recursion step. Proofs given in this way are both easier to construct and to understand, similarly to proofs given in cyclic proof systems or by appealing parameterised coinduction. In this paper, we develop a framework for recursive proofs of coinductive predicates that are given through fibrational predicate liftings. This framework is built on the so-called later modality, which has made its appearance in type theoretic settings before. In particular, we show the soundness and completeness of recursive proofs, we prove that compatible up-to techniques can be used as inference rules in recursive proofs, and provide some illustrating examples.
Real-Time Dense Stereo Matching With ELAS on FPGA Accelerated Embedded Devices
Venue: arXiv cs.CV 2018
Year: 2018

For many applications in low-power real-time robotics, stereo cameras are the sensors of choice for depth perception as they are typically cheaper and more versatile than their active counterparts. Their biggest drawback, however, is that they do not directly sense depth maps; instead, these must be estimated through data-intensive processes. Therefore, appropriate algorithm selection plays an important role in achieving the desired performance characteristics. Motivated by applications in space and mobile robotics, we implement and evaluate a FPGA-accelerated adaptation of the ELAS algorithm. Despite offering one of the best trade-offs between efficiency and accuracy, ELAS has only been shown to run at 1.5-3 fps on a high-end CPU. Our system preserves all intriguing properties of the original algorithm, such as the slanted plane priors, but can achieve a frame rate of 47fps whilst consuming under 4W of power. Unlike previous FPGA based designs, we take advantage of both components on the CPU/FPGA System-on-Chip to showcase the strategy necessary to accelerate more complex and computationally diverse algorithms for such low power, real-time systems.
Frictionless Authentication System: Security & Privacy Analysis and Potential Solutions
Venue: arXiv cs.CR 2018
Year: 2018

This paper proposes a frictionless authentication system, provides a comprehensive security analysis of and proposes potential solutions for this system. It first presents a system that allows users to authenticate to services in a frictionless manner, i.e., without the need to perform any particular authentication-related actions. Based on this system model, the paper analyses security problems and potential privacy threats imposed on users, leading to the specification of a set of security and privacy requirements. These requirements can be used as a guidance on designing secure and privacy-friendly frictionless authentication systems. The paper also sketches three potential solutions for such systems and highlights their advantages and disadvantages.