OpenRaiser/Intern-Atlas huggingface dataset:
Matchings in Geometric Graphs
Venue: arXiv cs.CG 2016
Year: 2016

A geometric graph is a graph whose vertex set is a set of points in the plane and whose edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A geometric matching is a matching in a geometric graph. In this thesis, we study matching problems in various geometric graphs. Among the family of geometric graphs we look at complete graphs, complete bipartite graphs, complete multipartite graphs, Delaunay graphs, Gabriel graphs, and $Θ$-graphs. The classical matching problem is to find a matching of maximum size in a given graph. We study this problem as well as some of its variants on geometric graphs. The bottleneck matching problem is to find a maximum matching that minimizes the length of the longest edge. The plane matching problem is to find a maximum matching so that the edges in the matching are pairwise non-crossing. A geometric matching is strong with respect to a given shape $S$ if we can assign to each edge in the matching a scaled version of $S$ such that the shapes representing the edges are pairwise disjoint. The strong matching problem is to find a maximum strong matching with respect to a given shape. The matching packing problem is to pack as many edge-disjoint perfect matchings as possible into a geometric graph. We study these problems and establish lower and upper bounds on the size of different kinds of matchings in various geometric graphs. We also present algorithms for computing such matchings. Some of the presented bounds are tight, while the others need to be sharpened.
Ten Blue Links on Mars
Venue: arXiv cs.IR 2016
Year: 2016

This paper explores a simple question: How would we provide a high-quality search experience on Mars, where the fundamental physical limit is speed-of-light propagation delays on the order of tens of minutes? On Earth, users are accustomed to nearly instantaneous response times from search engines. Is it possible to overcome orders-of-magnitude longer latency to provide a tolerable user experience on Mars? In this paper, we formulate the searching from Mars problem as a tradeoff between "effort" (waiting for responses from Earth) and "data transfer" (pre-fetching or caching data on Mars). The contribution of our work is articulating this design space and presenting two case studies that explore the effectiveness of baseline techniques, using publicly available data from the TREC Total Recall and Sessions Tracks. We intend for this research problem to be aspirational and inspirational - even if one is not convinced by the premise of Mars colonization, there are Earth-based scenarios such as searching from a rural village in India that share similar constraints, thus making the problem worthy of exploration and attention from researchers.
An Evolving Cascade System Based on A Set Of Neo Fuzzy Nodes
Venue: arXiv cs.AI 2016
Year: 2016

Neo-fuzzy elements are used as nodes for an evolving cascade system. The proposed system can tune both its parameters and architecture in an online mode. It can be used for solving a wide range of Data Mining tasks (namely time series forecasting). The evolving cascade system with neo-fuzzy nodes can process rather large data sets with high speed and effectiveness.
An Evolving Neuro-Fuzzy System with Online Learning/Self-learning
Venue: arXiv cs.AI 2016
Year: 2016

An architecture of a new neuro-fuzzy system is proposed. The basic idea of this approach is to tune both synaptic weights and membership functions with the help of the supervised learning and self-learning paradigms. The approach to solving the problem has to do with evolving online neuro-fuzzy systems that can process data under uncertainty conditions. The results prove the effectiveness of the developed architecture and the learning procedure.
An Ensemble of Adaptive Neuro-Fuzzy Kohonen Networks for Online Data Stream Fuzzy Clustering
Venue: arXiv cs.AI 2016
Year: 2016

A new approach to data stream clustering with the help of an ensemble of adaptive neuro-fuzzy systems is proposed. The proposed ensemble is formed with adaptive neuro-fuzzy self-organizing Kohonen maps in a parallel processing mode. A final result is chosen by the best neuro-fuzzy self-organizing Kohonen map.
Information Overload in Group Communication: From Conversation to Cacophony in the Twitch Chat
Venue: arXiv cs.SI 2016
Year: 2016

Online communication channels, especially social web platforms, are rapidly replacing traditional ones. Online platforms allow users to overcome physical barriers, enabling worldwide participation. However, the power of online communication bears an important negative consequence --- we are exposed to too much information to process. Too many participants, for example, can turn online public spaces into noisy, overcrowded fora where no meaningful conversation can be held. Here we analyze a large dataset of public chat logs from Twitch, a popular video streaming platform, in order to examine how information overload affects online group communication. We measure structural and textual features of conversations such as user output, interaction, and information content per message across a wide range of information loads. Our analysis reveals the existence of a transition from a conversational state to a cacophony --- a state of overload with lower user participation, more copy-pasted messages, and less information per message. These results hold both on average and at the individual level for the majority of users. This study provides a quantitative basis for further studies of the social effects of information overload, and may guide the design of more resilient online communication systems.
On the Price of Stability of Undirected Multicast Games
Venue: arXiv cs.DS 2016
Year: 2016

