OpenRaiser/Intern-Atlas huggingface dataset:
Do Mobile Developers Ask on Q&A Sites About Error Codes Thrown by a Cross-Platform App Development Framework? An Empirical Study
Venue: arXiv cs.SE 2018
Year: 2018

During last years development frameworks have emerged to make easier the development and maintenance of cross-platform mobile applications. Xamarin framework is one of them: it takes as input an app written in C# and produces native code for Android, iOS and Windows Mobile platforms. When using Xamarin, developers can meet errors, identified with codes, thrown by the framework.Unfortunately, the Xamarin official documentation does not provide a complete description, solution or workaround for all those codes.In this paper, we analyze two sites of questions and answers related to Xamarin for finding questions that mention those error codes. We found in both sites that there are questions written by developers asking about Xamarin errors, and the majority of them have at least one answer. Our intuition is this discovered information could be useful for giving support to Xamarin developers.
Generalized HARQ Protocols with Delayed Channel State Information and Average Latency Constraints
Venue: arXiv cs.IT 2018
Year: 2018

In many wireless systems, the signal-to-interference-and-noise ratio that is applicable to a certain transmission, referred to as channel state information (CSI), can only be learned after the transmission has taken place and is thereby delayed (outdated). In such systems, hybrid automatic repeat request (HARQ) protocols are often used to achieve high throughput with low latency. This paper put forth the family of expandable message space (EMS) protocols that generalize the HARQ protocol and allow for rate adaptation based on delayed CSI at the transmitter (CSIT). Assuming a block-fading channel, the proposed EMS protocols are analyzed using dynamic programming. When full delayed CSIT is available and there is a constraint on the average decoding time, it is shown that the optimal zero outage EMS protocol has a particularly simple operational interpretation and that the throughput is identical to that of the backtrack retransmission request (BRQ) protocol. We also devise EMS protocols for the case in which CSIT is only available through a finite number of feedback messages. The numerical results demonstrate that the throughput of BRQ approaches the ergodic capacity quickly compared to HARQ, while EMS protocols with only three and four feedback messages achieve throughputs that are only slightly worse than that of BRQ.
A Novel Weighted Distance Measure for Multi-Attributed Graph
Venue: arXiv cs.SI 2018
Year: 2018

Due to exponential growth of complex data, graph structure has become increasingly important to model various entities and their interactions, with many interesting applications including, bioinformatics, social network analysis, etc. Depending on the complexity of the data, the underlying graph model can be a simple directed/undirected and/or weighted/un-weighted graph to a complex graph (aka multi-attributed graph) where vertices and edges are labelled with multi-dimensional vectors. In this paper, we present a novel weighted distance measure based on weighted Euclidean norm which is defined as a function of both vertex and edge attributes, and it can be used for various graph analysis tasks including classification and cluster analysis. The proposed distance measure has flexibility to increase/decrease the weightage of edge labels while calculating the distance between vertex-pairs. We have also proposed a MAGDist algorithm, which reads multi-attributed graph stored in CSV files containing the list of vertex vectors and edge vectors, and calculates the distance between each vertex-pair using the proposed weighted distance measure. Finally, we have proposed a multi-attributed similarity graph generation algorithm, MAGSim, which reads the output of MAGDist algorithm and generates a similarity graph that can be analysed using classification and clustering algorithms. The significance and accuracy of the proposed distance measure and algorithms is evaluated on Iris and Twitter data sets, and it is found that the similarity graph generated by our proposed method yields better clustering results than the existing similarity graph generation methods.
Unsupervised Open Relation Extraction
Venue: arXiv cs.CL 2018
Year: 2018

We explore methods to extract relations between named entities from free text in an unsupervised setting. In addition to standard feature extraction, we develop a novel method to re-weight word embeddings. We alleviate the problem of features sparsity using an individual feature reduction. Our approach exhibits a significant improvement by 5.8% over the state-of-the-art relation clustering scoring a F1-score of 0.416 on the NYT-FB dataset.
Resource Allocation for Solar Powered UAV Communication Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we investigate the resource allocation design for multicarrier (MC) systems employing a solar powered unmanned aerial vehicle (UAV) for providing communication services to multiple downlink users. We study the joint design of the three-dimensional positioning of the UAV and the power and subcarrier allocation for maximization of the system sum throughput. The algorithm design is formulated as a mixed-integer non-convex optimization problem, which requires a prohibitive computational complexity for obtaining the globally optimal solution. Therefore, a low-complexity suboptimal iterative solution based on successive convex approximation is proposed. Simulation results confirm that the proposed suboptimal algorithm achieves a substantially higher system sum throughput compared to several baseline schemes.
Even flying cops should think ahead
Venue: arXiv cs.DM 2018
Year: 2018

