OpenRaiser/Intern-Atlas huggingface dataset:
Byzantine Multi-Agent Optimization: Part II
Venue: arXiv cs.DC 2015
Year: 2015

In Part I of this report, we introduced a Byzantine fault-tolerant distributed optimization problem whose goal is to optimize a sum of convex (cost) functions with real-valued scalar input/ouput. In this second part, we introduce a condition-based variant of the original problem over arbitrary directed graphs. Specifically, for a given collection of $k$ input functions $h_1(x), \ldots, h_k(x)$, we consider the scenario when the local cost function stored at agent $j$, denoted by $g_j(x)$, is formed as a convex combination of the $k$ input functions $h_1(x), \ldots, h_k(x)$. The goal of this condition-based problem is to generate an output that is an optimum of $\frac{1}{k}\sum_{i=1}^k h_i(x)$. Depending on the availability of side information at each agent, two slightly different variants are considered. We show that for a given graph, the problem can indeed be solved despite the presence of faulty agents. In particular, even in the absence of side information at each agent, when adequate redundancy is available in the optima of input functions, a distributed algorithm is proposed in which each agent carries minimal state across iterations.
A linear approach for sparse coding by a two-layer neural network
Venue: arXiv cs.LG 2015
Year: 2015

Many approaches to transform classification problems from non-linear to linear by feature transformation have been recently presented in the literature. These notably include sparse coding methods and deep neural networks. However, many of these approaches require the repeated application of a learning process upon the presentation of unseen data input vectors, or else involve the use of large numbers of parameters and hyper-parameters, which must be chosen through cross-validation, thus increasing running time dramatically. In this paper, we propose and experimentally investigate a new approach for the purpose of overcoming limitations of both kinds. The proposed approach makes use of a linear auto-associative network (called SCNN) with just one hidden layer. The combination of this architecture with a specific error function to be minimized enables one to learn a linear encoder computing a sparse code which turns out to be as similar as possible to the sparse coding that one obtains by re-training the neural network. Importantly, the linearity of SCNN and the choice of the error function allow one to achieve reduced running time in the learning phase. The proposed architecture is evaluated on the basis of two standard machine learning tasks. Its performances are compared with those of recently proposed non-linear auto-associative neural networks. The overall results suggest that linear encoders can be profitably used to obtain sparse data representations in the context of machine learning problems, provided that an appropriate error function is used during the learning phase.
Cyber-Deception and Attribution in Capture-the-Flag Exercises
Venue: arXiv cs.CR 2015
Year: 2015

Attributing the culprit of a cyber-attack is widely considered one of the major technical and policy challenges of cyber-security. The lack of ground truth for an individual responsible for a given attack has limited previous studies. Here, we overcome this limitation by leveraging DEFCON capture-the-flag (CTF) exercise data where the actual ground-truth is known. In this work, we use various classification techniques to identify the culprit in a cyberattack and find that deceptive activities account for the majority of misclassified samples. We also explore several heuristics to alleviate some of the misclassification caused by deception.
Demonstration of an Aerial and Submersible Vehicle Capable of Flight and Underwater Navigation with Seamless Air-Water Transition
Venue: arXiv cs.RO 2015
Year: 2015

Bio-inspired vehicles are currently leading the way in the quest to produce a vehicle capable of flight and underwater navigation. However, a fully functional vehicle has not yet been realized. We present the first fully functional vehicle platform operating in air and underwater with seamless transition between both mediums. These unique capabilities combined with the hovering, high maneuverability and reliability of multirotor vehicles, results in a disruptive technology for both civil and military application including air/water search and rescue, inspection, repairs and survey missions among others. The invention was built on a bio-inspired locomotion force analysis that combines flight and swimming. Three main advances in the present work has allowed this invention. The first is the discovery of a seamless transition method between air and underwater. The second is the design of a multi-medium propulsion system capable of efficient operation in air and underwater. The third combines the requirements for lift and thrust for flight (for a given weight) and the requirements for thrust and neutral buoyancy (in water) for swimming. The result is a careful balance between lift, thrust, weight, and neutral buoyancy implemented in the vehicle design. A fully operational prototype demonstrated the flight, and underwater navigation capabilities as well as the rapid air/water and water/air transition.
Timing and Carrier Synchronization in Wireless Communication Systems: A Survey and Classification of Research in the Last Five Years
Venue: arXiv cs.IT 2015
Year: 2015

