OpenRaiser/Intern-Atlas huggingface dataset:
On the Solution of Large-Scale Robust Transmission Network Expansion Planning under Uncertain Demand and Generation Capacity
Venue: arXiv cs.CE 2016
Year: 2016

Two-stage robust optimization has emerged as a relevant approach to deal with uncertain demand and generation capacity in the transmission network expansion planning problem. Unfortunately, available solution methodologies for the resulting trilevel robust counterpart are unsuitable for large-scale problems. In order to overcome this shortcoming, this paper presents an alternative column-and-constraint generation algorithm wherein the max-min problem associated with the second stage is solved by a novel coordinate descent method. As a major salient feature, the proposed approach does not rely on the transformation of the second-stage problem to a single-level equivalent. As a consequence, bilinear terms involving dual variables or Lagrange multipliers do not arise, thereby precluding the use of computationally expensive big-M-based linearization schemes. Thus, not only is the computational effort reduced, but also the typically overlooked non-trivial tuning of bounding parameters for dual variables or Lagrange multipliers is avoided. The practical applicability of the proposed methodology is confirmed by numerical testing on several benchmarks including a case based on the Polish 2383-bus system, which is well beyond the capability of the robust methods available in the literature.
Performance Comparison of Short-Length Error-Correcting Codes
Venue: arXiv cs.IT 2016
Year: 2016

We compare the performance of short-length linear binary codes on the binary erasure channel and the binary-input Gaussian channel. We use a universal decoder that can decode any linear binary block code: Gaussian-elimination based Maximum-Likelihood decoder on the erasure channel and probabilistic Ordered Statistics Decoder on the Gaussian channel. As such we compare codes and not decoders. The word error rate versus the channel parameter is found for LDPC, Reed-Muller, Polar, and BCH codes at length 256 bits. BCH codes outperform other codes in absence of cyclic redundancy check. Under joint decoding, the concatenation of a cyclic redundancy check makes all codes perform very close to optimal lower bounds.
It wasn't me! Plausible Deniability in Web Search
Venue: arXiv cs.CR 2016
Year: 2016

Our ability to control the flow of sensitive personal information to online systems is key to trust in personal privacy on the internet. We ask how to detect, assess and defend user privacy in the face of search engine personalisation? We develop practical and scalable tools allowing a user to detect, assess and defend against threats to plausible deniability. We show that threats to plausible deniability of interest are readily detectable for all topics tested in an extensive testing program. We show this remains the case when attempting to disrupt search engine learning through noise query injection and click obfuscation are used. We use our model we design a defence technique exploiting uninteresting, proxy topics and show that it provides amore effective defence of plausible deniability in our experiments.
A Framework for Algebraic Characterizations in Recursive Analysis
Venue: arXiv cs.LO 2016
Year: 2016

Algebraic characterizations of the computational aspects of functions defined over the real numbers provide very effective tool to understand what computability and complexity over the reals, and generally over continuous spaces, mean. This is relevant for both communities of computer scientists and mathematical analysts, particularly the latter who do not understand (and/or like) the language of machines and string encodings. Recursive analysis can be considered the most standard framework of computation over continuous spaces, it is however defined in a very machine specific way which does not leave much to intuitiveness. Recently several characterizations, in the form of function algebras, of recursively computable functions and some sub-recursive classes were introduced. These characterizations shed light on the hidden behavior of recursive analysis as they convert complex computational operations on sequences of real objects to "simple" intuitive mathematical operations such as integration or taking limits. The authors previously presented a framework for obtaining algebraic characterizations at the complexity level over compact domains. The current paper presents a comprehensive extension to that framework. Though we focus our attention in this paper on functions defined over the whole real line, the framework, and accordingly the obtained results, can be easily extended to functions defined over arbitrary domains.
Optimistic and Pessimistic Neural Networks for Scene and Object Recognition
Venue: arXiv cs.CV 2016
Year: 2016

In this paper the application of uncertainty modeling to convolutional neural networks is evaluated. A novel method for adjusting the network's predictions based on uncertainty information is introduced. This allows the network to be either optimistic or pessimistic in its prediction scores. The proposed method builds on the idea of applying dropout at test time and sampling a predictive mean and variance from the network's output. Besides the methodological aspects, implementation details allowing for a fast evaluation are presented. Furthermore, a multilabel network architecture is introduced that strongly benefits from the presented approach. In the evaluation it will be shown that modeling uncertainty allows for improving the performance of a given model purely at test time without any further training steps. The evaluation considers several applications in the field of computer vision, including object classification and detection as well as scene attribute recognition.
Towards Evidence-Based Ontology for Supporting Systematic Literature Review
Venue: arXiv cs.DL 2016
Year: 2016