We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to catch a robber in G, we show that the required number of cops can be much larger, even for graphs with small maximum degree. In particular, we show that there are 3-regular graphs where a linear number of cops are needed.
Optimizing Prediction Intervals by Tuning Random Forest via Meta-Validation
Venue: arXiv cs.LG 2018
Year: 2018

Recent studies have shown that tuning prediction models increases prediction accuracy and that Random Forest can be used to construct prediction intervals. However, to our best knowledge, no study has investigated the need to, and the manner in which one can, tune Random Forest for optimizing prediction intervals { this paper aims to fill this gap. We explore a tuning approach that combines an effectively exhaustive search with a validation technique on a single Random Forest parameter. This paper investigates which, out of eight validation techniques, are beneficial for tuning, i.e., which automatically choose a Random Forest configuration constructing prediction intervals that are reliable and with a smaller width than the default configuration. Additionally, we present and validate three meta-validation techniques to determine which are beneficial, i.e., those which automatically chose a beneficial validation technique. This study uses data from our industrial partner (Keymind Inc.) and the Tukutuku Research Project, related to post-release defect prediction and Web application effort estimation, respectively. Results from our study indicate that: i) the default configuration is frequently unreliable, ii) most of the validation techniques, including previously successfully adopted ones such as 50/50 holdout and bootstrap, are counterproductive in most of the cases, and iii) the 75/25 holdout meta-validation technique is always beneficial; i.e., it avoids the likely counterproductive effects of validation techniques.
Handwriting Trajectory Recovery using End-to-End Deep Encoder-Decoder Network
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we introduce a novel technique to recover the pen trajectory of offline characters which is a crucial step for handwritten character recognition. Generally, online acquisition approach has more advantage than its offline counterpart as the online technique keeps track of the pen movement. Hence, pen tip trajectory retrieval from offline text can bridge the gap between online and offline methods. Our proposed framework employs sequence to sequence model which consists of an encoder-decoder LSTM module. Our encoder module consists of Convolutional LSTM network, which takes an offline character image as the input and encodes the feature sequence to a hidden representation. The output of the encoder is fed to a decoder LSTM and we get the successive coordinate points from every time step of the decoder LSTM. Although the sequence to sequence model is a popular paradigm in various computer vision and language translation tasks, the main contribution of our work lies in designing an end-to-end network for a decade old popular problem in Document Image Analysis community. Tamil, Telugu and Devanagari characters of LIPI Toolkit dataset are used for our experiments. Our proposed method has achieved superior performance compared to the other conventional approaches.
Rover Descent: Learning to optimize by learning to navigate on prototypical loss surfaces
Venue: arXiv cs.LG 2018
Year: 2018

Learning to optimize - the idea that we can learn from data algorithms that optimize a numerical criterion - has recently been at the heart of a growing number of research efforts. One of the most challenging issues within this approach is to learn a policy that is able to optimize over classes of functions that are fairly different from the ones that it was trained on. We propose a novel way of framing learning to optimize as a problem of learning a good navigation policy on a partially observable loss surface. To this end, we develop Rover Descent, a solution that allows us to learn a fairly broad optimization policy from training on a small set of prototypical two-dimensional surfaces that encompasses the classically hard cases such as valleys, plateaus, cliffs and saddles and by using strictly zero-order information. We show that, without having access to gradient or curvature information, we achieve state-of-the-art convergence speed on optimization problems not presented at training time such as the Rosenbrock function and other hard cases in two dimensions. We extend our framework to optimize over high dimensional landscapes, while still handling only two-dimensional local landscape information and show good preliminary results.
Combinatorial framework for planning in geological exploration
Venue: arXiv cs.AI 2018
Year: 2018

The paper describes combinatorial framework for planning of geological exploration for oil-gas fields. The suggested scheme of the geological exploration involves the following stages: (1) building of special 4-layer tree-like model (layer of geological exploration): productive layer, group of productive layers, oil-gas field, oil-gas region (or group of the fields); (2) generations of local design (exploration) alternatives for each low-layer geological objects: conservation, additional search, independent utilization, joint utilization; (3) multicriteria (i.e., multi-attribute) assessment of the design (exploration) alternatives and their interrelation (compatibility) and mapping if the obtained vector estimates into integrated ordinal scale; (4) hierarchical design ('bottom-up') of composite exploration plans for each oil-gas field; (5) integration of the plans into region plans and (6) aggregation of the region plans into a general exploration plan. Stages 2, 3, 4, and 5 are based on hierarchical multicriteria morphological design (HMMD) method (assessment of ranking of alternatives, selection and composition of alternatives into composite alternatives). The composition problem is based on morphological clique model. Aggregation of the obtained modular alternatives (stage 6) is based on detection of a alternatives 'kernel' and its extension by addition of elements (multiple choice model). In addition, the usage of multiset estimates for alternatives is described as well. The alternative estimates are based on expert judgment. The suggested combinatorial planning methodology is illustrated by numerical examples for geological exploration of Yamal peninsula.
Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness
Venue: arXiv cs.NE 2018
Year: 2018

