OpenRaiser/Intern-Atlas huggingface dataset:
A Note on the Flip Distance Problem for Edge-Labeled Triangulations
Venue: arXiv cs.CG 2018
Year: 2018

For both triangulations of point sets and simple polygons, it is known that determining the flip distance between two triangulations is an NP-hard problem. To gain more insight into flips of triangulations and to characterize "where edges go" when flipping from one triangulation to another, flips in edge-labeled triangulations have lately attracted considerable interest. In a recent breakthrough, Lubiw, Masárová, and Wagner (in Proc. 33rd Symp. of Computational Geometry, 2017) prove the so-called "Orbit Conjecture" for edge-labeled triangulations and ask for the complexity of the flip distance problem in the edge-labeled setting. By revisiting and modifying the hardness proofs for the unlabeled setting, we show in this note that the flip distance problem is APX-hard for edge-labeled triangulations of point sets and NP-hard for triangulations of simple polygons. The main technical challenge is to show that this remains true even if the source and target triangulation are the same when disregarding the labeling.
A Set-Theoretic Framework for Parallel Graph Rewriting
Venue: arXiv cs.LO 2018
Year: 2018

We tackle the problem of attributed graph transformations and propose a new algorithmic approach for defining parallel graph transformations allowing overlaps. We start by introducing some abstract operations over graph structures. Then, we define the notion of rewrite rules as three inclusions of the form $L \supseteq K \supseteq M \subseteq R$. We provide six conditions that parallel graph rewrite relations should ideally satisfy, which lead us to define two distinct full parallel graph rewrite relations. A central notion of regularity of matchings is proved to be equivalent to these six conditions, and to the equality of these two relations. Furthermore, we take advantage of the symmetries that may occur in $L$, $K$, $M$ and $R$ and define another pair of rewrite relations that factor out possibly many equivalent matchings up to their common symmetries. These definitions and the corresponding proofs combine operations on graphs with group-theoretic notions, thus illustrating the relevance of our framework.
Fuzzy Clustering to Identify Clusters at Different Levels of Fuzziness: An Evolutionary Multi-Objective Optimization Approach
Venue: arXiv cs.NE 2018
Year: 2018

Fuzzy clustering methods identify naturally occurring clusters in a dataset, where the extent to which different clusters are overlapped can differ. Most methods have a parameter to fix the level of fuzziness. However, the appropriate level of fuzziness depends on the application at hand. This paper presents Entropy $c$-Means (ECM), a method of fuzzy clustering that simultaneously optimizes two contradictory objective functions, resulting in the creation of fuzzy clusters with different levels of fuzziness. This allows ECM to identify clusters with different degrees of overlap. ECM optimizes the two objective functions using two multi-objective optimization methods, Non-dominated Sorting Genetic Algorithm II (NSGA-II), and Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D). We also propose a method to select a suitable trade-off clustering from the Pareto front. Experiments on challenging synthetic datasets as well as real-world datasets show that ECM leads to better cluster detection compared to the conventional fuzzy clustering methods as well as previously used multi-objective methods for fuzzy clustering.
Uncovering the Spread of Chagas Disease in Argentina and Mexico
Venue: arXiv cs.CY 2018
Year: 2018

Chagas disease is a neglected disease, and information about its geographical spread is very scarse. We analyze here mobility and calling patterns in order to identify potential risk zones for the disease, by using public health information and mobile phone records. Geolocalized call records are rich in social and mobility information, which can be used to infer whether an individual has lived in an endemic area. We present two case studies in Latin American countries. Our objective is to generate risk maps which can be used by public health campaign managers to prioritize detection campaigns and target specific areas. Finally, we analyze the value of mobile phone data to infer long-term migrations, which play a crucial role in the geographical spread of Chagas disease.
Fast Flexible Function Dispatch in Julia
Venue: arXiv cs.PL 2018
Year: 2018

Technical computing is a challenging application area for programming languages to address. This is evinced by the unusually large number of specialized languages in the area (e.g. MATLAB, R), and the complexity of common software stacks, often involving multiple languages and custom code generators. We believe this is ultimately due to key characteristics of the domain: highly complex operators, a need for extensive code specialization for performance, and a desire for permissive high-level programming styles allowing productive experimentation. The Julia language attempts to provide a more effective structure for this kind of programming by allowing programmers to express complex polymorphic behaviors using dynamic multiple dispatch over parametric types. The forms of extension and reuse permitted by this paradigm have proven valuable for technical computing. We report on how this approach has allowed domain experts to express useful abstractions while simultaneously providing a natural path to better performance for high-level technical code.
Hybrid approach for transliteration of Algerian arabizi: a primary study
Venue: arXiv cs.CL 2018
Year: 2018

