OpenRaiser/Intern-Atlas huggingface dataset:
Edge Detection for Pattern Recognition: A Survey
Venue: arXiv cs.CV 2016
Year: 2016

This review provides an overview of the literature on the edge detection methods for pattern recognition that inspire from the understanding of human vision. We note that edge detection is one of the most fundamental process within the low level vision and provides the basis for the higher level visual intelligence in primates. The recognition of the patterns within the images relate closely to the spatiotemporal processes of edge formations, and its implementation needs a crossdisciplanry approach in neuroscience, computing and pattern recognition. In this review, the edge detectors are grouped in as edge features, gradients and sketch models, and some example applications are provided for reference. We note a significant increase in the amount of published research in the last decade that utilizes edge features in a wide range of problems in computer vision and image understanding having a direct implication to pattern recognition with images.
Energy-Efficient Time Synchronization Based on Asynchronous Source Clock Frequency Recovery and Reverse Two-Way Message Exchanges in Wireless Sensor Networks
Venue: arXiv cs.NI 2016
Year: 2016

We consider energy-efficient time synchronization in a wireless sensor network where a head node (i.e., a gateway between wired and wireless networks and a center of data fusion) is equipped with a powerful processor and supplied power from outlet, and sensor nodes (i.e., nodes measuring data and connected only through wireless channels) are limited in processing and battery-powered. It is this asymmetry that our study focuses on; unlike most existing schemes to save the power of all network nodes, we concentrate on battery-powered sensor nodes in minimizing energy consumption for time synchronization. We present a time synchronization scheme based on asynchronous source clock frequency recovery and reverse two-way message exchanges combined with measurement data report messages, where we minimize the number of message transmissions from sensor nodes, and carry out the performance analysis of the estimation of both measurement time and clock frequency with lower bounds for the latter. Simulation results verify that the proposed scheme outperforms the schemes based on conventional two-way message exchanges with and without clock frequency recovery in terms of the accuracy of measurement time estimation and the number of message transmissions and receptions at sensor nodes as an indirect measure of energy efficiency.
Optimized and Trusted Collision Avoidance for Unmanned Aerial Vehicles using Approximate Dynamic Programming (Technical Report)
Venue: arXiv cs.RO 2016
Year: 2016

Safely integrating unmanned aerial vehicles into civil airspace is contingent upon development of a trustworthy collision avoidance system. This paper proposes an approach whereby a parameterized resolution logic that is considered trusted for a given range of its parameters is adaptively tuned online. Specifically, to address the potential conservatism of the resolution logic with static parameters, we present a dynamic programming approach for adapting the parameters dynamically based on the encounter state. We compute the adaptation policy offline using a simulation-based approximate dynamic programming method that accommodates the high dimensionality of the problem. Numerical experiments show that this approach improves safety and operational performance compared to the baseline resolution logic, while retaining trustworthiness.
Wearable Embroidered Muscle Activity Sensing Device for the Human Upper Leg
Venue: arXiv cs.HC 2016
Year: 2016

Within the last decade, running has become one of the most popular physical activities in the world. Although the benefits of running are numerous, there is a risk of Running Related Injuries (RRI) of the lower extremities. Electromyography (EMG) techniques have previously been used to study causes of RRIs, but the complexity of this technology limits its use to a laboratory setting. As running is primarily an outdoors activity, this lack of technology acts as a barrier to the study of RRIs in natural environments. This study presents a minimally invasive wearable muscle sensing device consisting of jogging leggings with embroidered surface EMG (sEMG) electrodes capable of recording muscle activity data of the quadriceps group. To test the use of the device, a proof of concept study consisting of $N=2$ runners performing a set of $5km$ running trials is presented in which the effect of running surfaces on muscle fatigue, a potential cause of RRIs, is evaluated. Results show that muscle fatigue can be analysed from the sEMG data obtained through the wearable device, and that running on soft surfaces (such as sand) may increase the likelihood of suffering from RRIs.
Personalized Federated Search at LinkedIn
Venue: arXiv cs.IR 2016
Year: 2016

LinkedIn has grown to become a platform hosting diverse sources of information ranging from member profiles, jobs, professional groups, slideshows etc. Given the existence of multiple sources, when a member issues a query like "software engineer", the member could look for software engineer profiles, jobs or professional groups. To tackle this problem, we exploit a data-driven approach that extracts searcher intents from their profile data and recent activities at a large scale. The intents such as job seeking, hiring, content consuming are used to construct features to personalize federated search experience. We tested the approach on the LinkedIn homepage and A/B tests show significant improvements in member engagement. As of writing this paper, the approach powers all of federated search on LinkedIn homepage.
"Why Should I Trust You?": Explaining the Predictions of Any Classifier
Venue: arXiv cs.LG 2016
Year: 2016