In multicast network design games, a set of agents choose paths from their source locations to a common sink with the goal of minimizing their individual costs, where the cost of an edge is divided equally among the agents using it. Since the work of Anshelevich et al. (FOCS 2004) that introduced network design games, the main open problem in this field has been the price of stability (PoS) of multicast games. For the special case of broadcast games (every vertex is a terminal, i.e., has an agent), a series of works has culminated in a constant upper bound on the PoS (Bilo` et al., FOCS 2013). However, no significantly sub-logarithmic bound is known for multicast games. In this paper, we make progress toward resolving this question by showing a constant upper bound on the PoS of multicast games for quasi-bipartite graphs. These are graphs where all edges are between two terminals (as in broadcast games) or between a terminal and a nonterminal, but there is no edge between nonterminals. This represents a natural class of intermediate generality between broadcast and multicast games. In addition to the result itself, our techniques overcome some of the fundamental difficulties of analyzing the PoS of general multicast games, and are a promising step toward resolving this major open problem.
Revisiting Link Prediction: Evolving Models and Real Data Findings
Venue: arXiv cs.SI 2016
Year: 2016

The explosive growth of Web 2.0, which was characterized by the creation of online social networks, has reignited the study of factors that could help us understand the growth and dynamism of these networks. Various generative network models have been proposed, including the Barabasi-Albert and Watts-Strogatz models. In this study, we revisit the problem from a perspective that seeks to compare results obtained from these generative models with those from real networks. To this end, we consider the dating network Skout Inc. An analysis is performed on the topological characteristics of the network that could explain the creation of new network links. Afterwards, the results are contrasted with those obtained from the Barabasi-Albert and Watts-Strogatz generative models. We conclude that a key factor that could explain the creation of links originates in its cluster structure, where link recommendations are more precise in Watts-Strogatz segmented networks than in Barabasi-Albert hierarchical networks. This result reinforces the need to establish more and better network segmentation algorithms that are capable of clustering large networks precisely and efficiently.
Model-based Outdoor Performance Capture
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new model-based method to accurately reconstruct human performances captured outdoors in a multi-camera setup. Starting from a template of the actor model, we introduce a new unified implicit representation for both, articulated skeleton tracking and nonrigid surface shape refinement. Our method fits the template to unsegmented video frames in two stages - first, the coarse skeletal pose is estimated, and subsequently non-rigid surface shape and body pose are jointly refined. Particularly for surface shape refinement we propose a new combination of 3D Gaussians designed to align the projected model with likely silhouette contours without explicit segmentation or edge detection. We obtain reconstructions of much higher quality in outdoor settings than existing methods, and show that we are on par with state-of-the-art methods on indoor scenes for which they were designed
Automated Big Text Security Classification
Venue: arXiv cs.CR 2016
Year: 2016

In recent years, traditional cybersecurity safeguards have proven ineffective against insider threats. Famous cases of sensitive information leaks caused by insiders, including the WikiLeaks release of diplomatic cables and the Edward Snowden incident, have greatly harmed the U.S. government's relationship with other governments and with its own citizens. Data Leak Prevention (DLP) is a solution for detecting and preventing information leaks from within an organization's network. However, state-of-art DLP detection models are only able to detect very limited types of sensitive information, and research in the field has been hindered due to the lack of available sensitive texts. Many researchers have focused on document-based detection with artificially labeled "confidential documents" for which security labels are assigned to the entire document, when in reality only a portion of the document is sensitive. This type of whole-document based security labeling increases the chances of preventing authorized users from accessing non-sensitive information within sensitive documents. In this paper, we introduce Automated Classification Enabled by Security Similarity (ACESS), a new and innovative detection model that penetrates the complexity of big text security classification/detection. To analyze the ACESS system, we constructed a novel dataset, containing formerly classified paragraphs from diplomatic cables made public by the WikiLeaks organization. To our knowledge this paper is the first to analyze a dataset that contains actual formerly sensitive information annotated at paragraph granularity.
Spectral Angle Based Unary Energy Functions for Spatial-Spectral Hyperspectral Classification using Markov Random Fields
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose and compare two spectral angle based approaches for spatial-spectral classification. Our methods use the spectral angle to generate unary energies in a grid-structured Markov random field defined over the pixel labels of a hyperspectral image. The first approach is to use the exponential spectral angle mapper (ESAM) kernel/covariance function, a spectral angle based function, with the support vector machine and the Gaussian process classifier. The second approach is to directly use the minimum spectral angle between the test pixel and the training pixels as the unary energy. We compare the proposed methods with the state-of-the-art Markov random field methods that use support vector machines and Gaussian processes with squared exponential kernel/covariance function. In our experiments with two datasets, it is seen that using minimum spectral angle as unary energy produces better or comparable results to the existing methods at a smaller running time.
Ranking of classification algorithms in terms of mean-standard deviation using A-TOPSIS
Venue: arXiv cs.LG 2016
Year: 2016

In classification problems when multiples algorithms are applied to different benchmarks a difficult issue arises, i.e., how can we rank the algorithms? In machine learning it is common run the algorithms several times and then a statistic is calculated in terms of means and standard deviations. In order to compare the performance of the algorithms, it is very common to employ statistical tests. However, these tests may also present limitations, since they consider only the means and not the standard deviations of the obtained results. In this paper, we present the so called A-TOPSIS, based on TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), to solve the problem of ranking and comparing classification algorithms in terms of means and standard deviations. We use two case studies to illustrate the A-TOPSIS for ranking classification algorithms and the results show the suitability of A-TOPSIS to rank the algorithms. The presented approach is general and can be applied to compare the performance of stochastic algorithms in machine learning. Finally, to encourage researchers to use the A-TOPSIS for ranking algorithms we also presented in this work an easy-to-use A-TOPSIS web framework.
P_3-Games on Chordal Bipartite Graphs
Venue: arXiv cs.DS 2016
Year: 2016

Let G=(V,E) be a connected graph. A set U subseteq V is convex if G[U] is connected and all vertices of V\U have at most one neighbor in U. Let sigma(W) denote the unique smallest convex set that contains W subseteq V. Two players play the following game. Consider a convex set U and call it the `playground.' Initially, U = emptyset. When U=V, the player to move loses the game. Otherwise, that player chooses a vertex x in V\U which is at distance at most two from U. The effect of the move is that the playground U changes into sigma(U cup {x}) and the opponent is presented with this new playground. A graph is chordal bipartite if it is bipartite and has no induced cycle of length more than four. In this paper we show that, when G is chordal bipartite, there is a polynomial-time algorithm that computes the Grundy number of the P_3-game played on G. This implies that there is an efficient algorithm to decide whether the first player has a winning strategy.
Study of Tomlinson-Harashima Precoding Strategies for Physical-Layer Security in Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose novel non-linear precoders for the downlink of a multi-user MIMO system with the existence of multiple eavesdroppers. The proposed non-linear precoders are designed to improve the physical-layer secrecy rate. Specifically, we combine the non-linear successive optimization Tomlinson-Harashima precoding (SO-THP) with generalized matrix inversion (GMI) technique to maximize the physical-layer secrecy rate. For the purpose of comparison, we examine different traditional precoders with the proposed algorithm in terms of secrecy rate as well as BER performance. We also investigate simplified generalized matrix inversion (S-GMI) and lattice-reduction (LR) techniques in order to efficiently compute the parameters of the precoders. We further conduct computational complexity and secrecy rate analysis of the proposed and existing algorithms. In addition, in the scenario without knowledge of channel state information (CSI) to the eavesdroppers, a strategy of injecting artificial noise (AN) prior to the transmission is employed to enhance the physical-layer secrecy rate. Simulation results show that the proposed non-linear precoders outperform existing precoders in terms of BER and secrecy rate performance.
Unified Reasoning about Robustness Properties of Symbolic-Heap Separation Logic
Venue: arXiv cs.LO 2016
Year: 2016

We introduce heap automata, a formalism for automatic reasoning about robustness properties of the symbolic heap fragment of separation logic with user-defined inductive predicates. Robustness properties, such as satisfiability, reachability, and acyclicity, are important for a wide range of reasoning tasks in automated program analysis and verification based on separation logic. Previously, such properties have appeared in many places in the separation logic literature, but have not been studied in a systematic manner. In this paper, we develop an algorithmic framework based on heap automata that allows us to derive asymptotically optimal decision procedures for a wide range of robustness properties in a uniform way. We implemented a protoype of our framework and obtained promising results for all of the aforementioned robustness properties. Further, we demonstrate the applicability of heap automata beyond robustness properties. We apply our algorithmic framework to the model checking and the entailment problem for symbolic-heap separation logic.
Hybrid-DCA: A Double Asynchronous Approach for Stochastic Dual Coordinate Ascent
Venue: arXiv cs.DC 2016
Year: 2016

In prior works, stochastic dual coordinate ascent (SDCA) has been parallelized in a multi-core environment where the cores communicate through shared memory, or in a multi-processor distributed memory environment where the processors communicate through message passing. In this paper, we propose a hybrid SDCA framework for multi-core clusters, the most common high performance computing environment that consists of multiple nodes each having multiple cores and its own shared memory. We distribute data across nodes where each node solves a local problem in an asynchronous parallel fashion on its cores, and then the local updates are aggregated via an asynchronous across-node update scheme. The proposed double asynchronous method converges to a global solution for $L$-Lipschitz continuous loss functions, and at a linear convergence rate if a smooth convex loss function is used. Extensive empirical comparison has shown that our algorithm scales better than the best known shared-memory methods and runs faster than previous distributed-memory methods. Big datasets, such as one of 280 GB from the LIBSVM repository, cannot be accommodated on a single node and hence cannot be solved by a parallel algorithm. For such a dataset, our hybrid algorithm takes 30 seconds to achieve a duality gap of $10^{-6}$ on 16 nodes each using 8 cores, which is significantly faster than the best known distributed algorithms, such as CoCoA+, that take more than 300 seconds on 16 nodes.
SPiKeS: Superpixel-Keypoints Structure for Robust Visual Tracking
Venue: arXiv cs.CV 2016
Year: 2016

In visual tracking, part-based trackers are attractive since they are robust against occlusion and deformation. However, a part represented by a rectangular patch does not account for the shape of the target, while a superpixel does thanks to its boundary evidence. Nevertheless, tracking superpixels is difficult due to their lack of discriminative power. Therefore, to enable superpixels to be tracked discriminatively as object parts, we propose to enhance them with keypoints. By combining properties of these two features, we build a novel element designated as a Superpixel-Keypoints structure (SPiKeS). Being discriminative, these new object parts can be located efficiently by a simple nearest neighbor matching process. Then, in a tracking process, each match votes for the target's center to give its location. In addition, the interesting properties of our new feature allows the development of an efficient model update for more robust tracking. According to experimental results, our SPiKeS-based tracker proves to be robust in many challenging scenarios by performing favorably against the state-of-the-art.
From Ontology to Structured Applied Epistemology
Venue: arXiv cs.DL 2016
Year: 2016

Developing and organizing new knowledge is a core activity for scholars. Recently, ontologies have been introduced as an approach for organizing knowledge. However, most ontologies do not readily support the development and organization of new knowledge. By comparison, to ontology, epistemology is the study of what can be known. Aspects of epistemology include the acquisition of and justification for new knowledge. Thus, we need to coordinate ontology with epistemology. Because we are developing frameworks for capturing knowledge across several scholarly domains, we describe the work in this paper as exploring structured applied epistemology. Unlike other recent proposals for new approaches to scholarly publishing, we propose an integrated and comprehensive approach. We have explored direct representation based on the rigorous Basic Formal Ontology and in this paper, we consider how epistemology can be incorporated with that. In addition to highly-structured scientific research reports, we also consider how to develop highly-structured descriptions of historical events on which historical analyses can be based.
Representation Learning with Deconvolution for Multivariate Time Series Classification and Visualization
Venue: arXiv cs.LG 2016
Year: 2016

We propose a new model based on the deconvolutional networks and SAX discretization to learn the representation for multivariate time series. Deconvolutional networks fully exploit the advantage the powerful expressiveness of deep neural networks in the manner of unsupervised learning. We design a network structure specifically to capture the cross-channel correlation with deconvolution, forcing the pooling operation to perform the dimension reduction along each position in the individual channel. Discretization based on Symbolic Aggregate Approximation is applied on the feature vectors to further extract the bag of features. We show how this representation and bag of features helps on classification. A full comparison with the sequence distance based approach is provided to demonstrate the effectiveness of our approach on the standard datasets. We further build the Markov matrix from the discretized representation from the deconvolution to visualize the time series as complex networks, which show more class-specific statistical properties and clear structures with respect to different labels.
Learning Reporting Dynamics during Breaking News for Rumour Detection in Social Media
Venue: arXiv cs.CL 2016
Year: 2016

Breaking news leads to situations of fast-paced reporting in social media, producing all kinds of updates related to news stories, albeit with the caveat that some of those early updates tend to be rumours, i.e., information with an unverified status at the time of posting. Flagging information that is unverified can be helpful to avoid the spread of information that may turn out to be false. Detection of rumours can also feed a rumour tracking system that ultimately determines their veracity. In this paper we introduce a novel approach to rumour detection that learns from the sequential dynamics of reporting during breaking news in social media to detect rumours in new stories. Using Twitter datasets collected during five breaking news stories, we experiment with Conditional Random Fields as a sequential classifier that leverages context learnt during an event for rumour detection, which we compare with the state-of-the-art rumour detection system as well as other baselines. In contrast to existing work, our classifier does not need to observe tweets querying a piece of information to deem it a rumour, but instead we detect rumours from the tweet alone by exploiting context learnt during the event. Our classifier achieves competitive performance, beating the state-of-the-art classifier that relies on querying tweets with improved precision and recall, as well as outperforming our best baseline with nearly 40% improvement in terms of F1 score. The scale and diversity of our experiments reinforces the generalisability of our classifier.