OpenRaiser/Intern-Atlas huggingface dataset:
Improved Algorithms for Exact and Approximate Boolean Matrix Decomposition
Venue: arXiv cs.DM 2015
Year: 2015

An arbitrary $m\times n$ Boolean matrix $M$ can be decomposed {\em exactly} as $M =U\circ V$, where $U$ (resp. $V$) is an $m\times k$ (resp. $k\times n$) Boolean matrix and $\circ$ denotes the Boolean matrix multiplication operator. We first prove an exact formula for the Boolean matrix $J$ such that $M =M\circ J^T$ holds, where $J$ is maximal in the sense that if any 0 element in $J$ is changed to a 1 then this equality no longer holds. Since minimizing $k$ is NP-hard, we propose two heuristic algorithms for finding suboptimal but good decomposition. We measure the performance (in minimizing $k$) of our algorithms on several real datasets in comparison with other representative heuristic algorithms for Boolean matrix decomposition (BMD). The results on some popular benchmark datasets demonstrate that one of our proposed algorithms performs as well or better on most of them. Our algorithms have a number of other advantages: They are based on exact mathematical formula, which can be interpreted intuitively. They can be used for approximation as well with competitive "coverage." Last but not least, they also run very fast. Due to interpretability issues in data mining, we impose the condition, called the "column use condition," that the columns of the factor matrix $U$ must form a subset of the columns of $M$.
The Utility of Abstaining in Binary Classification
Venue: arXiv cs.LG 2015
Year: 2015

We explore the problem of binary classification in machine learning, with a twist - the classifier is allowed to abstain on any datum, professing ignorance about the true class label without committing to any prediction. This is directly motivated by applications like medical diagnosis and fraud risk assessment, in which incorrect predictions have potentially calamitous consequences. We focus on a recent spate of theoretically driven work in this area that characterizes how allowing abstentions can lead to fewer errors in very general settings. Two areas are highlighted: the surprising possibility of zero-error learning, and the fundamental tradeoff between predicting sufficiently often and avoiding incorrect predictions. We review efficient algorithms with provable guarantees for each of these areas. We also discuss connections to other scenarios, notably active learning, as they suggest promising directions of further inquiry in this emerging field.
Design of portable power consumption measuring system for green computing needs
Venue: arXiv cs.OH 2015
Year: 2015

The article presents the design of a digital power measurement device intended for the green IT. Article comprises: use case analysis, accuracy and precision measurements and real life test of apache web server as exemplary application.
Thirty eight things to do with live slime mould
Venue: arXiv cs.ET 2015
Year: 2015

Slime mould \emph{Physarum polycephalum} is a large single cell capable for distributed sensing, concurrent information processing, parallel computation and decentralised actuation. The ease of culturing and experimenting with Physarum makes this slime mould an ideal substrate for real-world implementations of unconventional sensing and computing devices. In the last decade the Physarum became a swiss knife of the unconventional computing: give the slime mould a problem it will solve it. We provide a concise summary of what exact computing and sensing operations are implemented with live slime mould. The Physarum devices range from morphological processors for computational geometry to experimental archeology tools, from self-routing wires to memristors, from devices approximating a shortest path to analog physical models of space exploration.
Quantum Resistant Random Linear Code Based Public Key Encryption Scheme RLCE
Venue: arXiv cs.CR 2015
Year: 2015

Lattice based encryption schemes and linear code based encryption schemes have received extensive attention in recent years since they have been considered as post-quantum candidate encryption schemes. Though LLL reduction algorithm has been one of the major cryptanalysis techniques for lattice based cryptographic systems, key recovery cryptanalysis techniques for linear code based cryptographic systems are generally scheme specific. In recent years, several important techniques such as Sidelnikov-Shestakov attack, filtration attacks, and algebraic attacks have been developed to crypt-analyze linear code based encryption schemes. Though most of these cryptanalysis techniques are relatively new, they prove to be very powerful and many systems have been broken using them. Thus it is important to design linear code based cryptographic systems that are immune against these attacks. This paper proposes linear code based encryption scheme RLCE which shares many characteristics with random linear codes. Our analysis shows that the scheme RLCE is secure against existing attacks and we hope that the security of the RLCE scheme is equivalent to the hardness of decoding random linear codes. Example parameters for different security levels are recommended for the scheme RLCE.
Security Metrics in Industrial Control Systems
Venue: arXiv cs.CR 2015
Year: 2015

