OpenRaiser/Intern-Atlas huggingface dataset:
Predicting Enemy's Actions Improves Commander Decision-Making
Venue: arXiv cs.AI 2016
Year: 2016

The Defense Advanced Research Projects Agency (DARPA) Real-time Adversarial Intelligence and Decision-making (RAID) program is investigating the feasibility of "reading the mind of the enemy" - to estimate and anticipate, in real-time, the enemy's likely goals, deceptions, actions, movements and positions. This program focuses specifically on urban battles at echelons of battalion and below. The RAID program leverages approximate game-theoretic and deception-sensitive algorithms to provide real-time enemy estimates to a tactical commander. A key hypothesis of the program is that these predictions and recommendations will make the commander more effective, i.e. he should be able to achieve his operational goals safer, faster, and more efficiently. Realistic experimentation and evaluation drive the development process using human-in-the-loop wargames to compare humans and the RAID system. Two experiments were conducted in 2005 as part of Phase I to determine if the RAID software could make predictions and recommendations as effectively and accurately as a 4-person experienced staff. This report discusses the intriguing and encouraging results of these first two experiments conducted by the RAID program. It also provides details about the experiment environment and methodology that were used to demonstrate and prove the research goals.
Can DMD obtain a Scene Background in Color?
Venue: arXiv cs.CV 2016
Year: 2016

A background model describes a scene without any foreground objects and has a number of applications, ranging from video surveillance to computational photography. Recent studies have introduced the method of Dynamic Mode Decomposition (DMD) for robustly separating video frames into a background model and foreground components. While the method introduced operates by converting color images to grayscale, we in this study propose a technique to obtain the background model in the color domain. The effectiveness of our technique is demonstrated using a publicly available Scene Background Initialisation (SBI) dataset. Our results both qualitatively and quantitatively show that DMD can successfully obtain a colored background model.
On the Impact of a Single Edge on the Network Coding Capacity
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $δ$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $δ$ cannot change the capacity region of the network by more than $δ$ in each dimension. In this paper, we extend this result to the case of multi-source, multi-sink networks for some special network topologies.
A probabilistic patch based image representation using Conditional Random Field model for image classification
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we proposed an ordered patch based method using Conditional Random Field (CRF) in order to encode local properties and their spatial relationship in images to address texture classification, face recognition, and scene classification problems. Typical image classification approaches work without considering spatial causality among distinctive properties of an image for image representation in feature space. In this method first, each image is encoded as a sequence of ordered patches, including local properties. Second, the sequence of these ordered patches is modeled as a probabilistic feature vector by CRF to model spatial relationship of these local properties. And finally, image classification is performed on such probabilistic image representation. Experimental results on several standard image datasets indicate that proposed method outperforms some of existing image classification methods.
Nonasymptotic coding-rate bounds for binary erasure channels with feedback
Venue: arXiv cs.IT 2016
Year: 2016

We present nonasymptotic achievability and converse bounds on the maximum coding rate (for a fixed average error probability and a fixed average blocklength) of variable-length full-feedback (VLF) and variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC). For the VLF setup, the achievability bound relies on a scheme that maps each message onto a variable-length Huffman codeword and then repeats each bit of the codeword until it is received correctly. The converse bound is inspired by the meta-converse framework by Polyanskiy, Poor, and Verdú (2010) and relies on binary sequential hypothesis testing. For the case of zero error probability, our achievability and converse bounds match. For the VLSF case, we provide achievability bounds that exploit the following feature of BEC: the decoder can assess the correctness of its estimate by verifying whether the chosen codeword is the only one that is compatible with the erasure pattern. One of these bounds is obtained by analyzing the performance of a variable-length extension of random linear fountain codes. The gap between the VLSF achievability and the VLF converse bound, when number of messages is small, is significant: $23\%$ for 8 messages on a BEC with erasure probability $0.5.$ The absence of a tight VLSF converse bound does not allow us to assess whether this gap is fundamental.
How to Succeed in Crowdfunding: a Long-Term Study in Kickstarter
Venue: arXiv cs.SI 2016
Year: 2016