[Background]: Systematic Literature Review (SLR) has become an important software engineering research method but costs tremendous efforts. [Aim]: This paper proposes an approach to leverage on empirically evolved ontology to support automating key SLR activities. [Method]: First, we propose an ontology, SLRONT, built on SLR experiences and best practices as a groundwork to capture common terminologies and their relationships during SLR processes; second, we present an extended version of SLRONT, the COSONT and instantiate it with the knowledge and concepts extracted from structured abstracts. Case studies illustrate the details of applying it for supporting SLR steps. [Results]: Results show that through using COSONT, we acquire the same conclusion compared with sheer manual works, but the efforts involved is significantly reduced. [Conclusions]: The approach of using ontology could effectively and efficiently support the conducting of systematic literature review.
S-MART: Novel Tree-based Structured Learning Algorithms Applied to Tweet Entity Linking
Venue: arXiv cs.CL 2016
Year: 2016

Non-linear models recently receive a lot of attention as people are starting to discover the power of statistical and embedding features. However, tree-based models are seldom studied in the context of structured learning despite their recent success on various classification and ranking tasks. In this paper, we propose S-MART, a tree-based structured learning framework based on multiple additive regression trees. S-MART is especially suitable for handling tasks with dense features, and can be used to learn many different structures under various loss functions. We apply S-MART to the task of tweet entity linking --- a core component of tweet information extraction, which aims to identify and link name mentions to entities in a knowledge base. A novel inference algorithm is proposed to handle the special structure of the task. The experimental results show that S-MART significantly outperforms state-of-the-art tweet entity linking systems.
The Effect of DNS on Tor's Anonymity
Venue: arXiv cs.CR 2016
Year: 2016

Previous attacks that link the sender and receiver of traffic in the Tor network ("correlation attacks") have generally relied on analyzing traffic from TCP connections. The TCP connections of a typical client application, however, are often accompanied by DNS requests and responses. This additional traffic presents more opportunities for correlation attacks. This paper quantifies how DNS traffic can make Tor users more vulnerable to correlation attacks. We investigate how incorporating DNS traffic can make existing correlation attacks more powerful and how DNS lookups can leak information to third parties about anonymous communication. We (i) develop a method to identify the DNS resolvers of Tor exit relays; (ii) develop a new set of correlation attacks (DefecTor attacks) that incorporate DNS traffic to improve precision; (iii) analyze the Internet-scale effects of these new attacks on Tor users; and (iv) develop improved methods to evaluate correlation attacks. First, we find that there exist adversaries who can mount DefecTor attacks: for example, Google's DNS resolver observes almost 40% of all DNS requests exiting the Tor network. We also find that DNS requests often traverse ASes that the corresponding TCP connections do not transit, enabling additional ASes to gain information about Tor users' traffic. We then show that an adversary who can mount a DefecTor attack can often determine the website that a Tor user is visiting with perfect precision, particularly for less popular websites where the set of DNS names associated with that website may be unique to the site. We also use the Tor Path Simulator (TorPS) in combination with traceroute data from vantage points co-located with Tor exit relays to estimate the power of AS-level adversaries who might mount DefecTor attacks in practice.
Generalized Line Spectral Estimation via Convex Optimization
Venue: arXiv cs.IT 2016
Year: 2016

Line spectral estimation is the problem of recovering the frequencies and amplitudes of a mixture of a few sinusoids from equispaced samples. However, in a variety of signal processing problems arising in imaging, radar, and localization we do not have access directly to such equispaced samples. Rather we only observe a severely undersampled version of these observations through linear measurements. This paper is about such generalized line spectral estimation problems. We reformulate these problems as sparse signal recovery problems over a continuously indexed dictionary which can be solved via a convex program. We prove that the frequencies and amplitudes of the components of the mixture can be recovered perfectly from a near-minimal number of observations via this convex program. This result holds provided the frequencies are sufficiently separated, and the linear measurements obey natural conditions that are satisfied in a variety of applications.
Robust Time-Series Retrieval Using Probabilistic Adaptive Segmental Alignment
Venue: arXiv cs.DB 2016
Year: 2016