Despite widespread adoption, machine learning models remain mostly black boxes. Understanding the reasons behind predictions is, however, quite important in assessing trust, which is fundamental if one plans to take action based on a prediction, or when choosing whether to deploy a new model. Such understanding also provides insights into the model, which can be used to transform an untrustworthy model or prediction into a trustworthy one. In this work, we propose LIME, a novel explanation technique that explains the predictions of any classifier in an interpretable and faithful manner, by learning an interpretable model locally around the prediction. We also propose a method to explain models by presenting representative individual predictions and their explanations in a non-redundant way, framing the task as a submodular optimization problem. We demonstrate the flexibility of these methods by explaining different models for text (e.g. random forests) and image classification (e.g. neural networks). We show the utility of explanations via novel experiments, both simulated and with human subjects, on various scenarios that require trust: deciding if one should trust a prediction, choosing between models, improving an untrustworthy classifier, and identifying why a classifier should not be trusted.
Towards an Efficient Smart Space Architecture
Venue: arXiv cs.CY 2016
Year: 2016

A smart space offers entirely new opportunities for end users by adapting services accordingly to make life easy. A number of architectural designs have been proposed to design context awareness systems and adaptation behavior. However, the quality of the system depends on the degree of satisfaction of the initials needs. In this paper, we discuss three main indicators of quality design for smart spaces that are strongly related to the context modules and reasoning process: functionality, reusability and changeability. A general layered architecture system is presented to define the principal components that should constitute any context aware adaptive system.
A Harmonic Extension Approach for Collaborative Ranking
Venue: arXiv cs.LG 2016
Year: 2016

We present a new perspective on graph-based methods for collaborative ranking for recommender systems. Unlike user-based or item-based methods that compute a weighted average of ratings given by the nearest neighbors, or low-rank approximation methods using convex optimization and the nuclear norm, we formulate matrix completion as a series of semi-supervised learning problems, and propagate the known ratings to the missing ones on the user-user or item-item graph globally. The semi-supervised learning problems are expressed as Laplace-Beltrami equations on a manifold, or namely, harmonic extension, and can be discretized by a point integral method. We show that our approach does not impose a low-rank Euclidean subspace on the data points, but instead minimizes the dimension of the underlying manifold. Our method, named LDM (low dimensional manifold), turns out to be particularly effective in generating rankings of items, showing decent computational efficiency and robust ranking quality compared to state-of-the-art methods.
A note and a correction on measuring cognitive distance in multiple dimensions
Venue: arXiv cs.DL 2016
Year: 2016

In a previous article (Rahman, Guns, Rousseau, and Engels, 2015) we described several approaches to determine the cognitive distance between two units. One of these approaches was based on what we called barycenters in N dimensions. The present note corrects this terminology and introduces the more adequate term 'similarity-adapted publication vectors'. Furthermore, we correct an error in normalization and explain the importance of scale invariance in determining cognitive distance. We also consider weighted cosine similarity as an alternative approach to determine cognitive (dis)similarity. Overall, we find that the three approaches (distance between barycenters, distance between similarity-adapted publication vectors, and weighted cosine similarity) yield very similar results.
Work-Efficient Parallel and Incremental Graph Connectivity
Venue: arXiv cs.DS 2016
Year: 2016

On an evolving graph that is continuously updated by a high-velocity stream of edges, how can one efficiently maintain if two vertices are connected? This is the connectivity problem, a fundamental and widely studied problem on graphs. We present the first shared-memory parallel algorithm for incremental graph connectivity that is both provably work-efficient and has polylogarithmic parallel depth. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement and has good practical performance. Our experiments show a throughput of hundreds of millions of edges per second on a $20$-core machine.
Robust Influence Maximization
Venue: arXiv cs.SI 2016
Year: 2016

Uncertainty about models and data is ubiquitous in the computational social sciences, and it creates a need for robust social network algorithms, which can simultaneously provide guarantees across a spectrum of models and parameter settings. We begin an investigation into this broad domain by studying robust algorithms for the Influence Maximization problem, in which the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions, typically derived from different influence models or different parameter settings for the same model. The different parameter settings could be derived from observed cascades on different topics, under different conditions, or at different times. The algorithm's goal is to identify a set of k nodes who are simultaneously influential for all influence functions, compared to the (function-specific) optimum solutions. We show strong approximation hardness results for this problem unless the algorithm gets to select at least a logarithmic factor more seeds than the optimum solution. However, when enough extra seeds may be selected, we show that techniques of Krause et al. can be used to approximate the optimum robust influence to within a factor of 1 - 1/e. We evaluate this bicriteria approximation algorithm against natural heuristics on several real-world data sets. Our experiments indicate that the worst-case hardness does not necessarily translate into bad performance on real-world data sets; all algorithms perform fairly well.
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Venue: arXiv cs.LG 2016
Year: 2016