Crowdfunding platforms have become important sites where people can create projects to seek funds toward turning their ideas into products, and back someone else's projects. As news media have reported successfully funded projects (e.g., Pebble Time, Coolest Cooler), more people have joined crowdfunding platforms and launched projects. But in spite of rapid growth of the number of users and projects, a project success rate at large has been decreasing because of launching projects without enough preparation and experience. Little is known about what reactions project creators made (e.g., giving up or making the failed projects better) when projects failed, and what types of successful projects we can find. To solve these problems, in this manuscript we (i) collect the largest datasets from Kickstarter, consisting of all project profiles, corresponding user profiles, projects' temporal data and users' social media information; (ii) analyze characteristics of successful projects, behaviors of users and understand dynamics of the crowdfunding platform; (iii) propose novel statistical approaches to predict whether a project will be successful and a range of expected pledged money of the project; (iv) develop predictive models and evaluate performance of the models; (v) analyze what reactions project creators had when project failed, and if they did not give up, how they made the failed projects successful; and (vi) cluster successful projects by their evolutional patterns of pledged money toward understanding what efforts project creators should make in order to get more pledged money. Our experimental results show that the predictive models can effectively predict project success and a range of expected pledged money.
How to Boost the Throughput of HARQ with Off-the-Shelf Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we propose a coding strategy designed to enhance the throughput of hybrid ARQ (HARQ) transmissions over i.i.d. block-fading channels with the channel state information (CSI) unknown at the transmitter. We use a joint packet coding where the same channel block is logically shared among many packets. To reduce the complexity, we use a two-layer coding where, first, packets are first coded by the binary compressing encoders, and the results are then passed to the conventional channel encoder. We show how to optimize the compression rates on the basis of the empirical error-rate curves. We also discuss how the parameters of the practical turbo-codes may be modified to take advantage of the proposed HARQ scheme. Finally, simple and pragmatic rate adaptation strategies are developed. In numerical examples, our scheme is compared to the conventional incremental redundancy HARQ (IR-HARQ), and it yields a notable gain of 1-2 dB in the region of high throughput, where HARQ fails to provide any improvement.
Evaluation of TRANSFoRm Mobile eHealth Solution for Remote Patient Monitoring during Clinical Trials
Venue: arXiv cs.HC 2016
Year: 2016

Today, in the digital age, the mobile devices are more and more used to aid people in the struggle to improve or maintain their health. In this paper, the mobile eHealth solution for remote patient monitoring during clinical trials is presented, together with the outcomes of quantitative and qualitative performance evaluation. The evaluation is a third step to improve the quality of the application after earlier Good Clinical Practice certification and validation with the participation of 10 patients and three general practitioners. This time, the focus was on the usability which was evaluated by the seventeen participants divided into three age groups (18-28, 29-50, and 50+). The results, from recorded sessions and the eye tracking, show that there is no difference in performance between the first group and the second group, while for the third group the performance was worse, however, it was still good enough to complete task within reasonable time.
Variable-to-Fixed Length Homophonic Coding with a Modified Shannon-Fano-Elias Code
Venue: arXiv cs.IT 2016
Year: 2016

Homophonic coding is a framework to reversibly convert a message into a sequence with some target distribution. This is a promising tool to generate a codeword with a biased code-symbol distribution, which is required for capacity-achieving communication by asymmetric channels. It is known that asymptotically optimal homophonic coding can be realized by a Fixed-to-Variable (FV) length code using an interval algorithm similar to a random number generator. However, FV codes are not preferable as a component of channel codes since a decoding error propagates to all subsequent codewords. As a solution for this problem an asymptotically optimal Variable-to-Fixed (VF) length homophonic code, dual Shannon-Fano-Elias-Gray (dual SFEG) code, is proposed in this paper. This code can be interpreted as a dual of a modified Shannon-Fano-Elias (SFE) code based on Gray code. It is also shown as a by-product that the modified SFE code, named SFEG code, achieves a better coding rate than the original SFE code in lossless source coding.
A Search Algorithm for Simplicial Complexes
Venue: arXiv cs.DM 2016
Year: 2016