Timing and carrier synchronization is a fundamental requirement for any wireless communication system to work properly. Timing synchronization is the process by which a receiver node determines the correct instants of time at which to sample the incoming signal. Carrier synchronization is the process by which a receiver adapts the frequency and phase of its local carrier oscillator with those of the received signal. In this paper, we survey the literature over the last five years (2010-2014) and present a comprehensive literature review and classification of the recent research progress in achieving timing and carrier synchronization in single-input-single-output (SISO), multiple-input-multiple-output (MIMO), cooperative relaying, and multiuser/multicell interference networks. Considering both single-carrier and multi-carrier communication systems, we survey and categorise the timing and carrier synchronization techniques proposed for the different communication systems focusing on the system model assumptions for synchronization, the synchronization challenges, and the state-of-the-art synchronization solutions and their limitations. Finally, we envision some future research directions.
The Society Spectrum: Self-Regulation of Cellular Network Markets
Venue: arXiv cs.NI 2015
Year: 2015

Today's cellular telecommunications markets require continuous monitoring and intervention by regulators in order to balance the interests of various stakeholders. In order to reduce the extent of regulatory involvements in the day-to-day business of cellular operators, the present paper proposes a "self-regulating" spectrum market regime named "society spectrum". This regime provides a market-inherent and automatic self-balancing of stakeholder powers, which at the same time provides a series of coordination and fairness assurance functions that clearly distinguish it from "spectrum as a commons" solutions. The present paper will introduce the fundamental regulatory design and will elaborate on mechanisms to assure fairness among stakeholders and individuals. This work further puts the society spectrum into the context of contemporary radio access technologies and cognitive radio approaches.
A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

In two-tiered Wireless Sensor Networks (WSNs) relay node placement is one of the key factors impacting the network energy consumption and the system overhead. In this paper, a novel connectivity-aware approximation algorithm for relay node placement in WSNs is proposed to offer a major step forward in saving system overhead. Specifically, a unique Local Search Approximation Algorithm (LSAA) is introduced to solve the Relay Node Single Cover (RNSC) problem. In this proposed LSAA approach, the sensor nodes are allocated into groups and then a local Set Cover (SC) for each group is achieved by a local search algorithm. The union set of all local SCs constitutes a SC of the RNSC problem. The approximation ratio and the time complexity of the LSAA are analyzed by rigorous proof. Additionally, the LSAA approach has been extended to solve the relay node double cover problem. Then, a Relay Location Selection Algorithm (RLSA) is proposed to utilize the resulting SC from LSAA in combining RLSA with the minimum spanning tree heuristic to build the high-tier connectivity. As the RLSA searches for a nearest location to the sink node for each relay node, the high-tier network built by RLSA becomes denser than that by existing works. As a result, the number of added relay nodes for building the connectivity of the high-tier WSN can be significantly saved. Simulation results clearly demonstrate that the proposed LSAA outperforms the approaches reported in literature and the RLSA-based algorithm can noticeably save relay nodes newly deployed for the high-tier connectivity.
Shedding Light on the Asymmetric Learning Capability of AdaBoost
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we propose a different insight to analyze AdaBoost. This analysis reveals that, beyond some preconceptions, AdaBoost can be directly used as an asymmetric learning algorithm, preserving all its theoretical properties. A novel class-conditional description of AdaBoost, which models the actual asymmetric behavior of the algorithm, is presented.
Model of human collective decision-making in complex environments
Venue: arXiv cs.MA 2015
Year: 2015

A continuous-time Markov process is proposed to analyze how a group of humans solves a complex task, consisting in the search of the optimal set of decisions on a fitness landscape. Individuals change their opinions driven by two different forces: (i) the self-interest, which pushes them to increase their own fitness values, and (ii) the social interactions, which push individuals to reduce the diversity of their opinions in order to reach consensus. Results show that the performance of the group is strongly affected by the strength of social interactions and by the level of knowledge of the individuals. Increasing the strength of social interactions improves the performance of the team. However, too strong social interactions slow down the search of the optimal solution and worsen the performance of the group. In particular, we find that the threshold value of the social interaction strength, which leads to the emergence of a superior intelligence of the group, is just the critical threshold at which the consensus among the members sets in. We also prove that a moderate level of knowledge is already enough to guarantee high performance of the group in making decisions.
On the Evaluation of RDF Distribution Algorithms Implemented over Apache Spark
Venue: arXiv cs.DB 2015
Year: 2015