Strongly Rayleigh distributions are natural generalizations of product and determinantal probability distributions and satisfy strongest form of negative dependence properties. We show that the "natural" Monte Carlo Markov Chain (MCMC) is rapidly mixing in the support of a {\em homogeneous} strongly Rayleigh distribution. As a byproduct, our proof implies Markov chains can be used to efficiently generate approximate samples of a $k$-determinantal point process. This answers an open question raised by Deshpande and Rademacher.
Simulation Study of an Energy-Efficient Time Synchronization Scheme based on Source Clock Frequency Recovery in Asymmetric Wireless Sensor Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper we report preliminary results of a simulation study on an energy-efficient time synchronization scheme based on source clock frequency recovery (SCFR) at sensor nodes in asymmetric wireless sensor networks (WSNs), where a head node --- serving as a gateway between wired and wireless networks --- is equipped with a powerful processor and supplied power from outlet, and sensor nodes --- connected only through wireless channels --- are limited in processing and battery-powered. In the SCFR-based WSN time synchronization scheme, we concentrate on battery-powered sensor nodes and reduce their energy consumption by minimizing the number of message transmissions from sensor nodes to the head node. Through simulation experiments we analyze the performance of the SCFR-based WSN time synchronization scheme, including the impact of SCFR on time synchronization based on two-way message exchange, and demonstrate the feasibility of the proposed time synchronization scheme.
Energy-Efficient Joint Congestion Control and Resource Optimization in Heterogeneous Cloud Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

The heterogeneous cloud radio access network (HCRAN) is a promising paradigm which integrates the advantages of cloud radio access network (C-RAN) and heterogeneous network (HetNet). In this paper, we study the joint congestion control and resource optimization to explore the energy efficiency (EE)-guaranteed tradeoff between throughput utility and delay performance in a downlink slotted H-CRAN. We formulate the considered problem as a stochastic optimization problem, which maximizes the utility of average throughput and maintains the network stability subject to required EE constraint and transmit power consumption constraints by traffic admission control, user association, resource block allocation and power allocation. Leveraging on the Lyapunov optimization technique, the stochastic optimization problem can be transformed and decomposed into three separate subproblems which can be solved concurrently at each slot. The third mixed-integer nonconvex subproblem is efficiently solved utilizing the continuity relaxation of binary variables and the Lagrange dual decomposition method. Theoretical analysis shows that the proposal can quantitatively control the throughput-delay performance tradeoff with required EE performance. Simulation results consolidate the theoretical analysis and demonstrate the advantages of the proposal from the prospective of queue stability and power consumption.
Lasserre Lower Bounds and Definability of Semidefinite Programming
Venue: arXiv cs.LO 2016
Year: 2016

For a large class of optimization problems, namely those that can be expressed as finite-valued constraint satisfaction problems (VCSPs), we establish a dichotomy on the number of levels of the Lasserre hierarchy of semi-definite programs (SDPs) that are required to solve the problem exactly. In particular, we show that if a finite-valued constraint problem is not solved exactly by its basic linear programming relaxation, it is also not solved exactly by any sub-linear number of levels of the Lasserre hierarchy. The lower bounds are established through logical undefinability results. We show that the linear programming relaxation of the problem, as well as the SDP corresponding to any fixed level of the Lasserre hierarchy is interpretable in a VCSP instance by means of formulas of fixed-point logic with counting. We also show that the solution of an SDP can be expressed in this logic. Together, these results give a way of translating lower bounds on the number of variables required in counting logic to express a VCSP into lower bounds on the number of levels required in the Lasserre hierarchy to eliminate the integrality gap. As a special case, we obtain the same dichotomy for the class of MAXCSP problems, generalizing some earlier Lasserre lower bound results of Schoenebeck.
Improved Bounds on the Stretch Factor of $Y_4$
Venue: arXiv cs.CG 2016
Year: 2016