Traditional pairwise sequence alignment is based on matching individual samples from two sequences, under time monotonicity constraints. However, in many application settings matching subsequences (segments) instead of individual samples may bring in additional robustness to noise or local non-causal perturbations. This paper presents an approach to segmental sequence alignment that jointly segments and aligns two sequences, generalizing the traditional per-sample alignment. To accomplish this task, we introduce a distance metric between segments based on average pairwise distances and then present a modified pair-HMM (PHMM) that incorporates the proposed distance metric to solve the joint segmentation and alignment task. We also propose a relaxation to our model that improves the computational efficiency of the generic segmental PHMM. Our results demonstrate that this new measure of sequence similarity can lead to improved classification performance, while being resilient to noise, on a variety of sequence retrieval problems, from EEG to motion sequence classification.
Towards Scalable Network Delay Minimization
Venue: arXiv cs.DB 2016
Year: 2016

Reduction of end-to-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in the case of communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search-space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NP-hard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling and targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.
On the Group and Color Isomorphism Problems
Venue: arXiv cs.CC 2016
Year: 2016

In this paper, we prove results on the relationship between the complexity of the group and color isomorphism problems. The difficulty of color isomorphism problems is known to be closely linked to the the composition factors of the permutation group involved. Previous works are primarily concerned with applying color isomorphism to bou nded degree graph isomorphism, and have therefore focused on the alternating composit ion factors, since those are the bottleneck in the case of graph isomorphism. We consider the color isomorphism problem with composition factors restricted to those other than the alternating group, show that group isomorphism reduces in n^(O(log log n)) time to this problem, and, conversely, that a special case of this color isomorphism problem reduces to a slight generalization of group isomorphism. We then sharpen our results by identifying the projective special linear group as the main obstacle to faster algorithms for group isomorphism and prove that the aforementioned reduc tion from group isomorphism to color isomorphism in fact produces only cyclic and projective special linear factors. Our results demonstrate that, just as the alternatin g group was a barrier to faster algorithms for graph isomorphism for three decades, the projective special linear group is an obstacle to faster algorithms for group isomorphism.
Unsupervised Co-segmentation of 3D Shapes via Functional Maps
Venue: arXiv cs.GR 2016
Year: 2016

We present an unsupervised method for co-segmentation of a set of 3D shapes from the same class with the aim of segmenting the input shapes into consistent semantic parts and establishing their correspondence across the set. Starting from meaningful pre-segmentation of all given shapes individually, we construct the correspondence between same candidate parts and obtain the labels via functional maps. And then, we use these labels to mark the input shapes and obtain results of co-segmentation. The core of our algorithm is to seek for an optimal correspondence between semantically similar parts through functional maps and mark such shape parts. Experimental results on the benchmark datasets show the efficiency of this method and comparable accuracy to the state-of-the-art algorithms.
Flatness-based nonlinear control strategies for trajectory tracking of quadcopter systems
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes several nonlinear control strategies for trajectory tracking of a quadcopter system based on the property of differential flatness. Its originality is twofold. Firstly, it provides a flat output for the quadcopter dynamics capable of creating full flat parametrization of the states and inputs. Moreover, B-splines characterizations of the flat output and their properties allow for optimal trajectory generation subject to way-point constraints. Secondly, several control strategies based on computed torque control and feedback linearization are presented and compared. The advantages of flatness within each control strategy are analyzed and detailed through extensive simulation results.
DESQ: Frequent Sequence Mining with Subsequence Constraints
Venue: arXiv cs.DB 2016
Year: 2016

Frequent sequence mining methods often make use of constraints to control which subsequences should be mined. A variety of such subsequence constraints has been studied in the literature, including length, gap, span, regular-expression, and hierarchy constraints. In this paper, we show that many subsequence constraints---including and beyond those considered in the literature---can be unified in a single framework. A unified treatment allows researchers to study jointly many types of subsequence constraints (instead of each one individually) and helps to improve usability of pattern mining systems for practitioners. In more detail, we propose a set of simple and intuitive "pattern expressions" to describe subsequence constraints and explore algorithms for efficiently mining frequent subsequences under such general constraints. Our algorithms translate pattern expressions to compressed finite state transducers, which we use as computational model, and simulate these transducers in a way suitable for frequent sequence mining. Our experimental study on real-world datasets indicates that our algorithms---although more general---are competitive to existing state-of-the-art algorithms.
Flows Generating Nonlinear Eigenfunctions
Venue: arXiv cs.CV 2016
Year: 2016