Querying very large RDF data sets in an efficient manner requires a sophisticated distribution strategy. Several innovative solutions have recently been proposed for optimizing data distribution with predefined query workloads. This paper presents an in-depth analysis and experimental comparison of five representative and complementary distribution approaches. For achieving fair experimental results, we are using Apache Spark as a common parallel computing framework by rewriting the concerned algorithms using the Spark API. Spark provides guarantees in terms of fault tolerance, high availability and scalability which are essential in such systems. Our different implementations aim to highlight the fundamental implementation-independent characteristics of each approach in terms of data preparation, load balancing, data replication and to some extent to query answering cost and performance. The presented measures are obtained by testing each system on one synthetic and one real-world data set over query workloads with differing characteristics and different partitioning constraints.
Neural Network Classifiers for Natural Food Products
Venue: arXiv cs.CV 2015
Year: 2015

Two cheap, off-the-shelf machine vision systems (MVS), each using an artificial neural network (ANN) as classifier, were developed, improved and evaluated to automate the classification of tomato ripeness and acceptability of eggs, respectively. Six thousand color images of human-graded tomatoes and 750 images of human-graded eggs were used to train, test, and validate several multi-layered ANNs. The ANNs output the corresponding grade of the produce by accepting as inputs the spectral patterns of the background-less image. In both MVS, the ANN with the highest validation rate was automatically chosen by a heuristic and its performance compared to that of the human graders'. Using the validation set, the MVS correctly graded 97.00\% and 86.00\% of the tomato and egg data, respectively. The human grader's, however, were measured to perform at a daily average of 92.65\% and 72.67\% for tomato and egg grading, respectively. This results show that an ANN-based MVS is a potential alternative to manual grading.
Well-Formed Separator Sequences, with an Application to Hypergraph Drawing
Venue: arXiv cs.DM 2015
Year: 2015

Given a hypergraph $H$, the Planar Support problem asks whether there is a planar graph $G$ on the same vertex set as $H$ such that each hyperedge induces a connected subgraph of $G$. Planar Support is motivated by applications in graph drawing and data visualization. We show that Planar Support is fixed-parameter tractable when parameterized by the number of hyperedges in the input hypergraph and the outerplanarity number of the sought planar graph. To this end, we develop novel structural results for $r$-outerplanar triangulated disks, showing that they admit sequences of separators with structural properties enabling data reduction. This allows us to obtain a problem kernel for Planar Support, thus showing its fixed-parameter tractability.
Lustre, Hadoop, Accumulo
Venue: arXiv cs.DC 2015
Year: 2015

Data processing systems impose multiple views on data as it is processed by the system. These views include spreadsheets, databases, matrices, and graphs. There are a wide variety of technologies that can be used to store and process data through these different steps. The Lustre parallel file system, the Hadoop distributed file system, and the Accumulo database are all designed to address the largest and the most challenging data storage problems. There have been many ad-hoc comparisons of these technologies. This paper describes the foundational principles of each technology, provides simple models for assessing their capabilities, and compares the various technologies on a hypothetical common cluster. These comparisons indicate that Lustre provides 2x more storage capacity, is less likely to loose data during 3 simultaneous drive failures, and provides higher bandwidth on general purpose workloads. Hadoop can provide 4x greater read bandwidth on special purpose workloads. Accumulo provides 10,000x lower latency on random lookups than either Lustre or Hadoop but Accumulo's bulk bandwidth is 10x less. Significant recent work has been done to enable mix-and-match solutions that allow Lustre, Hadoop, and Accumulo to be combined in different ways.
Learning Structured Ordinal Measures for Video based Face Recognition
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a structured ordinal measure method for video-based face recognition that simultaneously learns ordinal filters and structured ordinal features. The problem is posed as a non-convex integer program problem that includes two parts. The first part learns stable ordinal filters to project video data into a large-margin ordinal space. The second seeks self-correcting and discrete codes by balancing the projected data and a rank-one ordinal matrix in a structured low-rank way. Unsupervised and supervised structures are considered for the ordinal matrix. In addition, as a complement to hierarchical structures, deep feature representations are integrated into our method to enhance coding stability. An alternating minimization method is employed to handle the discrete and low-rank constraints, yielding high-quality codes that capture prior structures well. Experimental results on three commonly used face video databases show that our method with a simple voting classifier can achieve state-of-the-art recognition rates using fewer features and samples.
Towards Effective Codebookless Model for Image Classification
Venue: arXiv cs.CV 2015
Year: 2015