A hybrid approach for the transliteration of Algerian Arabizi: A primary study In this paper, we present a hybrid approach for the transliteration of the Algerian Arabizi. We define a set of rules enable us the passage from Arabizi to Arabic. Through these rules, we generate a set of candidates for the transliteration of each Arabizi word into arabic. Then, we extract the best candidate. This approach was evaluated by using three test corpora, and the obtained results show an improvement of the precision score which is equal to 75.11% for the best result. These results allow us to verify that our approach is very competitive comparing to others works that treat Arabizi transliteration in general. Keywords: Arabizi, Dialecte Algérien, Arabizi Algérien, Translitération.
Model Approximation Using Cascade of Tree Decompositions
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we present a general, multistage framework for graphical model approximation using a cascade of models such as trees. In particular, we look at the problem of covariance matrix approximation for Gaussian distributions as linear transformations of tree models. This is a new way to decompose the covariance matrix. Here, we propose an algorithm which incorporates the Cholesky factorization method to compute the decomposition matrix and thus can approximate a simple graphical model using a cascade of the Cholesky factorization of the tree approximation transformations. The Cholesky decomposition enables us to achieve a tree structure factor graph at each cascade stage of the algorithm which facilitates the use of the message passing algorithm since the approximated graph has less loops compared to the original graph. The overall graph is a cascade of factor graphs with each factor graph being a tree. This is a different perspective on the approximation model, and algorithms such as Gaussian belief propagation can be used on this overall graph. Here, we present theoretical result that guarantees the convergence of the proposed model approximation using the cascade of tree decompositions. In the simulations, we look at synthetic and real data and measure the performance of the proposed framework by comparing the KL divergences.
Band selection with Higher Order Multivariate Cumulants for small target detection in hyperspectral images
Venue: arXiv cs.CV 2018
Year: 2018