Nonlinear variational methods have become very powerful tools for many image processing tasks. Recently a new line of research has emerged, dealing with nonlinear eigenfunctions induced by convex functionals. This has provided new insights and better theoretical understanding of convex regularization and introduced new processing methods. However, the theory of nonlinear eigenvalue problems is still at its infancy. We present a new flow that can generate nonlinear eigenfunctions of the form $T(u)=λu$, where $T(u)$ is a nonlinear operator and $λ\in \mathbb{R} $ is the eigenvalue. We develop the theory where $T(u)$ is a subgradient element of a regularizing one-homogeneous functional, such as total-variation (TV) or total-generalized-variation (TGV). We introduce two flows: a forward flow and an inverse flow; for which the steady state solution is a nonlinear eigenfunction. The forward flow monotonically smooths the solution (with respect to the regularizer) and simultaneously increases the $L^2$ norm. The inverse flow has the opposite characteristics. For both flows, the steady state depends on the initial condition, thus different initial conditions yield different eigenfunctions. This enables a deeper investigation into the space of nonlinear eigenfunctions, allowing to produce numerically diverse examples, which may be unknown yet. In addition we suggest an indicator to measure the affinity of a function to an eigenfunction and relate it to pseudo-eigenfunctions in the linear case.
Model-based Test Generation for Robotic Software: Automata versus Belief-Desire-Intention Agents
Venue: arXiv cs.AI 2016
Year: 2016

Robotic code needs to be verified to ensure its safety and functional correctness, especially when the robot is interacting with people. Testing real code in simulation is a viable option. However, generating tests that cover rare scenarios, as well as exercising most of the code, is a challenge amplified by the complexity of the interactions between the environment and the software. Model-based test generation methods can automate otherwise manual processes and facilitate reaching rare scenarios during testing. In this paper, we compare using Belief-Desire-Intention (BDI) agents as models for test generation with more conventional automata-based techniques that exploit model checking, in terms of practicality, performance, transferability to different scenarios, and exploration (`coverage'), through two case studies: a cooperative manufacturing task, and a home care scenario. The results highlight the advantages of using BDI agents for test generation. BDI agents naturally emulate the agency present in Human-Robot Interactions (HRIs), and are thus more expressive than automata. The performance of the BDI-based test generation is at least as high, and the achieved coverage is higher or equivalent, compared to test generation based on model checking automata.
The curse of variety in computing, and what can be done about it
Venue: arXiv cs.OH 2016
Year: 2016

Excess freedom in how computers are used creates problems that include: bit rot, problems with big data, problems in the creation and debugging of software, and problems with cyber security. To tame excess freedom, "tough love" is needed in the form of a {\em universal framework for the representation and processing of diverse kinds of knowledge} (UFK). The "SP machine", based on the "SP theory of intelligence", has the potential to provide that framework and to help solve the problems above. There is potential to reduce the near-4000 different kinds of computer file to one, and to reduce the hundreds of different computer languages to one.
Chronodes: Interactive Multi-focus Exploration of Event Sequences
Venue: arXiv cs.HC 2016
Year: 2016

The advent of mobile health technologies presents new challenges that existing visualizations, interactive tools, and algorithms are not yet designed to support. In dealing with uncertainty in sensor data and high-dimensional physiological records, we must seek to improve current tools that make sense of health data from traditional perspectives in event-based trend discovery. With Chronodes, a system developed to help researchers collect, interpret, and model mobile health (mHealth) data, we posit a series of interaction techniques that enable new approaches to understanding and exploring event-based data. From numerous and discontinuous mobile health data streams, Chronodes finds and visualizes frequent event sequences that reveal common chronological patterns across participants and days. By then promoting the sequences as interactive elements, Chronodes presents opportunities for finding, defining, and comparing cohorts of participants that exhibit particular behaviors. We applied Chronodes to a real 40GB mHealth dataset capturing about 400 hours of data. Through our pilot study with 20 behavioral and biomedical health experts, we gained insights into Chronodes' efficacy, limitations, and potential applicability to a wide range of healthcare scenarios.
Correct classification for big/smart/fast data machine learning
Venue: arXiv cs.LG 2016
Year: 2016

Table (database) / Relational database Classification for big/smart/fast data machine learning is one of the most important tasks of predictive analytics and extracting valuable information from data. It is core applied technique for what now understood under data science and/or artificial intelligence. Widely used Decision Tree (Random Forest) and rare used rule based PRISM , VFST, etc classifiers are empirical substitutions of theoretically correct to use Boolean functions minimization. Developing Minimization of Boolean functions algorithms is started long time ago by Edward Veitch's 1952. Since it, big efforts by wide scientific/industrial community was done to find feasible solution of Boolean functions minimization. In this paper we propose consider table data classification from mathematical point of view, as minimization of Boolean functions. It is shown that data representation may be transformed to Boolean functions form and how to use known algorithms. For simplicity, binary output function is used for development, what opens doors for multivalued outputs developments.