The bag-of-features (BoF) model for image classification has been thoroughly studied over the last decade. Different from the widely used BoF methods which modeled images with a pre-trained codebook, the alternative codebook free image modeling method, which we call Codebookless Model (CLM), attracted little attention. In this paper, we present an effective CLM that represents an image with a single Gaussian for classification. By embedding Gaussian manifold into a vector space, we show that the simple incorporation of our CLM into a linear classifier achieves very competitive accuracy compared with state-of-the-art BoF methods (e.g., Fisher Vector). Since our CLM lies in a high dimensional Riemannian manifold, we further propose a joint learning method of low-rank transformation with support vector machine (SVM) classifier on the Gaussian manifold, in order to reduce computational and storage cost. To study and alleviate the side effect of background clutter on our CLM, we also present a simple yet effective partial background removal method based on saliency detection. Experiments are extensively conducted on eight widely used databases to demonstrate the effectiveness and efficiency of our CLM method.
Place Categorization and Semantic Mapping on a Mobile Robot
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we focus on the challenging problem of place categorization and semantic mapping on a robot without environment-specific training. Motivated by their ongoing success in various visual recognition tasks, we build our system upon a state-of-the-art convolutional network. We overcome its closed-set limitations by complementing the network with a series of one-vs-all classifiers that can learn to recognize new semantic classes online. Prior domain knowledge is incorporated by embedding the classification system into a Bayesian filter framework that also ensures temporal coherence. We evaluate the classification accuracy of the system on a robot that maps a variety of places on our campus in real-time. We show how semantic information can boost robotic object detection performance and how the semantic map can be used to modulate the robot's behaviour during navigation tasks. The system is made available to the community as a ROS module.
Data Mining of Causal Relations from Text: Analysing Maritime Accident Investigation Reports
Venue: arXiv cs.IR 2015
Year: 2015

Text mining is a process of extracting information of interest from text. Such a method includes techniques from various areas such as Information Retrieval (IR), Natural Language Processing (NLP), and Information Extraction (IE). In this study, text mining methods are applied to extract causal relations from maritime accident investigation reports collected from the Marine Accident Investigation Branch (MAIB). These causal relations provide information on various mechanisms behind accidents, including human and organizational factors relating to the accident. The objective of this study is to facilitate the analysis of the maritime accident investigation reports, by means of extracting contributory causes with more feasibility. A careful investigation of contributory causes from the reports provide opportunity to improve safety in future. Two methods have been employed in this study to extract the causal relations. They are 1) Pattern classification method and 2) Connectives method. The earlier one uses naive Bayes and Support Vector Machines (SVM) as classifiers. The latter simply searches for the words connecting cause and effect in sentences. The causal patterns extracted using these two methods are compared to the manual (human expert) extraction. The pattern classification method showed a fair and sensible performance with F-measure(average) = 65% when compared to connectives method with F-measure(average) = 58%. This study is an evidence, that text mining methods could be employed in extracting causal relations from marine accident investigation reports.
Towards a Security Lifecycle Model against Social Engineering Attacks: SLM-SEA
Venue: arXiv cs.CR 2015
Year: 2015

This research considers the impact of social engineering security attacks which are noted as taking opportunities for critically exploiting user awareness and behavior. The research proposes in this respect a managerial method in an attempt to enhance or even ensure protection. The aim of this study is to construct a security lifecycle model against these eventualities and to analyze the test results that have been carried out within the context of the Turkish public sector. The main objective of the study is to determine why employees shared sensitive information by stating fallacies and related amendments through interviews and thus to understand user actions when they are face to face with a real social engineering attack. The research findings demonstrate that employees in Turkish public organizations are not sufficiently aware of information security and they generally ignore critically important security procedures. This represents an important illustration of the increasing need for further generalized user awareness and responsibilities where individuals and not simply software form a critical element of the security protection portfolio.
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Venue: arXiv cs.DS 2015
Year: 2015

The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called "islands of tractability." A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language, whereas a constraint language is conservative if it contains all unary relations. This paper addresses the general limit of the mentioned tractability results for CSP and #CSP, that they only apply to instances where all constraints belong to a single tractable language (in general, the union of two tractable languages isn't tractable). We show that we can overcome this limitation as long as we keep some control of how constraints over the various considered tractable languages interact with each other. For this purpose we utilize the notion of a \emph{strong backdoor} of a CSP instance, as introduced by Williams et al. (IJCAI 2003), which is a set of variables that when instantiated moves the instance to an island of tractability, i.e., to a tractable class of instances. In this paper, we consider strong backdoors into \emph{scattered classes}, consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Our main result is an algorithm that, given a CSP instance with $n$ variables, finds in time $f(k)n^{O(1)}$ a strong backdoor into a scattered class (associated with a list of finite conservative constraint languages) of size $k$ or correctly decides that there isn't such a backdoor.