We establish an upper bound of 4.94 on the stretch factor of the Yao graph $Y_4^\infty$ defined in the $L_\infty$-metric, improving upon the best previously known upper bound of 6.31. We also establish an upper bound of 54.62 on the stretch factor of the Yao graph $Y_4$ defined in the Euclidean metric, improving upon the best previously known upper bound of 662.16.
Cybernetic Interpretation of the Riemann Zeta Function
Venue: arXiv cs.SY 2016
Year: 2016

This paper uses cybernetic approach to study behavior of the Riemann zeta function. It is based on the elementary cybernetic concepts like feedback, transfer functions, time delays, PI (Proportional--Integral) controllers or FOPDT (First Order Plus Dead Time) models, respectively. An unusual dynamic interpretation of the Riemann zeta function is obtained.
Whither probabilistic security management for real-time operation of power systems ?
Venue: arXiv cs.SY 2016
Year: 2016

This paper investigates the stakes of introducing probabilistic approaches for the management of power system's security. In real-time operation, the aim is to arbitrate in a rational way between preventive and corrective control, while taking into account i) the prior probabilities of contingencies, ii) the possible failure modes of corrective control actions, iii) the socio-economic consequences of service interruptions. This work is a first step towards the construction of a globally coherent decision making framework for security management from long-term system expansion, via mid-term asset management, towards short-term operation planning and real-time operation.
On the fine-grained complexity of rainbow coloring
Venue: arXiv cs.DS 2016
Year: 2016

The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\ge 2$, there is no algorithm for Rainbow k-Coloring running in time $2^{o(n^{3/2})}$, unless ETH fails. Motivated by this negative result we consider two parameterized variants of the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is FPT when parameterized by $|S|$. We also study Maximum Rainbow k-Coloring problem, where we are additionally given an integer $q$ and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $k\ge 2$ (thus proving that the problem is FPT), extending the result of Ananth et al. [FSTTCS 2011].
Testing Quality Requirements of a System-of-Systems in the Public Sector - Challenges and Potential Remedies
Venue: arXiv cs.SE 2016
Year: 2016

Quality requirements is a difficult concept in software projects, and testing software qualities is a well-known challenge. Without proper management of quality requirements, there is an increased risk that the software product under development will not meet the expectations of its future users. In this paper, we share experiences from testing quality requirements when developing a large system-of-systems in the public sector in Sweden. We complement the experience reporting by analyzing documents from the case under study. As a final step, we match the identified challenges with solution proposals from the literature. We report five main challenges covering inadequate requirements engineering and disconnected test managers. Finally, we match the challenges to solutions proposed in the scientific literature, including integrated requirements engineering, the twin peaks model, virtual plumblines, the QUPER model, and architecturally significant requirements. Our experiences are valuable to other large development projects struggling with testing of quality requirements. Furthermore, the report could be used by as input to process improvement activities in the case under study.
An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems
Venue: arXiv cs.SE 2016
Year: 2016

We present the first systematic analysis of the characteristics of patch search spaces for automatic patch generation systems. We analyze the search spaces of two current state-of-the-art systems, SPR and Prophet, with 16 different search space configurations. Our results are derived from an analysis of 1104 different search spaces and 768 patch generation executions. Together these experiments consumed over 9000 hours of CPU time on Amazon EC2. The analysis shows that 1) correct patches are sparse in the search spaces (typically at most one correct patch per search space per defect), 2) incorrect patches that nevertheless pass all of the test cases in the validation test suite are typically orders of magnitude more abundant, and 3) leveraging information other than the test suite is therefore critical for enabling the system to successfully isolate correct patches. We also characterize a key tradeoff in the structure of the search spaces. Larger and richer search spaces that contain correct patches for more defects can actually cause systems to find fewer, not more, correct patches. We identify two reasons for this phenomenon: 1) increased validation times because of the presence of more candidate patches and 2) more incorrect patches that pass the test suite and block the discovery of correct patches. These fundamental properties, which are all characterized for the first time in this paper, help explain why past systems often fail to generate correct patches and help identify challenges, opportunities, and productive future directions for the field.
An Estimation Method Using Periodic Inspection of Indicators
Venue: arXiv cs.OH 2016
Year: 2016

This paper proposes a new approach for estimating the failure time distribution using the indicator data. The indicators, which are checked by periodic inspection of a standby redundant system, only convey whether at least one failure occurs per interval. The estimation procedure first obtains the estimation of the forward recurrence time using the indicator data. Then the mean is estimated based on its relationship with the forward recurrence time. And the estimation of the sampled Cdf is thus derived based on its relationship with the forward recurrence time and the mean. Finally, the Cdf function is estimated using interpolation method. The simulation results showed that the estimation method performed well for the four Weibull distributions.