Genetic algorithm (GA) is an efficient tool for solving optimization problems by evolving solutions, as it mimics the Darwinian theory of natural evolution. The mutation operator is one of the key success factors in GA, as it is considered the exploration operator of GA. Various mutation operators exist to solve hard combinatorial problems such as the TSP. In this paper, we propose a hybrid mutation operator called "IRGIBNNM", this mutation is a combination of two existing mutations, a knowledge-based mutation, and a random-based mutation. We also improve the existing "select best mutation" strategy using the proposed mutation. We conducted several experiments on twelve benchmark Symmetric traveling salesman problem (STSP) instances. The results of our experiments show the efficiency of the proposed mutation, particularly when we use it with some other mutations. Keyword: Knowledge-based mutation, Inversion mutation, Slide mutation, RGIBNNM, SBM.
Smoke: Fine-grained Lineage at Interactive Speed
Venue: arXiv cs.DB 2018
Year: 2018

Data lineage describes the relationship between individual input and output data items of a workflow, and has served as an integral ingredient for both traditional (e.g., debugging, auditing, data integration, and security) and emergent (e.g., interactive visualizations, iterative analytics, explanations, and cleaning) applications. The core, long-standing problem that lineage systems need to address---and the main focus of this paper---is to capture the relationships between input and output data items across a workflow with the goal to streamline queries over lineage. Unfortunately, current lineage systems either incur high lineage capture overheads, or lineage query processing costs, or both. As a result, applications, that in principle can express their logic declaratively in lineage terms, resort to hand-tuned implementations. To this end, we introduce Smoke, an in-memory database engine that neither lineage capture overhead nor lineage query processing needs to be compromised. To do so, Smoke introduces tight integration of the lineage capture logic into physical database operators; efficient, write-optimized lineage representations for storage; and optimizations when future lineage queries are known up-front. Our experiments on microbenchmarks and realistic workloads show that Smoke reduces the lineage capture overhead and streamlines lineage queries by multiple orders of magnitude compared to state-of-the-art alternatives. Our experiments on real-world applications highlight that Smoke can meet the latency requirements of interactive visualizations (e.g., <150ms) and outperform hand-written implementations of data profiling primitives.
Control of Large Swarms via Random Finite Set Theory
Venue: arXiv cs.SY 2018
Year: 2018

Controlling large swarms of robotic agents has many challenges including, but not limited to, computational complexity due to the number of agents, uncertainty in the functionality of each agent in the swarm, and uncertainty in the swarm's configuration. This work generalizes the swarm state using Random Finite Set (RFS) theory and solves the control problem using model predictive control which naturally handles the challenges. This work uses information divergence to define the distance between swarm RFS and a desired distribution. A stochastic optimal control problem is formulated using a modified L2 distance. Simulation results show that swarm densities converge to a target destination, and the RFS control formulation can vary in the number of target destinations.
Modeling and Performance Analysis of Full-Duplex Communications in Cache-Enabled D2D Networks
Venue: arXiv cs.IT 2018
Year: 2018

Cache-enabled Device-to-Device (D2D) communication is widely recognized as one of the key components of the emerging fifth generation (5G) cellular network architecture. However, conventional half-duplex (HD) transmission may not be sufficient to provide fast enough content delivery over D2D links in order to meet strict latency targets of emerging D2D applications. In-band full-duplex (FD), with its capability of allowing simultaneous transmission and reception, can improve spectral efficiency and reduce latency by providing more content delivery opportunities. In this paper, we consider a finite network of D2D nodes in which each node is endowed with FD capability. We first carefully list all possible operating modes for an arbitrary device using which we compute the number of devices that are actively transmitting at any given time. We then characterize network performance in terms of the success probability, which depends on the content availability, signal-to-interference ratio (SIR) distribution, as well as the operating mode of the D2D receiver. Our analysis concretely demonstrates that caching dictates the system performance in lower target SIR thresholds whereas interference dictates the performance at the higher target SIR thresholds.
Finding Pairwise Intersections of Rectangles in a Query Rectangle
Venue: arXiv cs.CG 2018
Year: 2018