Risk is the best known and perhaps the best studied example within a much broader class of cyber security metrics. However, risk is not the only possible cyber security metric. Other metrics such as resilience can exist and could be potentially very valuable to defenders of ICS systems. Often, metrics are defined as measurable properties of a system that quantify the degree to which objectives of the system are achieved. Metrics can provide cyber defenders of an ICS with critical insights regarding the system. Metrics are generally acquired by analyzing relevant attributes of that system. In terms of cyber security metrics, ICSs tend to have unique features: in many cases, these systems are older technologies that were designed for functionality rather than security. They are also extremely diverse systems that have different requirements and objectives. Therefore, metrics for ICSs must be tailored to a diverse group of systems with many features and perform many different functions. In this chapter, we first outline the general theory of performance metrics, and highlight examples from the cyber security domain and ICS in particular. We then focus on a particular example of a class of metrics that is different from the one we have considered in earlier chapters. Instead of risk, here we consider metrics of resilience. Resilience is defined by the National Academy of Sciences (2012) as the ability to prepare and plan for, absorb, recover from, or more successfully adapt to actual or potential adverse events. This chapter presents two approaches for the generation of metrics based on the concept of resilience using a matrix-based approach and a network-based approach. Finally, a discussion of the benefits and drawbacks of different methods is presented along with a process and tips intended to aid in devising effective metrics.
Conditional probability generation methods for high reliability effects-based decision making
Venue: arXiv cs.AI 2015
Year: 2015

Decision making is often based on Bayesian networks. The building blocks for Bayesian networks are its conditional probability tables (CPTs). These tables are obtained by parameter estimation methods, or they are elicited from subject matter experts (SME). Some of these knowledge representations are insufficient approximations. Using knowledge fusion of cause and effect observations lead to better predictive decisions. We propose three new methods to generate CPTs, which even work when only soft evidence is provided. The first two are novel ways of mapping conditional expectations to the probability space. The third is a column extraction method, which obtains CPTs from nonlinear functions such as the multinomial logistic regression. Case studies on military effects and burnt forest desertification have demonstrated that so derived CPTs have highly reliable predictive power, including superiority over the CPTs obtained from SMEs. In this context, new quality measures for determining the goodness of a CPT and for comparing CPTs with each other have been introduced. The predictive power and enhanced reliability of decision making based on the novel CPT generation methods presented in this paper have been confirmed and validated within the context of the case studies.
Tight Bounds for Approximate Carathéodory and Beyond
Venue: arXiv cs.DS 2015
Year: 2015

We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $ε$ in $\ell_p$ norm by a convex combination of only $O\left(D^2 p/ε^2\right)$ vertices of the polytope for $p \geq 2$. We also show that this bound is tight, using an argument based on anti-concentration for the binomial distribution. Along the way of establishing the upper bound, we develop a technique for minimizing norms over convex sets with complicated geometry; this is achieved by running Mirror Descent on a dual convex function obtained via Sion's Theorem. As simple extensions of our method, we then provide new algorithms for submodular function minimization and SVM training. For submodular function minimization we obtain a simplification and (provable) speed-up over Wolfe's algorithm, the method commonly found to be the fastest in practice. For SVM training, we obtain $O(1/ε^2)$ convergence for arbitrary kernels; each iteration only requires matrix-vector operations involving the kernel matrix, so we overcome the obstacle of having to explicitly store the kernel or compute its Cholesky factorization.
Robust Scene Text Recognition Using Sparse Coding based Features
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose an effective scene text recognition method using sparse coding based features, called Histograms of Sparse Codes (HSC) features. For character detection, we use the HSC features instead of using the Histograms of Oriented Gradients (HOG) features. The HSC features are extracted by computing sparse codes with dictionaries that are learned from data using K-SVD, and aggregating per-pixel sparse codes to form local histograms. For word recognition, we integrate multiple cues including character detection scores and geometric contexts in an objective function. The final recognition results are obtained by searching for the words which correspond to the maximum value of the objective function. The parameters in the objective function are learned using the Minimum Classification Error (MCE) training method. Experiments on several challenging datasets demonstrate that the proposed HSC-based scene text recognition method outperforms HOG-based methods significantly and outperforms most state-of-the-art methods.
Interactive Discovery of Coordinated Relationship Chains with Maximum Entropy Models
Venue: arXiv cs.DB 2015
Year: 2015

Modern visual analytic tools promote human-in-the-loop analysis but are limited in their ability to direct the user toward interesting and promising directions of study. This problem is especially acute when the analysis task is exploratory in nature, e.g., the discovery of potentially coordinated relationships in massive text datasets. Such tasks are very common in domains like intelligence analysis and security forensics where the goal is to uncover surprising coalitions bridging multiple types of relations. We introduce new maximum entropy models to discover surprising chains of relationships leveraging count data about entity occurrences in documents. These models are embedded in a visual analytic system called MERCER that treats relationship bundles as first class objects and directs the user toward promising lines of inquiry. We demonstrate how user input can judiciously direct analysis toward valid conclusions whereas a purely algorithmic approach could be led astray. Experimental results on both synthetic and real datasets from the intelligence community are presented.
Improving Style Similarity Metrics of 3D Shapes
Venue: arXiv cs.GR 2015
Year: 2015

