OpenRaiser/Intern-Atlas huggingface dataset:
Novel Framework for Spectral Clustering using Topological Node Features(TNF)
Venue: arXiv cs.CV 2017
Year: 2017

Spectral clustering has gained importance in recent years due to its ability to cluster complex data as it requires only pairwise similarity among data points with its ease of implementation. The central point in spectral clustering is the process of capturing pair-wise similarity. In the literature, many research techniques have been proposed for effective construction of affinity matrix with suitable pair- wise similarity. In this paper a general framework for capturing pairwise affinity using local features such as density, proximity and structural similarity is been proposed. Topological Node Features are exploited to define the notion of density and local structure. These local features are incorporated into the construction of the affinity matrix. Experimental results, on widely used datasets such as synthetic shape datasets, UCI real datasets and MNIST handwritten datasets show that the proposed framework outperforms standard spectral clustering methods.
The pragmatics of clone detection and elimination
Venue: arXiv cs.SE 2017
Year: 2017

The occurrence of similar code, or `code clones', can make program code difficult to read, modify and maintain. This paper describes industrial case studies of clone detection and elimination using a refactoring and clone detection tool. We discuss how the studies have informed the design of the tool; more importantly, we use the studies to illustrate the complex set of decisions that have to be taken when performing clone elimination in practice. The case studies were performed in collaboration with engineers from Ericsson AB, and used the refactoring tool Wrangler for Erlang. However, the conclusions we draw are largely language-independent, and set out the pragmatics of clone detection and elimination in real-world projects as well as design principles for clone detection decision-support tools.
Near-Optimal $\varepsilon$-Kernel Construction and Related Problems
Venue: arXiv cs.CG 2017
Year: 2017

The computation of (i) $\varepsilon$-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In this paper, we describe new algorithms that offer significant improvements to their running times. In each case the input is a set of $n$ points in $R^d$ for a constant dimension $d \geq 3$ and an approximation parameter $\varepsilon > 0$. We reduce the respective running times (i) from $O((n + 1/\varepsilon^{d-2})\log(1/\varepsilon))$ to $O(n \log(1/\varepsilon) + 1/\varepsilon^{(d-1)/2+α})$, (ii) from $O((n + 1/\varepsilon^{d-2})\log(1/\varepsilon))$ to $O(n \log(1/\varepsilon) + 1/\varepsilon^{(d-1)/2+α})$, and (iii) from $O(n / \varepsilon^{d/3})$ to $O(n / \varepsilon^{d/4+α}),$ for an arbitrarily small constant $α> 0$. Result (i) is nearly optimal since the size of the output $\varepsilon$-kernel is $Θ(1/\varepsilon^{(d-1)/2})$ in the worst case. These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decompose space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures to approximately answer queries for (iv) nearest-neighbor searching, (v) directional width, and (vi) polytope membership.
Formalization of some central theorems in combinatorics of finite sets
Venue: arXiv cs.LO 2017
Year: 2017

We present fully formalized proofs of some central theorems from combinatorics. These are Dilworth's decomposition theorem, Mirsky's theorem, Hall's marriage theorem and the Erdős-Szekeres theorem. Dilworth's decomposition theorem is the key result among these. It states that in any finite partially ordered set (poset), the size of a smallest chain cover and a largest antichain are the same. Mirsky's theorem is a dual of Dilworth's decomposition theorem, which states that in any finite poset, the size of a smallest antichain cover and a largest chain are the same. We use Dilworth's theorem in the proofs of Hall's Marriage theorem and the Erdős-Szekeres theorem. The combinatorial objects involved in these theorems are sets and sequences. All the proofs are formalized in the Coq proof assistant. We develop a library of definitions and facts that can be used as a framework for formalizing other theorems on finite posets.
What Is the Best Way For Developers to Learn New Software Tools? An Empirical Comparison Between a Text and a Video Tutorial
Venue: arXiv cs.SE 2017
Year: 2017

The better developers can learn software tools, the faster they can start using them and the more efficiently they can later work with them. Tutorials are supposed to help here. While in the early days of computing, mostly text tutorials were available, nowadays software developers can choose among a huge number of tutorials for almost any popular software tool. However, only little research was conducted to understand how text tutorials differ from other tutorials, which tutorial types are preferred and, especially, which tutorial types yield the best learning experience in terms of efficiency and effectiveness, especially for programmers. To evaluate these questions, we converted an existing video tutorial for a novel software tool into a content-equivalent text tutorial. We then conducted an experiment in three groups where 42 undergraduate students from a software engineering course were commissioned to operate the software tool after using a tutorial: the first group was provided only with the video tutorial, the second group only with the text tutorial and the third group with both. In this context, the differences in terms of efficiency were almost negligible: We could observe that participants using only the text tutorial completed the tutorial faster than the participants with the video tutorial. However, the participants using only the video tutorial applied the learned content faster, achieving roughly the same bottom line performance. We also found that if both tutorial types are offered, participants prefer video tutorials for learning new content but text tutorials for looking up "missed" information. We mainly gathered our data through questionnaires and screen recordings and analyzed it with suitable statistical hypotheses tests. The data is available at [12]. Since producing tutorials requires effort, knowing with which type of tutorial learnability can be increased to which extent has an immense practical relevance. We conclude that in contexts similar to ours, while it would be ideal if software tool makers would offer both tutorial types, it seems more efficient to produce only text tutorials instead of a passive video tutorial - provided you manage to motivate your learners to use them.
Assortment Optimization under Unknown MultiNomial Logit Choice Models
Venue: arXiv cs.LG 2017
Year: 2017

Motivated by e-commerce, we study the online assortment optimization problem. The seller offers an assortment, i.e. a subset of products, to each arriving customer, who then purchases one or no product from her offered assortment. A customer's purchase decision is governed by the underlying MultiNomial Logit (MNL) choice model. The seller aims to maximize the total revenue in a finite sales horizon, subject to resource constraints and uncertainty in the MNL choice model. We first propose an efficient online policy which incurs a regret $\tilde{O}(T^{2/3})$, where $T$ is the number of customers in the sales horizon. Then, we propose a UCB policy that achieves a regret $\tilde{O}(T^{1/2})$. Both regret bounds are sublinear in the number of assortments.
Regularized arrangements of cellular complexes
Venue: arXiv cs.CG 2017
Year: 2017

In this paper we propose a novel algorithm to combine two or more cellular complexes, providing a minimal fragmentation of the cells of the resulting complex. We introduce here the idea of arrangement generated by a collection of cellular complexes, producing a cellular decomposition of the embedding space. The algorithm that executes this computation is called \emph{Merge} of complexes. The arrangements of line segments in 2D and polygons in 3D are special cases, as well as the combination of closed triangulated surfaces or meshed models. This algorithm has several important applications, including Boolean and other set operations over large geometric models, the extraction of solid models of biomedical structures at the cellular scale, the detailed geometric modeling of buildings, the combination of 3D meshes, and the repair of graphical models. The algorithm is efficiently implemented using the Linear Algebraic Representation (LAR) of argument complexes, i.e., on sparse representation of binary characteristic matrices of $d$-cell bases, well-suited for implementation in last generation accelerators and GPGPU applications.
Clustering-based Source-aware Assessment of True Robustness for Learning Models
Venue: arXiv cs.LG 2017
Year: 2017

We introduce a novel validation framework to measure the true robustness of learning models for real-world applications by creating source-inclusive and source-exclusive partitions in a dataset via clustering. We develop a robustness metric derived from source-aware lower and upper bounds of model accuracy even when data source labels are not readily available. We clearly demonstrate that even on a well-explored dataset like MNIST, challenging training scenarios can be constructed under the proposed assessment framework for two separate yet equally important applications: i) more rigorous learning model comparison and ii) dataset adequacy evaluation. In addition, our findings not only promise a more complete identification of trade-offs between model complexity, accuracy and robustness but can also help researchers optimize their efforts in data collection by identifying the less robust and more challenging class labels.
Portinari: A Data Exploration Tool to Personalize Cervical Cancer Screening
Venue: arXiv cs.CY 2017
Year: 2017

Socio-technical systems play an important role in public health screening programs to prevent cancer. Cervical cancer incidence has significantly decreased in countries that developed systems for organized screening engaging medical practitioners, laboratories and patients. The system automatically identifies individuals at risk of developing the disease and invites them for a screening exam or a follow-up exam conducted by medical professionals. A triage algorithm in the system aims to reduce unnecessary screening exams for individuals at low-risk while detecting and treating individuals at high-risk. Despite the general success of screening, the triage algorithm is a one-size-fits all approach that is not personalized to a patient. This can easily be observed in historical data from screening exams. Often patients rely on personal factors to determine that they are either at high risk or not at risk at all and take action at their own discretion. Can exploring patient trajectories help hypothesize personal factors leading to their decisions? We present Portinari, a data exploration tool to query and visualize future trajectories of patients who have undergone a specific sequence of screening exams. The web-based tool contains (a) a visual query interface (b) a backend graph database of events in patients' lives (c) trajectory visualization using sankey diagrams. We use Portinari to explore diverse trajectories of patients following the Norwegian triage algorithm. The trajectories demonstrated variable degrees of adherence to the triage algorithm and allowed epidemiologists to hypothesize about the possible causes.
A Brownian Motion Model and Extreme Belief Machine for Modeling Sensor Data Measurements
Venue: arXiv cs.NE 2017
Year: 2017

As the title suggests, we will describe (and justify through the presentation of some of the relevant mathematics) prediction methodologies for sensor measurements. This exposition will mainly be concerned with the mathematics related to modeling the sensor measurements.
Fair Allocation of Indivisible Goods: Improvement and Generalization
Venue: arXiv cs.GT 2017
Year: 2017

We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1-MMS allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-MMS allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a $2/3$-MMS allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The main idea for our $3/4$-MMS allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time.
SAR image despeckling through convolutional neural networks
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we investigate the use of discriminative model learning through Convolutional Neural Networks (CNNs) for SAR image despeckling. The network uses a residual learning strategy, hence it does not recover the filtered image, but the speckle component, which is then subtracted from the noisy one. Training is carried out by considering a large multitemporal SAR image and its multilook version, in order to approximate a clean image. Experimental results, both on synthetic and real SAR data, show the method to achieve better performance with respect to state-of-the-art techniques.
Efficient Version-Space Reduction for Visual Tracking
Venue: arXiv cs.CV 2017
Year: 2017

Discrminative trackers, employ a classification approach to separate the target from its background. To cope with variations of the target shape and appearance, the classifier is updated online with different samples of the target and the background. Sample selection, labeling and updating the classifier is prone to various sources of errors that drift the tracker. We introduce the use of an efficient version space shrinking strategy to reduce the labeling errors and enhance its sampling strategy by measuring the uncertainty of the tracker about the samples. The proposed tracker, utilize an ensemble of classifiers that represents different hypotheses about the target, diversify them using boosting to provide a larger and more consistent coverage of the version-space and tune the classifiers' weights in voting. The proposed system adjusts the model update rate by promoting the co-training of the short-memory ensemble with a long-memory oracle. The proposed tracker outperformed state-of-the-art trackers on different sequences bearing various tracking challenges.
Wireless Powered Dense Cellular Networks: How Many Small Cells Do We Need?
Venue: arXiv cs.NI 2017
Year: 2017

This paper focuses on wireless powered 5G dense cellular networks, where base station (BS) delivers energy to user equipment (UE) via the microwave radiation in sub-6 GHz or millimeter wave (mmWave) frequency, and UE uses the harvested energy for uplink information transmission. By addressing the impacts of employing different number of antennas and bandwidths at lower and higher frequencies, we evaluate the amount of harvested energy and throughput in such networks. Based on the derived results, we obtain the required small cell density to achieve an expected level of harvested energy or throughput. Also, we obtain that when the ratio of the number of sub-6 GHz BSs to that of the mmWave BSs is lower than a given threshold, UE harvests more energy from a mmWave BS than a sub-6 GHz BS. We find how many mmWave small cells are needed to perform better than the sub-6 GHz small cells from the perspectives of harvested energy and throughput. Our results reveal that the amount of harvested energy from the mmWave tier can be comparable to the sub-6 GHz counterpart in the dense scenarios. For the same tier scale, mmWave tier can achieve higher throughput. Furthermore, the throughput gap between different mmWave frequencies increases with the mmWave BS density.
Committees providing EJR can be computed efficiently
Venue: arXiv cs.GT 2017
Year: 2017

We identify a whole family of approval-based multi-winner voting rules that satisfy PJR. Moreover, we identify a subfamily of voting rules within this family that satisfy EJR. All these voting rules can be computed in polynomial time as long as the subalgorithms that characterize each rule within the family are polynomial. One of the voting rules that satisfy EJR can be computed in $O(n m k)$.
Provable Inductive Robust PCA via Iterative Hard Thresholding
Venue: arXiv cs.LG 2017
Year: 2017

The robust PCA problem, wherein, given an input data matrix that is the superposition of a low-rank matrix and a sparse matrix, we aim to separate out the low-rank and sparse components, is a well-studied problem in machine learning. One natural question that arises is that, as in the inductive setting, if features are provided as input as well, can we hope to do better? Answering this in the affirmative, the main goal of this paper is to study the robust PCA problem while incorporating feature information. In contrast to previous works in which recovery guarantees are based on the convex relaxation of the problem, we propose a simple iterative algorithm based on hard-thresholding of appropriate residuals. Under weaker assumptions than previous works, we prove the global convergence of our iterative procedure; moreover, it admits a much faster convergence rate and lesser computational complexity per iteration. In practice, through systematic synthetic and real data simulations, we confirm our theoretical findings regarding improvements obtained by using feature information.
Sparse Autoencoder for Unsupervised Nucleus Detection and Representation in Histopathology Images
Venue: arXiv cs.CV 2017
Year: 2017

Histopathology images are crucial to the study of complex diseases such as cancer. The histologic characteristics of nuclei play a key role in disease diagnosis, prognosis and analysis. In this work, we propose a sparse Convolutional Autoencoder (CAE) for fully unsupervised, simultaneous nucleus detection and feature extraction in histopathology tissue images. Our CAE detects and encodes nuclei in image patches in tissue images into sparse feature maps that encode both the location and appearance of nuclei. Our CAE is the first unsupervised detection network for computer vision applications. The pretrained nucleus detection and feature extraction modules in our CAE can be fine-tuned for supervised learning in an end-to-end fashion. We evaluate our method on four datasets and reduce the errors of state-of-the-art methods up to 42%. We are able to achieve comparable performance with only 5% of the fully-supervised annotation cost.
A Thematic Study of Requirements Modeling and Analysis for Self-Adaptive Systems
Venue: arXiv cs.SE 2017
Year: 2017

Over the last decade, researchers and engineers have developed a vast body of methodologies and technologies in requirements engineering for self-adaptive systems. Although existing studies have explored various aspects of this topic, few of them have categorized and summarized these areas of research in require-ments modeling and analysis. This study aims to investigate the research themes based on the utilized modeling methods and RE activities. We conduct a thematic study in the systematic literature review. The results are derived by synthesizing the extracted data with statistical methods. This paper provides an updated review of the research literature, enabling researchers and practitioners to better understand the research themes in these areas and identify research gaps which need to be further studied.
Combining Lexical and Syntactic Features for Detecting Content-dense Texts in News
Venue: arXiv cs.CL 2017
Year: 2017

Content-dense news report important factual information about an event in direct, succinct manner. Information seeking applications such as information extraction, question answering and summarization normally assume all text they deal with is content-dense. Here we empirically test this assumption on news articles from the business, U.S. international relations, sports and science journalism domains. Our findings clearly indicate that about half of the news texts in our study are in fact not content-dense and motivate the development of a supervised content-density detector. We heuristically label a large training corpus for the task and train a two-layer classifying model based on lexical and unlexicalized syntactic features. On manually annotated data, we compare the performance of domain-specific classifiers, trained on data only from a given news domain and a general classifier in which data from all four domains is pooled together. Our annotation and prediction experiments demonstrate that the concept of content density varies depending on the domain and that naive annotators provide judgement biased toward the stereotypical domain label. Domain-specific classifiers are more accurate for domains in which content-dense texts are typically fewer. Domain independent classifiers reproduce better naive crowdsourced judgements. Classification prediction is high across all conditions, around 80%.
Learning a Variational Network for Reconstruction of Accelerated MRI Data
Venue: arXiv cs.CV 2017
Year: 2017

Purpose: To allow fast and high-quality reconstruction of clinical accelerated multi-coil MR data by learning a variational network that combines the mathematical structure of variational models with deep learning. Theory and Methods: Generalized compressed sensing reconstruction formulated as a variational model is embedded in an unrolled gradient descent scheme. All parameters of this formulation, including the prior model defined by filter kernels and activation functions as well as the data term weights, are learned during an offline training procedure. The learned model can then be applied online to previously unseen data. Results: The variational network approach is evaluated on a clinical knee imaging protocol. The variational network reconstructions outperform standard reconstruction algorithms in terms of image quality and residual artifacts for all tested acceleration factors and sampling patterns. Conclusion: Variational network reconstructions preserve the natural appearance of MR images as well as pathologies that were not included in the training data set. Due to its high computational performance, i.e., reconstruction time of 193 ms on a single graphics card, and the omission of parameter tuning once the network is trained, this new approach to image reconstruction can easily be integrated into clinical workflow.