We consider the following problem: Preprocess a set $\mathcal{S}$ of $n$ axis-parallel boxes in $\mathbb{R}^d$ so that given a query of an axis-parallel box in $\mathbb{R}^d$, the pairs of boxes of $\mathcal{S}$ whose intersection intersects the query box can be reported efficiently. For the case that $d=2$, we present a data structure of size $O(n\log n)$ supporting $O(\log n+k)$ query time, where $k$ is the size of the output. This improves the previously best known result by de Berg et al. which requires $O(\log n+ k\log n)$ query time using $O(n\log n)$ space. There has been no result known for this problem for higher dimensions, except that for $d=3$, the best known data structure supports $O(\sqrt{n}\log^2n+k\log^2n)$ query time using $O(n\sqrt {n}\log n)$ space. For a constant $d>2$, we present a data structure supporting $O(n^{1-δ}\log^{d-1} n + k \text{ polylog } n)$ query time for any constant $1/d\leqδ<1$. The size of the data structure is $O(n^{δd - 2δ+ 1}\log n)$.
Hybrid Gradient Boosting Trees and Neural Networks for Forecasting Operating Room Data
Venue: arXiv cs.LG 2018
Year: 2018

Time series data constitutes a distinct and growing problem in machine learning. As the corpus of time series data grows larger, deep models that simultaneously learn features and classify with these features can be intractable or suboptimal. In this paper, we present feature learning via long short term memory (LSTM) networks and prediction via gradient boosting trees (XGB). Focusing on the consequential setting of electronic health record data, we predict the occurrence of hypoxemia five minutes into the future based on past features. We make two observations: 1) long short term memory networks are effective at capturing long term dependencies based on a single feature and 2) gradient boosting trees are capable of tractably combining a large number of features including static features like height and weight. With these observations in mind, we generate features by performing "supervised" representation learning with LSTM networks. Augmenting the original XGB model with these features gives significantly better performance than either individual method.
Learning Networks from Random Walk-Based Node Similarities
Venue: arXiv cs.SI 2018
Year: 2018

Digital presence in the world of online social media entails significant privacy risks. In this work we consider a privacy threat to a social network in which an attacker has access to a subset of random walk-based node similarities, such as effective resistances (i.e., commute times) or personalized PageRank scores. Using these similarities, the attacker's goal is to infer as much information as possible about the underlying network, including any remaining unknown pairwise node similarities and edges. For the effective resistance metric, we show that with just a small subset of measurements, the attacker can learn a large fraction of edges in a social network, even when the measurements are noisy. We also show that it is possible to learn a graph which accurately matches the underlying network on all other effective resistances. This second observation is interesting from a data mining perspective, since it can be expensive to accurately compute all effective resistances. As an alternative, our graphs learned from just a subset of approximate effective resistances can be used as surrogates in a wide range of applications that use effective resistances to probe graph structure, including for graph clustering, node centrality evaluation, and anomaly detection. We obtain our results by formalizing the graph learning objective mathematically, using two optimization problems. One formulation is convex and can be solved provably in polynomial time. The other is not, but we solve it efficiently with projected gradient and coordinate descent. We demonstrate the effectiveness of these methods on a number of social networks obtained from Facebook. We also discuss how our methods can be generalized to other random walk-based similarities, such as personalized PageRank. Our code is available at https://github.com/cnmusco/graph-similarity-learning.
Optimality of Simple Layered Superposition Coding in the 3 User MISO BC with Finite Precision CSIT
Venue: arXiv cs.IT 2018
Year: 2018

We study the $K=3$ user multiple input single output (MISO) broadcast channel (BC) with $M=3$ antennas at the transmitter and $1$ antenna at each receiver, from the generalized degrees of freedom (GDoF) perspective, under the assumption that the channel state information at the transmitter (CSIT) is limited to finite precision. In particular, our goal is to identify a parameter regime where a simple layered superposition (SLS) coding scheme achieves the entire GDoF region. With $α_{ij}$ representing the channel strength parameter for the link from the $j^{th}$ antenna of the transmitter to the $i^{th}$ receiver, we prove that SLS is GDoF optimal without the need for time-sharing if $\max(α_{ki},α_{im})\leqα_{ii}$ and $α_{ki}+α_{im}\leα_{ii}+α_{km}$ for all $i,k\in[3],m\in[M]$. The GDoF region under this condition is a convex polyhedron. The result generalizes to arbitrary $M\geq 3$.
Sliding Suffix Tree using LCA
Venue: arXiv cs.DS 2018
Year: 2018

We consider a sliding window $W$ over a stream of characters from some alphabet of constant size. The user wants to perform deterministic substring matching on the current sliding window content and obtain positions of the matches. We present an indexed version of the sliding window using the suffix tree, the link tree and the lowest common ancestor. The data structure of size $Θ(|W|)$ has optimal time queries $Θ(m+occ)$ and amortized constant time updates, where $m$ is the length of the query string and $occ$ is the number of its occurrences.