The idea of style similarity metrics has been recently developed for various media types such as 2D clip art and 3D shapes. We explore this style metric problem and improve existing style similarity metrics of 3D shapes in four novel ways. First, we consider the color and texture of 3D shapes which are important properties that have not been previously considered. Second, we explore the effect of clustering a dataset of 3D models by comparing between style metrics for a single object type and style metrics that combine clusters of object types. Third, we explore the idea of user-guided learning for this problem. Fourth, we introduce an iterative approach that can learn a metric from a general set of 3D models. We demonstrate these contributions with various classes of 3D shapes and with applications such as style-based similarity search and scene composition.
Modelling and Verifying the AODV Routing Protocol
Venue: arXiv cs.NI 2015
Year: 2015

This paper presents a formal specification of the Ad hoc On-Demand Distance Vector (AODV) routing protocol using AWN (Algebra for Wireless Networks), a recent process algebra which has been tailored for the modelling of Mobile Ad Hoc Networks and Wireless Mesh Network protocols. Our formalisation models the exact details of the core functionality of AODV, such as route discovery, route maintenance and error handling. We demonstrate how AWN can be used to reason about critical protocol properties by providing detailed proofs of loop freedom and route correctness.
New Designs of Universal Reversible Gate Library
Venue: arXiv cs.ET 2015
Year: 2015

We present new algorithms to synthesize exact universal reversible gate library for various types of gates and costs. We use the powerful algebraic software GAP for implementation and examination of our algorithms and the reversible logic synthesis problems have been reduced to group theory problems. It is shown that minimization of arbitrary cost functions of gates and orders of magnitude are faster than its previously counterparts for reversible logic synthesis. Experimental results show that a significant improvement over the previously proposed synthesis algorithm is obtained compared with the existing approaches to reversible logic synthesis.
The Bounded Edge Coloring Problem and Offline Crossbar Scheduling
Venue: arXiv cs.DS 2015
Year: 2015

This paper introduces a variant of the classical edge coloring problem in graphs that can be applied to an offline scheduling problem for crossbar switches. We show that the problem is NP-complete, develop three lower bounds bounds on the optimal solution value and evaluate the performance of several approximation algorithms, both analytically and experimentally. We show how to approximate an optimal solution with a worst-case performance ratio of $3/2$ and our experimental results demonstrate that the best algorithms produce results that very closely track a lower bound.
Selecting Near-Optimal Learners via Incremental Data Allocation
Venue: arXiv cs.LG 2015
Year: 2015

We study a novel machine learning (ML) problem setting of sequentially allocating small subsets of training data amongst a large set of classifiers. The goal is to select a classifier that will give near-optimal accuracy when trained on all data, while also minimizing the cost of misallocated samples. This is motivated by large modern datasets and ML toolkits with many combinations of learning algorithms and hyper-parameters. Inspired by the principle of "optimism under uncertainty," we propose an innovative strategy, Data Allocation using Upper Bounds (DAUB), which robustly achieves these objectives across a variety of real-world datasets. We further develop substantial theoretical support for DAUB in an idealized setting where the expected accuracy of a classifier trained on $n$ samples can be known exactly. Under these conditions we establish a rigorous sub-linear bound on the regret of the approach (in terms of misallocated data), as well as a rigorous bound on suboptimality of the selected classifier. Our accuracy estimates using real-world datasets only entail mild violations of the theoretical scenario, suggesting that the practical behavior of DAUB is likely to approach the idealized behavior.
Supporting Multi-hop Device-to-Device Networks Through WiFi Direct Multi-group Networking
Venue: arXiv cs.NI 2015
Year: 2015

With the increasing availability of mobile devices that natively support Device-to-Device (D2D) communication protocols, we are presented with a unique opportunity to realize large scale ad hoc wireless networks. Recently, a novel D2D protocol named WiFi Direct has been proposed and standardized by the WiFi Alliance with the objective of facilitating the interconnection of nearby devices. However, WiFi Direct has been designed following a client-server hierarchical architecture, where a single device manages all the communications within a group of devices. In this paper, we propose and analyze different solutions for supporting the communications between multiple WiFi Direct groups using Android OS devices. By describing the WiFi Direct standard and the limitations of the current implementation of the Android WiFi Direct framework, we present possible solutions to interconnect different groups to create multi-hop ad hoc networks. Experimental results show that our proposed approaches are feasible with different overhead in terms of energy consumption and delay at the gateway node. Additionally, our experimental results demonstrate the superiority of techniques that exploit the device ability to maintain simultaneous physical connections to multiple groups.
Benders Decomposition for the Design of a Hub and Shuttle Public Transit System
Venue: arXiv cs.AI 2015
Year: 2015