In the small target detection problem a pattern to be located is on the order of magnitude less numerous than other patterns present in the dataset. This applies both to the case of supervised detection, where the known template is expected to match in just a few areas and unsupervised anomaly detection, as anomalies are rare by definition. This problem is frequently related to the imaging applications, i.e. detection within the scene acquired by a camera. To maximize available data about the scene, hyperspectral cameras are used; at each pixel, they record spectral data in hundreds of narrow bands. The typical feature of hyperspectral imaging is that characteristic properties of target materials are visible in the small number of bands, where light of certain wavelength interacts with characteristic molecules. A target-independent band selection method based on statistical principles is a versatile tool for solving this problem in different practical applications. Combination of a regular background and a rare standing out anomaly will produce a distortion in the joint distribution of hyperspectral pixels. Higher Order Cumulants Tensors are a natural `window' into this distribution, allowing to measure properties and suggest candidate bands for removal. While there have been attempts at producing band selection algorithms based on the 3 rd cumulant's tensor i.e. the joint skewness, the literature lacks a systematic analysis of how the order of the cumulant tensor used affects effectiveness of band selection in detection applications. In this paper we present an analysis of a general algorithm for band selection based on higher order cumulants. We discuss its usability related to the observed breaking points in performance, depending both on method order and the desired number of bands. Finally we perform experiments and evaluate these methods in a hyperspectral detection scenario.
MARS: Memory Aware Reordered Source
Venue: arXiv cs.PF 2018
Year: 2018

Memory bandwidth is critical in today's high performance computing systems. The bandwidth is particularly paramount for GPU workloads such as 3D Gaming, Imaging and Perceptual Computing, GPGPU due to their data-intensive nature. As the number of threads and data streams in the GPUs increases with each generation, along with a high available memory bandwidth, memory efficiency is also crucial in order to achieve desired performance. In presence of multiple concurrent data streams, the inherent locality in a single data stream is often lost as these streams are interleaved while moving through multiple levels of memory system. In DRAM based main memory, the poor request locality reduces row-buffer reuse resulting in underutilized and inefficient memory bandwidth. In this paper we propose Memory-Aware Reordered Source (\textit{MARS}) architecture to address memory inefficiency arising from highly interleaved data streams. The key idea of \textit{MARS} is that with a sufficiently large lookahead before the main memory, data streams can be reordered based on their row-buffer address to regain the lost locality and improve memory efficiency. We show that \textit{MARS} improves achieved memory bandwidth by 11\% for a set of synthetic microbenchmarks. Moreover, MARS does so without any specific knowledge of the memory configuration.
Self-Adaptive Systems in Organic Computing: Strategies for Self-Improvement
Venue: arXiv cs.AI 2018
Year: 2018

With the intensified use of intelligent things, the demands on the technological systems are increasing permanently. A possible approach to meet the continuously changing challenges is to shift the system integration from design to run-time by using adaptive systems. Diverse adaptivity properties, so-called self-* properties, form the basis of these systems and one of the properties is self-improvement. It describes the ability of a system not only to adapt to a changing environment according to a predefined model, but also the capability to adapt the adaptation logic of the whole system. In this paper, a closer look is taken at the structure of self-adaptive systems. Additionally, the systems' ability to improve themselves during run-time is described from the perspective of Organic Computing. Furthermore, four different strategies for self-improvement are presented, following the taxonomy of self-adaptation suggested by Christian Krupitzer et al.
Overlapping community detection using superior seed set selection in social networks
Venue: arXiv cs.SI 2018
Year: 2018

Community discovery in the social network is one of the tremendously expanding areas which earn interest among researchers for the past one decade. There are many already existing algorithms. However, new seed-based algorithms establish an emerging drift in this area. The basic idea behind these strategies is to identify exceptional nodes in the given network, called seeds, around which communities can be located. This paper proposes a blended strategy for locating suitable superior seed set by applying various centrality measures and using them to find overlapping communities. The examination of the algorithm has been performed regarding the goodness of the identified communities with the help of intra-cluster density and inter-cluster density. Finally, the runtime of the proposed algorithm has been compared with the existing community detection algorithms showing remarkable improvement.
Weakly supervised learning of indoor geometry by dual warping
Venue: arXiv cs.CV 2018
Year: 2018

A major element of depth perception and 3D understanding is the ability to predict the 3D layout of a scene and its contained objects for a novel pose. Indoor environments are particularly suitable for novel view prediction, since the set of objects in such environments is relatively restricted. In this work we address the task of 3D prediction especially for indoor scenes by leveraging only weak supervision. In the literature 3D scene prediction is usually solved via a 3D voxel grid. However, such methods are limited to estimating rather coarse 3D voxel grids, since predicting entire voxel spaces has large computational costs. Hence, our method operates in image-space rather than in voxel space, and the task of 3D estimation essentially becomes a depth image completion problem. We propose a novel approach to easily generate training data containing depth maps with realistic occlusions, and subsequently train a network for completing those occluded regions. Using multiple publicly available dataset~\cite{song2017semantic,Silberman:ECCV12} we benchmark our method against existing approaches and are able to obtain superior performance. We further demonstrate the flexibility of our method by presenting results for new view synthesis of RGB-D images.
An Iterative Path-Breaking Approach with Mutation and Restart Strategies for the MAX-SAT Problem
Venue: arXiv cs.AI 2018
Year: 2018

Although Path-Relinking is an effective local search method for many combinatorial optimization problems, its application is not straightforward in solving the MAX-SAT, an optimization variant of the satisfiability problem (SAT) that has many real-world applications and has gained more and more attention in academy and industry. Indeed, it was not used in any recent competitive MAX-SAT algorithms in our knowledge. In this paper, we propose a new local search algorithm called IPBMR for the MAX-SAT, that remedies the drawbacks of the Path-Relinking method by using a careful combination of three components: a new strategy named Path-Breaking to avoid unpromising regions of the search space when generating trajectories between two elite solutions; a weak and a strong mutation strategies, together with restarts, to diversify the search; and stochastic path generating steps to avoid premature local optimum solutions. We then present experimental results to show that IPBMR outperforms two of the best state-of-the-art MAX-SAT solvers, and an empirical investigation to identify and explain the effect of the three components in IPBMR.
Improved Bit-Flipping Algorithm for Successive Cancellation Decoding of Polar Codes
Venue: arXiv cs.IT 2018
Year: 2018

The interest in polar codes has been increasing significantly since their adoption for use in the 5$^{\rm th}$ generation wireless systems standard. Successive cancellation (SC) decoding algorithm has low implementation complexity, but yields mediocre error-correction performance at the code lengths of interest. SC-Flip algorithm improves the error-correction performance of SC by identifying possibly erroneous decisions made by SC and re-iterates after flipping one bit. It was recently shown that only a portion of bit-channels are most likely to be in error. In this work, we investigate the average log-likelihood ratio (LLR) values and their distribution related to the erroneous bit-channels, and develop the Thresholded SC-Flip (TSCF) decoding algorithm. We also replace the LLR selection and sorting of SC-Flip with a comparator to reduce the implementation complexity. Simulation results demonstrate that for practical code lengths and a wide range of rates, TSCF shows negligible loss compared to the error-correction performance obtained when all single-errors are corrected. At matching maximum iterations, TSCF has an error-correction performance gain of up to $0.45$ dB compared with SC-Flip decoding. At matching error-correction performance, the computational complexity of TSCF is reduced by up to $40\%$ on average, and requires up to $5\times$ lower maximum number of iterations.
Building Safer AGI by introducing Artificial Stupidity
Venue: arXiv cs.AI 2018
Year: 2018

Artificial Intelligence (AI) achieved super-human performance in a broad variety of domains. We say that an AI is made Artificially Stupid on a task when some limitations are deliberately introduced to match a human's ability to do the task. An Artificial General Intelligence (AGI) can be made safer by limiting its computing power and memory, or by introducing Artificial Stupidity on certain tasks. We survey human intellectual limits and give recommendations for which limits to implement in order to build a safe AGI.
User oriented assessment of vibration suppression by command shaping in a supernumerary wearable robotic arm
Venue: arXiv cs.RO 2018
Year: 2018

Supernumerary Robotic Limbs (SRLs) exhibit inherently compliant behavior due to the elasticity present at the intersection of human tissue and the robot. This compliance, can prominently influence the operation of some SRLs, depending on the application. In order to control the residual vibrations of SRLs, we have used an input-shaping method which is a computationally inexpensive approach. The effectiveness of this method in controlling the residual vibrations of a SRL has been proven using robustness analysis. User studies show that reducing the vibrations using input shaping directly increases the user satisfaction and comfort by at least 9%. It is also observed that 36% of the users preferred unshaped commands. We hypothesize that the shaped commands put a higher cognitive load on the user compared to unshaped commands. This shows that when dealing with human-robot interaction, user satisfaction becomes an equally important parameter as traditional performance criteria and should be taken into account while evaluating the success of any vibration-control method.
Hierarchical Attention: What Really Counts in Various NLP Tasks
Venue: arXiv cs.CL 2018
Year: 2018

Attention mechanisms in sequence to sequence models have shown great ability and wonderful performance in various natural language processing (NLP) tasks, such as sentence embedding, text generation, machine translation, machine reading comprehension, etc. Unfortunately, existing attention mechanisms only learn either high-level or low-level features. In this paper, we think that the lack of hierarchical mechanisms is a bottleneck in improving the performance of the attention mechanisms, and propose a novel Hierarchical Attention Mechanism (Ham) based on the weighted sum of different layers of a multi-level attention. Ham achieves a state-of-the-art BLEU score of 0.26 on Chinese poem generation task and a nearly 6.5% averaged improvement compared with the existing machine reading comprehension models such as BIDAF and Match-LSTM. Furthermore, our experiments and theorems reveal that Ham has greater generalization and representation ability than existing attention mechanisms.
Knowledge Graph Embedding with Entity Neighbors and Deep Memory Network
Venue: arXiv cs.CL 2018
Year: 2018

Knowledge Graph Embedding (KGE) aims to represent entities and relations of knowledge graph in a low-dimensional continuous vector space. Recent works focus on incorporating structural knowledge with additional information, such as entity descriptions, relation paths and so on. However, common used additional information usually contains plenty of noise, which makes it hard to learn valuable representation. In this paper, we propose a new kind of additional information, called entity neighbors, which contain both semantic and topological features about given entity. We then develop a deep memory network model to encode information from neighbors. Employing a gating mechanism, representations of structure and neighbors are integrated into a joint representation. The experimental results show that our model outperforms existing KGE methods utilizing entity descriptions and achieves state-of-the-art metrics on 4 datasets.
Going Viral: The Epidemiological Strategy of Referral Marketing
Venue: arXiv cs.CY 2018
Year: 2018

By now, Internet word-of-mouth marketing has established its importance for almost every kind of products. When word-of-mouth spread of a marketing campaign goes viral, the success of its strategy has been proved to be path-breaking for the firms. The current study is designed to extend knowledge about customer response to these campaigns, and is focused on the motivations that lead them to different responses. Primary goal of this study is to investigate the reasons that drive this dynamics and to generate a justified theoretical framework of diffusion dynamics of viral marketing campaigns. A rigorous analysis of data obtained through a questionnaire-based survey helped us to understand how people, who are from different age group, sex and locations, define and evaluate the encounter with a referral campaign online, in similar and unique logical ways. The key finding was a conceptual framework of customer motivation which in turn dictates the dynamics of the campaign. We have identified important themes related to customer motives, like significance of: incentives and ease, inherent forgetting, reminders from peers compared to company's remarketing mails, trust and brand value etc. Drawing an analogy with differential equation-based models of infectious disease spread, this paper further provides some initial evidence that participation in viral marketing campaigns has several consumer related dynamical factors which can be incorporated in an epidemiological model for mathematical treatment, to indicate key operational factors in ensuring an effective spread of the marketing campaign.
Statistics of the Eigenvalues of a Noisy Multi-Soliton Pulse
Venue: arXiv cs.IT 2018
Year: 2018

For Nonlinear-Frequency Division-Multiplexed (NFDM) systems, the statistics of the received nonlinear spectrum in the presence of additive white Gaussian noise (AWGN) is an open problem. We present a novel method, based on the Fourier collocation algorithm, to compute these statistics.