We present the `Basic S*' algorithm for computing shortest path through a metric simplicial complex. In particular, given a metric graph, $G$, which is constructed as a discrete representation of an underlying configuration space (a larger "continuous" space/manifold typically of dimension greater than one), we consider the Rips complex, $\mathcal{R}(G)$, associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is significantly different from the metric of the configuration space itself. We remedy this problem using the simplicial complex representation. Our algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length function, $d:E\rightarrow \mathbb{R}_+$, as inputs, and no global information such as an embedding or a global coordinate chart is required. The complexity of the Basic S* algorithm is comparable to that of Dijkstra's search, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space significantly more closely.
Incremental $2$-Edge-Connectivity in Directed Graphs
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we initiate the study of the dynamic maintenance of $2$-edge-connectivity relationships in directed graphs. We present an algorithm that can update the $2$-edge-connected blocks of a directed graph with $n$ vertices through a sequence of $m$ edge insertions in a total of $O(mn)$ time. After each insertion, we can answer the following queries in asymptotically optimal time: (i) Test in constant time if two query vertices $v$ and $w$ are $2$-edge-connected. Moreover, if $v$ and $w$ are not $2$-edge-connected, we can produce in constant time a "witness" of this property, by exhibiting an edge that is contained in all paths from $v$ to $w$ or in all paths from $w$ to $v$. (ii) Report in $O(n)$ time all the $2$-edge-connected blocks of $G$. To the best of our knowledge, this is the first dynamic algorithm for $2$-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.
On Wireless Energy and Information Transfer in Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the outage probability and the throughput of relay networks with wireless information and energy transfer where the relays harvest energy from the transmitted radio-frequency signal of the source. Considering different power consumption models, we derive the outage probability for both adaptive and non-adaptive power allocations at the relay. With a total energy consumption constraint at the source, we provide closed-form expressions for the optimal time sharing and power allocation between the source energy and information transfer signals as well as the optimal relay positioning such that the outage probability is minimized. Finally, we extend our analysis to multi-relay networks. We show that with perfect channel state information (CSI) available at the relays and $N$ relays the opportunistic relaying scheme achieves diversity order of $\frac{N+1}{2}$. Also, we analyze the opportunistic relaying with partial CSI where either the source-relay or the relay-destination CSI is provided at its corresponding transmit terminal, and prove that the relay selection based on the source-relay CSI outperforms the relay selection based on the relay-destination CSI, in terms of outage probability. The analytical and simulation results demonstrate the efficiency of wireless energy and information transfer systems in different conditions.
Coherence Disparity in Broadcast and Multiple Access Channels
Venue: arXiv cs.IT 2016
Year: 2016

Individual links in a wireless network may experience unequal fading coherence times due to differences in mobility or scattering environment, a practical scenario where the fundamental limits of communication have been mostly unknown. This paper studies broadcast and multiple access channels where multiple receivers experience unequal fading block lengths, and channel state information (CSI) is not available at the transmitter(s), or for free at any receiver. In other words, the cost of acquiring CSI at the receiver is fully accounted for in the degrees of freedom. In the broadcast channel, the method of product superposition is employed to find the achievable degrees of freedom. We start with unequal coherence intervals with integer ratios. As long as the coherence time is at least twice the number of transmit and receive antennas, these degrees of freedom meet the upper bound in four cases: when the transmitter has fewer antennas than the receivers, when all receivers have the same number of antennas, when the coherence time of one receiver is much shorter than all others, or when all receivers have identical block fading intervals. The degrees of freedom region of the broadcast under identical coherence times was also previously unknown and is settled by the results of this paper. The disparity of coherence times leads to gains that are distinct from those arising from other techniques such as spatial multiplexing or multi-user diversity; this class of gains is denoted coherence diversity. The inner bounds are further extended to the case of multiple receivers experiencing fading block lengths of arbitrary ratio or alignment. Also, in the multiple access channel with unequal coherence times, achievable and outer bounds on the degrees of freedom are obtained.
Complex Linear Physical-Layer Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents the results of a comprehensive investigation of complex linear physical-layer network (PNC) in two-way relay channels (TWRC). A critical question at relay R is as follows: "Given channel gain ratio $η= h_A/h_B$, where $h_A$ and $h_B$ are the complex channel gains from nodes A and B to relay R, respectively, what is the optimal coefficients $(α,β)$ that minimizes the symbol error rate (SER) of $w_N=αw_A+βw_B$ when we attempt to detect $w_N$ in the presence of noise?" Our contributions with respect to this question are as follows: (1) We put forth a general Gaussian-integer formulation for complex linear PNC in which $α,β,w_A, w_B$, and $w_N$ are elements of a finite field of Gaussian integers, that is, the field of $\mathbb{Z}[i]/q$ where $q$ is a Gaussian prime. Previous vector formulation, in which $w_A$, $w_B$, and $w_N$ were represented by $2$-dimensional vectors and $α$ and $β$ were represented by $2\times 2$ matrices, corresponds to a subcase of our Gaussian-integer formulation where $q$ is real prime only. Extension to Gaussian prime $q$, where $q$ can be complex, gives us a larger set of signal constellations to achieve different rates at different SNR. (2) We show how to divide the complex plane of $η$ into different Voronoi regions such that the $η$ within each Voronoi region share the same optimal PNC mapping $(α_{opt},β_{opt})$. We uncover the structure of the Voronoi regions that allows us to compute a minimum-distance metric that characterizes the SER of $w_N$ under optimal PNC mapping $(α_{opt},β_{opt})$. Overall, the contributions in (1) and (2) yield a toolset for a comprehensive understanding of complex linear PNC in $\mathbb{Z}[i]/q$. We believe investigation of linear PNC beyond $\mathbb{Z}[i]/q$ can follow the same approach.
Evaluating Link Prediction Accuracy on Dynamic Networks with Added and Removed Edges
Venue: arXiv cs.SI 2016
Year: 2016

The task of predicting future relationships in a social network, known as link prediction, has been studied extensively in the literature. Many link prediction methods have been proposed, ranging from common neighbors to probabilistic models. Recent work by Yang et al. has highlighted several challenges in evaluating link prediction accuracy. In dynamic networks where edges are both added and removed over time, the link prediction problem is more complex and involves predicting both newly added and newly removed edges. This results in new challenges in the evaluation of dynamic link prediction methods, and the recommendations provided by Yang et al. are no longer applicable, because they do not address edge removal. In this paper, we investigate several metrics currently used for evaluating accuracies of dynamic link prediction methods and demonstrate why they can be misleading in many cases. We provide several recommendations on evaluating dynamic link prediction accuracy, including separation into two categories of evaluation. Finally we propose a unified metric to characterize link prediction accuracy effectively using a single number.
Unfolding Convex Polyhedra via Radially Monotone Cut Trees
Venue: arXiv cs.CG 2016
Year: 2016

A notion of "radially monotone" cut paths is introduced as an effective choice for finding a non-overlapping edge-unfolding of a convex polyhedron. These paths have the property that the two sides of the cut avoid overlap locally as the cut is infinitesimally opened by the curvature at the vertices along the path. It is shown that a class of planar, triangulated convex domains always have a radially monotone spanning forest, a forest that can be found by an essentially greedy algorithm. This algorithm can be mimicked in 3D and applied to polyhedra inscribed in a sphere. Although the algorithm does not provably find a radially monotone cut tree, it in fact does find such a tree with high frequency, and after cutting unfolds without overlap. This performance of a greedy algorithm leads to the conjecture that spherical polyhedra always have a radially monotone cut tree and unfold without overlap.
Automatic Construction of Statechart-Based Anomaly Detection Models for Multi-Threaded Industrial Control Systems
Venue: arXiv cs.CR 2016
Year: 2016

Traffic of Industrial Control System (ICS) between the Human Machine Interface (HMI) and the Programmable Logic Controller (PLC) is known to be highly periodic. However, it is sometimes multiplexed, due to asynchronous scheduling. Modeling the network traffic patterns of multiplexed ICS streams using Deterministic Finite Automata (DFA) for anomaly detection typically produces a very large DFA, and a high false-alarm rate. We introduce a new modeling approach that addresses this gap. Our Statechart DFA modeling includes multiple DFAs, one per cyclic pattern, together with a DFA-selector that de-multiplexes the incoming traffic into sub-channels and sends them to their respective DFAs. We demonstrate how to automatically construct the Statechart from a captured traffic stream. Our unsupervised learning algorithm builds a Discrete-Time Markov Chain (DTMC) from the stream. Next it splits the symbols into sets, one per multiplexed cycle, based on symbol frequencies and node degrees in the DTMC graph. Then it creates a sub-graph for each cycle, and extracts Euler cycles for each sub-graph. The final Statechart is comprised of one DFA per Euler cycle. The algorithms allow for non-unique symbols, that appear in more than one cycle, and also for symbols that appear more than once in a cycle. We evaluated our solution on traces from a production ICS using the Siemens S7-0x72 protocol. We also stress-tested our algorithms on a collection of synthetically-generated traces that simulated multiplexed ICS traces with varying levels of symbol uniqueness and time overlap. The algorithms were able to split the symbols into sets with 99.6% accuracy. The resulting Statechart modeled the traces with a low median false-alarm rate of 0.483%. In all but the most extreme scenarios the Statechart model drastically reduced both the false-alarm rate and the learned model size in compare to a naive single-DFA model
Salient Object Subitizing
Venue: arXiv cs.CV 2016
Year: 2016

We study the problem of Salient Object Subitizing, i.e. predicting the existence and the number of salient objects in an image using holistic cues. This task is inspired by the ability of people to quickly and accurately identify the number of items within the subitizing range (1-4). To this end, we present a salient object subitizing image dataset of about 14K everyday images which are annotated using an online crowdsourcing marketplace. We show that using an end-to-end trained Convolutional Neural Network (CNN) model, we achieve prediction accuracy comparable to human performance in identifying images with zero or one salient object. For images with multiple salient objects, our model also provides significantly better than chance performance without requiring any localization process. Moreover, we propose a method to improve the training of the CNN subitizing model by leveraging synthetic images. In experiments, we demonstrate the accuracy and generalizability of our CNN subitizing model and its applications in salient object detection and image retrieval.