The BusPlus project aims at improving the off-peak hours public transit service in Canberra, Australia. To address the difficulty of covering a large geographic area, BusPlus proposes a hub and shuttle model consisting of a combination of a few high-frequency bus routes between key hubs and a large number of shuttles that bring passengers from their origin to the closest hub and take them from their last bus stop to their destination. This paper focuses on the design of bus network and proposes an efficient solving method to this multimodal network design problem based on the Benders decomposition method. Starting from a MIP formulation of the problem, the paper presents a Benders decomposition approach using dedicated solution techniques for solving independent sub-problems, Pareto optimal cuts, cut bundling, and core point update. Computational results on real-world data from Canberra's public transit system justify the design choices and show that the approach outperforms the MIP formulation by two orders of magnitude. Moreover, the results show that the hub and shuttle model may decrease transit time by a factor of 2, while staying within the costs of the existing transit system.
Crowds for Clouds: Recent Trends in Humanities Research Infrastructures
Venue: arXiv cs.OH 2015
Year: 2015

Humanities have convincingly argued that they need transnational research opportunities and through the digital transformation of their disciplines also have the means to proceed with it on an up to now unknown scale. The digital transformation of research and its resources means that many of the artifacts, documents, materials, etc. that interest humanities research can now be combined in new and innovative ways. Due to the digital transformations, (big) data and information have become central to the study of culture and society. Humanities research infrastructures manage, organise and distribute this kind of information and many more data objects as they becomes relevant for social and cultural research.
A Fuzzy MLP Approach for Non-linear Pattern Classification
Venue: arXiv cs.NE 2015
Year: 2015

In case of decision making problems, classification of pattern is a complex and crucial task. Pattern classification using multilayer perceptron (MLP) trained with back propagation learning becomes much complex with increase in number of layers, number of nodes and number of epochs and ultimate increases computational time [31]. In this paper, an attempt has been made to use fuzzy MLP and its learning algorithm for pattern classification. The time and space complexities of the algorithm have been analyzed. A training performance comparison has been carried out between MLP and the proposed fuzzy-MLP model by considering six cases. Results are noted against different learning rates ranging from 0 to 1. A new performance evaluation factor 'convergence gain' has been introduced. It is observed that the number of epochs drastically reduced and performance increased compared to MLP. The average and minimum gain has been found to be 93% and 75% respectively. The best gain is found to be 95% and is obtained by setting the learning rate to 0.55.
A Low Complexity VLSI Architecture for Multi-Focus Image Fusion in DCT Domain
Venue: arXiv cs.CV 2015
Year: 2015

Due to the confined focal length of optical sensors, focusing all objects in a scene with a single sensor is a difficult task. To handle such a situation, image fusion methods are used in multi-focus environment. Discrete Cosine Transform (DCT) is a widely used image compression transform, image fusion in DCT domain is an efficient method. This paper presents a low complexity approach for multi-focus image fusion and its VLSI implementation using DCT. The proposed method is evaluated using reference/non-reference fusion measure criteria and the obtained results asserts it's effectiveness. The maximum synthesized frequency on FPGA is found to be 221 MHz and consumes 42% of FPGA resources. The proposed method consumes very less power and can process 4K resolution images at the rate of 60 frames per second which makes the hardware suitable for handheld portable devices such as camera module and wireless image sensors.
Contribution to the Formal Specification and Verification of a Multi-Agent Robotic System
Venue: arXiv cs.SE 2015
Year: 2015

It is important to have multi-agent robotic system specifications that ensure correctness properties of safety and liveness. As these systems have concurrency, and often have dynamic environment, the formal specification and verification of these systems along with step-wise refinement from abstract to concrete concepts play a major role in system correctness. Formal verification is used for exhaustive investigation of the system space thus ensuring that undetected failures in the behavior are excluded. We construct the system incrementally from subcomponents, based on software architecture. The challenge is to develop a safe multi-agent robotic system, more specifically to ensure the correctness properties of safety and liveness. Formal specifications based on model-checking are flexible, have a concrete syntax, and play vital role in correctness of a multi-agent robotic system. To formally verify safety and liveness of such systems is important because they have high concurrency and in most of the cases have dynamic environment. We have considered a case-study of a multi-agent robotic system for the transport of stock between storehouses to exemplify our formal approach. Our proposed development approach allows for formal verification during specification definition. The development process has been classified in to four major phases of requirement specifications, verification specifications, architecture specifications and implementation.