OpenRaiser/Intern-Atlas huggingface dataset:
Reasoning by Cases in Structured Argumentation
Venue: arXiv cs.AI 2017
Year: 2017

We extend the $ASPIC^+$ framework for structured argumentation so as to allow applications of the reasoning by cases inference scheme for defeasible arguments. Given an argument with conclusion `$A$ or $B$', an argument based on $A$ with conclusion $C$, and an argument based on $B$ with conclusion $C$, we allow the construction of an argument with conclusion $C$. We show how our framework leads to different results than other approaches in non-monotonic logic for dealing with disjunctive information, such as disjunctive default theory or approaches based on the OR-rule (which allows to derive a defeasible rule `If ($A$ or $B$) then $C$', given two defeasible rules `If $A$ then $C$' and `If $B$ then $C$'). We raise new questions regarding the subtleties of reasoning defeasibly with disjunctive information, and show that its formalization is more intricate than one would presume.
LASeR: Lightweight Authentication and Secured Routing for NDN IoT in Smart Cities
Venue: arXiv cs.NI 2017
Year: 2017

Recent literature suggests that the Internet of Things (IoT) scales much better in an Information-Centric Networking (ICN) model instead of the current host-centric Internet Protocol (IP) model. In particular, the Named Data Networking (NDN) project (one of the ICN architecture flavors) offers features exploitable by IoT applications, such as stateful forwarding, in- network caching, and built-in assurance of data provenance. Though NDN-based IoT frameworks have been proposed, none have adequately and holistically addressed concerns related to secure onboarding and routing. Additionally, emerging IoT applications such as smart cities require high scalability and thus pose new challenges to NDN routing. Therefore, in this work, we propose and evaluate a novel, scalable framework for lightweight authentication and hierarchical routing in the NDN IoT (ND- NoT). Our ns-3 based simulation analyses demonstrate that our framework is scalable and efficient. It supports deployment densities as high as 40,000 nodes/km2 with an average onboarding convergence time of around 250 seconds and overhead of less than 20 KiB per node. This demonstrates its efficacy for emerging large-scale IoT applications such as smart cities.
Extracting Build Changes with BUILDDIFF
Venue: arXiv cs.SE 2017
Year: 2017

Build systems are an essential part of modern software engineering projects. As software projects change continuously, it is crucial to understand how the build system changes because neglecting its maintenance can lead to expensive build breakage. Recent studies have investigated the (co-)evolution of build configurations and reasons for build breakage, but they did this only on a coarse grained level. In this paper, we present BUILDDIFF, an approach to extract detailed build changes from MAVEN build files and classify them into 95 change types. In a manual evaluation of 400 build changing commits, we show that BUILDDIFF can extract and classify build changes with an average precision and recall of 0.96 and 0.98, respectively. We then present two studies using the build changes extracted from 30 open source Java projects to study the frequency and time of build changes. The results show that the top 10 most frequent change types account for 73% of the build changes. Among them, changes to version numbers and changes to dependencies of the projects occur most frequently. Furthermore, our results show that build changes occur frequently around releases. With these results, we provide the basis for further research, such as for analyzing the (co-)evolution of build files with other artifacts or improving effort estimation approaches. Furthermore, our detailed change information enables improvements of refactoring approaches for build configurations and improvements of models to identify error-prone build files.
Gaussian Processes with Context-Supported Priors for Active Object Localization
Venue: arXiv cs.CV 2017
Year: 2017

We devise an algorithm using a Bayesian optimization framework in conjunction with contextual visual data for the efficient localization of objects in still images. Recent research has demonstrated substantial progress in object localization and related tasks for computer vision. However, many current state-of-the-art object localization procedures still suffer from inaccuracy and inefficiency, in addition to failing to provide a principled and interpretable system amenable to high-level vision tasks. We address these issues with the current research. Our method encompasses an active search procedure that uses contextual data to generate initial bounding-box proposals for a target object. We train a convolutional neural network to approximate an offset distance from the target object. Next, we use a Gaussian Process to model this offset response signal over the search space of the target. We then employ a Bayesian active search for accurate localization of the target. In experiments, we compare our approach to a state-of-theart bounding-box regression method for a challenging pedestrian localization task. Our method exhibits a substantial improvement over this baseline regression method.
Randomized Load Balancing on Networks with Stochastic Inputs
Venue: arXiv cs.DC 2017
Year: 2017

Iterative load balancing algorithms for indivisible tokens have been studied intensively in the past. Complementing previous worst-case analyses, we study an average-case scenario where the load inputs are drawn from a fixed probability distribution. For cycles, tori, hypercubes and expanders, we obtain almost matching upper and lower bounds on the discrepancy, the difference between the maximum and the minimum load. Our bounds hold for a variety of probability distributions including the uniform and binomial distribution but also distributions with unbounded range such as the Poisson and geometric distribution. For graphs with slow convergence like cycles and tori, our results demonstrate a substantial difference between the convergence in the worst- and average-case. An important ingredient in our analysis is new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process.
Count-ception: Counting by Fully Convolutional Redundant Counting
Venue: arXiv cs.CV 2017
Year: 2017

Counting objects in digital images is a process that should be replaced by machines. This tedious task is time consuming and prone to errors due to fatigue of human annotators. The goal is to have a system that takes as input an image and returns a count of the objects inside and justification for the prediction in the form of object localization. We repose a problem, originally posed by Lempitsky and Zisserman, to instead predict a count map which contains redundant counts based on the receptive field of a smaller regression network. The regression network predicts a count of the objects that exist inside this frame. By processing the image in a fully convolutional way each pixel is going to be accounted for some number of times, the number of windows which include it, which is the size of each window, (i.e., 32x32 = 1024). To recover the true count we take the average over the redundant predictions. Our contribution is redundant counting instead of predicting a density map in order to average over errors. We also propose a novel deep neural network architecture adapted from the Inception family of networks called the Count-ception network. Together our approach results in a 20% relative improvement (2.9 to 2.3 MAE) over the state of the art method by Xie, Noble, and Zisserman in 2016.
Denoising-based Turbo Compressed Sensing
Venue: arXiv cs.IT 2017
Year: 2017

Turbo compressed sensing (Turbo-CS) is an efficient iterative algorithm for sparse signal recovery with partial orthogonal sensing matrices. In this paper, we extend the Turbo-CS algorithm to solve compressed sensing problems involving more general signal structure, including compressive image recovery and low-rank matrix recovery. A main difficulty for such an extension is that the original Turbo-CS algorithm requires prior knowledge of the signal distribution that is usually unavailable in practice. To overcome this difficulty, we propose to redesign the Turbo-CS algorithm by employing a generic denoiser that does not depend on the prior distribution and hence the name denoising-based Turbo-CS (D-Turbo-CS). We then derive the extrinsic information for a generic denoiser by following the Turbo-CS principle. Based on that, we optimize the parametric extrinsic denoisers to minimize the output mean-square error (MSE). Explicit expressions are derived for the extrinsic SURE-LET denoiser used in compressive image denoising and also for the singular value thresholding (SVT) denoiser used in low-rank matrix denoising. We find that the dynamics of D-Turbo-CS can be well described by a scaler recursion called MSE evolution, similar to the case for Turbo-CS. Numerical results demonstrate that D-Turbo-CS considerably outperforms the counterpart algorithms in both reconstruction quality and running time.
SCAN: Structure Correcting Adversarial Network for Organ Segmentation in Chest X-rays
Venue: arXiv cs.CV 2017
Year: 2017

Chest X-ray (CXR) is one of the most commonly prescribed medical imaging procedures, often with over 2-10x more scans than other imaging modalities such as MRI, CT scan, and PET scans. These voluminous CXR scans place significant workloads on radiologists and medical practitioners. Organ segmentation is a crucial step to obtain effective computer-aided detection on CXR. In this work, we propose Structure Correcting Adversarial Network (SCAN) to segment lung fields and the heart in CXR images. SCAN incorporates a critic network to impose on the convolutional segmentation network the structural regularities emerging from human physiology. During training, the critic network learns to discriminate between the ground truth organ annotations from the masks synthesized by the segmentation network. Through this adversarial process the critic network learns the higher order structures and guides the segmentation model to achieve realistic segmentation outcomes. Extensive experiments show that our method produces highly accurate and natural segmentation. Using only very limited training data available, our model reaches human-level performance without relying on any existing trained model or dataset. Our method also generalizes well to CXR images from a different patient population and disease profiles, surpassing the current state-of-the-art.
Automatic Detection of GUI Design Smells: The Case of Blob Listener
Venue: arXiv cs.SE 2017
Year: 2017

Graphical User Interfaces (GUIs) intensively rely on event-driven programming: widgets send GUI events, which capture users' interactions, to dedicated objects called controllers. Controllers implement several GUI listeners that handle these events to produce GUI commands. In this work, we conducted an empirical study on 13 large Java Swing open-source software systems. We study to what extent the number of GUI commands that a GUI listener can produce has an impact on the change-and fault-proneness of the GUI listener code. We identify a new type of design smell, called Blob listener that characterizes GUI listeners that can produce more than two GUI commands. We show that 21 % of the analyzed GUI controllers are Blob listeners. We propose a systematic static code analysis procedure that searches for Blob listener that we implement in InspectorGuidget. We conducted experiments on six software systems for which we manually identified 37 instances of Blob listener. InspectorGuidget successfully detected 36 Blob listeners out of 37. The results exhibit a precision of 97.37 % and a recall of 97.59 %. Finally, we propose coding practices to avoid the use of Blob listeners.
Transductive Zero-Shot Learning with a Self-training dictionary approach
Venue: arXiv cs.CV 2017
Year: 2017

As an important and challenging problem in computer vision, zero-shot learning (ZSL) aims at automatically recognizing the instances from unseen object classes without training data. To address this problem, ZSL is usually carried out in the following two aspects: 1) capturing the domain distribution connections between seen classes data and unseen classes data; and 2) modeling the semantic interactions between the image feature space and the label embedding space. Motivated by these observations, we propose a bidirectional mapping based semantic relationship modeling scheme that seeks for crossmodal knowledge transfer by simultaneously projecting the image features and label embeddings into a common latent space. Namely, we have a bidirectional connection relationship that takes place from the image feature space to the latent space as well as from the label embedding space to the latent space. To deal with the domain shift problem, we further present a transductive learning approach that formulates the class prediction problem in an iterative refining process, where the object classification capacity is progressively reinforced through bootstrapping-based model updating over highly reliable instances. Experimental results on three benchmark datasets (AwA, CUB and SUN) demonstrate the effectiveness of the proposed approach against the state-of-the-art approaches.
A Visual Measure of Changes to Weighted Self-Organizing Map Patterns
Venue: arXiv cs.CV 2017
Year: 2017

Estimating output changes by input changes is the main task in causal analysis. In previous work, input and output Self-Organizing Maps (SOMs) were associated for causal analysis of multivariate and nonlinear data. Based on the association, a weight distribution of the output conditional on a given input was obtained over the output map space. Such a weighted SOM pattern of the output changes when the input changes. In order to analyze the change, it is important to measure the difference of the patterns. Many methods have been proposed for the dissimilarity measure of patterns. However, it remains a major challenge when attempting to measure how the patterns change. In this paper, we propose a visualization approach that simplifies the comparison of the difference in terms of the pattern property. Using this approach, the change can be analyzed by integrating colors and star glyph shapes representing the property dissimilarity. Ecological data is used to demonstrate the usefulness of our approach and the experimental results show that our approach provides the change information effectively.
Resource-monotonicity and Population-monotonicity in Connected Cake-cutting
Venue: arXiv cs.GT 2017
Year: 2017

In the classic cake-cutting problem (Steinhaus, 1948), a heterogeneous resource has to be divided among n agents with different valuations in a proportional way --- giving each agent a piece with a value of at least 1/n of the total. In many applications, such as dividing a land-estate or a time-interval, it is also important that the pieces are connected. We propose two additional requirements: resource-monotonicity (RM) and population-monotonicity (PM). When either the cake or the set of agents changes and the cake is re-divided using the same rule, the utility of all remaining agents must change in the same direction. Classic cake-cutting protocols are neither RM nor PM. Moreover, we prove that no Pareto-optimal proportional division rule can be either RM or PM. Motivated by this negative result, we search for division rules that are weakly-Pareto-optimal --- no other division is strictly better for all agents. We present two such rules. The relative-equitable rule, which assigns the maximum possible relative value equal for all agents, is proportional and PM. The so-called rightmost-mark rule, which is an improved version of the Cut and Choose protocol, is proportional and RM for two agents.
Palindromic Decompositions with Gaps and Errors
Venue: arXiv cs.DS 2017
Year: 2017

Identifying palindromes in sequences has been an interesting line of research in combinatorics on words and also in computational biology, after the discovery of the relation of palindromes in the DNA sequence with the HIV virus. Efficient algorithms for the factorization of sequences into palindromes and maximal palindromes have been devised in recent years. We extend these studies by allowing gaps in decompositions and errors in palindromes, and also imposing a lower bound to the length of acceptable palindromes. We first present an algorithm for obtaining a palindromic decomposition of a string of length n with the minimal total gap length in time O(n log n * g) and space O(n g), where g is the number of allowed gaps in the decomposition. We then consider a decomposition of the string in maximal δ-palindromes (i.e. palindromes with δerrors under the edit or Hamming distance) and g allowed gaps. We present an algorithm to obtain such a decomposition with the minimal total gap length in time O(n (g + δ)) and space O(n g).
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Venue: arXiv cs.DS 2017
Year: 2017

The edit distance between two rooted ordered trees with $n$ nodes labeled from an alphabet~$Σ$ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic $O(n^3)$ time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic $O(n^{3-\varepsilon})$ time algorithm for tree edit distance is unlikely: For $|Σ| = Ω(n)$, a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For $|Σ| = O(1)$, a truly subcubic algorithm for tree edit distance implies an $O(n^{k-\varepsilon})$ algorithm for finding a maximum weight $k$-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC'15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.
One- and Two-Way Relay Optimization for MIMO Interference Networks
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers multiple-input multiple-output (MIMO) relay communication in multi-cellular (interference) systems in which MIMO source-destination pairs communicate simultaneously. It is assumed that due to severe attenuation and/or shadowing effects, communication links can be established only with the aid of a relay node. The aim is to minimize the maximal mean-square-error (MSE) among all the receiving nodes under constrained source and relay transmit powers. Both one- and two-way amplify-and-forward (AF) relaying mechanisms are considered. Since the exactly optimal solution for this practically appealing problem is intractable, we first propose optimizing the source, relay, and receiver matrices in an alternating fashion. Then we contrive a simplified semidefinite programming (SDP) solution based on the error covariance matrix decomposition technique, avoiding the high complexity of the iterative process. Numerical results reveal the effectiveness of the proposed schemes.
Multiple Access for 5G New Radio: Categorization, Evaluation, and Challenges
Venue: arXiv cs.IT 2017
Year: 2017

Next generation wireless networks require massive uplink connections as well as high spectral efficiency. It is well known that, theoretically, it is not possible to achieve the sum capacity of multi-user communications with orthogonal multiple access. To meet the challenging requirements of next generation networks, researchers have explored non-orthogonal and overloaded transmission technologies-known as new radio multiple access (NR-MA) schemes-for fifth generation (5G) networks. In this article, we discuss the key features of the promising NR-MA schemes for the massive uplink connections. The candidate schemes of NR-MA can be characterized by multiple access signatures (MA-signatures), such as codebook, sequence, and interleaver/scrambler. At the receiver side, advanced multi-user detection (MUD) schemes are employed to extract each user's data from non-orthogonally superposed data according to MA-signatures. Through link-level simulations, we compare the performances of NR-MA candidates under the same conditions. We further evaluate the sum rate performances of the NR-MA schemes using a 3-dimensional (3D) ray tracing tool based system-level simulator by reflecting realistic environments. Lastly, we discuss the tips for system operations as well as call attention to the remaining technical challenges.
Towards Effective Research-Paper Recommender Systems and User Modeling based on Mind Maps
Venue: arXiv cs.IR 2017
Year: 2017

While user-modeling and recommender systems successfully utilize items like emails, news, and movies, they widely neglect mind-maps as a source for user modeling. We consider this a serious shortcoming since we assume user modeling based on mind maps to be equally effective as user modeling based on other items. Hence, millions of mind-mapping users could benefit from user-modeling applications such as recommender systems. The objective of this doctoral thesis is to develop an effective user-modeling approach based on mind maps. To achieve this objective, we integrate a recommender system in our mind-mapping and reference-management software Docear. The recommender system builds user models based on the mind maps, and recommends research papers based on the user models. As part of our research, we identify several variables relating to mind-map-based user modeling, and evaluate the variables' impact on user-modeling effectiveness with an offline evaluation, a user study, and an online evaluation based on 430,893 recommendations displayed to 4,700 users. We find, among others, that the number of analyzed nodes, modification time, visibility of nodes, relations between nodes, and number of children and siblings of a node affect the effectiveness of user modeling. When all variables are combined in a favorable way, this novel approach achieves click-through rates of 7.20%, which is nearly twice as effective as the best baseline. In addition, we show that user modeling based on mind maps performs about as well as user modeling based on other items, namely the research articles users downloaded or cited. Our findings let us to conclude that user modeling based on mind maps is a promising research field, and that developers of mind-mapping applications should integrate recommender systems into their applications. Such systems could create additional value for millions of mind-mapping users.
Generalized Gabidulin codes over fields of any characteristic
Venue: arXiv cs.IT 2017
Year: 2017

We generalise Gabidulin codes to the case of infinite fields, eventually with characteristic zero. For this purpose, we consider an abstract field extension and any automorphism in the Galois group. We derive some conditions on the automorphism to be able to have a proper notion of rank metric which is in coherence with linearized polynomials. Under these conditions, we generalize Gabidulin codes and provide a decoding algorithm which decode both errors and erasures. Then, we focus on codes over integer rings and how to decode them. We are then faced with the problem of the exponential growth of intermediate values, and to circumvent the problem, it is natural to propose to do computations modulo a prime ideal. For this, we study the reduction of generalized Gabidulin codes over number ideals codes modulo a prime ideal, and show they are classical Gabidulin codes. As a consequence, knowing side information on the size of the errors or the message, we can reduce the decoding problem over the integer ring to a decoding problem over a finite field. We also give examples and timings.