OpenRaiser/Intern-Atlas huggingface dataset:
Inducing and Mitigating a Self-Reinforcing Degradation in Decision-making Teams
Venue: arXiv cs.SY 2016
Year: 2016

The models in this paper demonstrate how self-reinforcing error due to positive feedback can lead to overload and saturation of decision-making elements, and ultimately the cascading collapse of an organization due to the propagation of overload and erroneous decisions throughout the organization. We begin the paper with an analysis of the stability of the decision-making aspects of command organizations from a system-theoretic perspective. A simple dynamic model shows how an organization can enter into a self-reinforcing cycle of increasing decision workload until the demand for decisions exceeds the decision-making capacity of the organization. We then extend the model to more complex networked organizations and show that they also experience a form of self-reinforcing degradation. In particular, we find that the degradation in decision quality has a tendency to propagate through the hierarchical structure, i.e. overload at one location affects other locations by overloading the higher-level components which then in turn overload their subordinates. Our computational experiments suggest several strategies for mitigating this type of malfunction: dumping excessive load, empowering lower echelons, minimizing the need for coordination, using command-by-negation, insulating weak performers, and applying on-line diagnostics. We describe a method to allocate decision responsibility and arrange information flow dynamically within a team of decision-makers for command and control.
Online Trajectory Segmentation and Summary With Applications to Visualization and Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

Trajectory segmentation is the process of subdividing a trajectory into parts either by grouping points similar with respect to some measure of interest, or by minimizing a global objective function. Here we present a novel online algorithm for segmentation and summary, based on point density along the trajectory, and based on the nature of the naturally occurring structure of intermittent bouts of locomotive and local activity. We show an application to visualization of trajectory datasets, and discuss the use of the summary as an index allowing efficient queries which are otherwise impossible or computationally expensive, over very large datasets.
Counting matchings with k unmatched vertices in planar graphs
Venue: arXiv cs.CC 2016
Year: 2016

We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomial-time algorithm, the problem of counting all matchings (possibly containing unmatched vertices, also known as defects) is known to be #P-complete on planar graphs. To interpolate between the hard case of counting matchings and the easy case of counting perfect matchings, we study the parameterized problem of counting matchings with exactly k unmatched vertices in a planar graph G, on input G and k. This setting has a natural interpretation in statistical physics, and it is a special case of counting perfect matchings in k-apex graphs (graphs that can be turned planar by removing at most k vertices). Starting from a recent #W[1]-hardness proof for counting perfect matchings on k-apex graphs, we obtain that counting matchings with k unmatched vertices in planar graphs is #W[1]-hard. In contrast, given a plane graph G with s distinguished faces, there is an $O(2^s \cdot n^3)$ time algorithm for counting those matchings with k unmatched vertices such that all unmatched vertices lie on the distinguished faces. This implies an $f(k,s)\cdot n^{O(1)}$ time algorithm for counting perfect matchings in k-apex graphs whose apex neighborhood is covered by s faces.
Beyond the Dolev-Yao Model: Realistic Application-Specific Attacker Models for Applications Using Vehicular Communication
Venue: arXiv cs.CR 2016
Year: 2016

In recent time, the standards for Vehicular Ad-hoc Networks (VANETs) and Intelligent Transportation Systems (ITSs) matured and scientific and industry interest is high especially as autonomous driving gets a lot of media attention. Autonomous driving and other assistance systems for cars make heavy use of VANETs to exchange information.They may provide more comfort, security and safety for drivers. However, it is of crucial importance for the user's trust in these assistance systems that they could not be influenced by malicious users. VANETs are likely attack vectors for such malicious users, hence application-specific security requirements must be considered during the design of applications using VANETs. In literature, many attacks on vehicular communication have been described but attacks on specific vehicular networking applications are often missing. This paper fills in this gap by describing standardized vehicular networking applications, defining and extending previous attacker models, and using the resulting new models to characterize the possible attackers interested in the specific vehicular networking application. The attacker models presented in this paper hopefully provide great benefit for the scientific community and industry as they allow to compare security evaluations of different works, characterize attackers, their intentions and help to plan application-specific security controls for vehicular networking applications.
25 years of CNNs: Can we compare to human abstraction capabilities?
Venue: arXiv cs.CV 2016
Year: 2016

We try to determine the progress made by convolutional neural networks over the past 25 years in classifying images into abstractc lasses. For this purpose we compare the performance of LeNet to that of GoogLeNet at classifying randomly generated images which are differentiated by an abstract property (e.g., one class contains two objects of the same size, the other class two objects of different sizes). Our results show that there is still work to do in order to solve vision problems humans are able to solve without much difficulty.
SEMBED: Semantic Embedding of Egocentric Action Videos
Venue: arXiv cs.CV 2016
Year: 2016

We present SEMBED, an approach for embedding an egocentric object interaction video in a semantic-visual graph to estimate the probability distribution over its potential semantic labels. When object interactions are annotated using unbounded choice of verbs, we embrace the wealth and ambiguity of these labels by capturing the semantic relationships as well as the visual similarities over motion and appearance features. We show how SEMBED can interpret a challenging dataset of 1225 freely annotated egocentric videos, outperforming SVM classification by more than 5%.
Fine-To-Coarse Global Registration of RGB-D Scans
Venue: arXiv cs.CV 2016
Year: 2016

RGB-D scanning of indoor environments is important for many applications, including real estate, interior design, and virtual reality. However, it is still challenging to register RGB-D images from a hand-held camera over a long video sequence into a globally consistent 3D model. Current methods often can lose tracking or drift and thus fail to reconstruct salient structures in large environments (e.g., parallel walls in different rooms). To address this problem, we propose a "fine-to-coarse" global registration algorithm that leverages robust registrations at finer scales to seed detection and enforcement of new correspondence and structural constraints at coarser scales. To test global registration algorithms, we provide a benchmark with 10,401 manually-clicked point correspondences in 25 scenes from the SUN3D dataset. During experiments with this benchmark, we find that our fine-to-coarse algorithm registers long RGB-D sequences better than previous methods.
Darknet and Deepnet Mining for Proactive Cybersecurity Threat Intelligence
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we present an operational system for cyber threat intelligence gathering from various social platforms on the Internet particularly sites on the darknet and deepnet. We focus our attention to collecting information from hacker forum discussions and marketplaces offering products and services focusing on malicious hacking. We have developed an operational system for obtaining information from these sites for the purposes of identifying emerging cyber threats. Currently, this system collects on average 305 high-quality cyber threat warnings each week. These threat warnings include information on newly developed malware and exploits that have not yet been deployed in a cyber-attack. This provides a significant service to cyber-defenders. The system is significantly augmented through the use of various data mining and machine learning techniques. With the use of machine learning models, we are able to recall 92% of products in marketplaces and 80% of discussions on forums relating to malicious hacking with high precision. We perform preliminary analysis on the data collected, demonstrating its application to aid a security expert for better threat analysis.
Characterizing Complex Networks with Forman-Ricci Curvature and Associated Geometric Flows
Venue: arXiv cs.DM 2016
Year: 2016

We introduce Forman-Ricci curvature and its corresponding flow as characteristics for complex networks attempting to extend the common approach of node-based network analysis by edge-based characteristics. Following a theoretical introduction and mathematical motivation, we apply the proposed network-analytic methods to static and dynamic complex networks and compare the results with established node-based characteristics. Our work suggests a number of applications for data mining, including denoising and clustering of experimental data, as well as extrapolation of network evolution.
Phase Noise Influence in Optical OFDM Systems employing RF Pilot Tone for Phase Noise Cancellation
Venue: arXiv cs.OH 2016
Year: 2016

For coherent and direct-detection Orthogonal Frequency Division Multiplexed (OFDM) systems employing radio frequency (RF) pilot tone phase noise cancellation the influence of laser phase noise is evaluated. Novel analytical results for the common phase error and for the (modulation dependent) inter carrier interference are evaluated based upon Gaussian statistics for the laser phase noise. In the evaluation it is accounted for that the laser phase noise is filtered in the correlation signal detection. Numerical results are presented for OFDM systems with 4 and 16 PSK modulation, 200 OFDM bins and baud rate of 1 GS/s. It is found that about 225 km transmission is feasible for the coherent 4PSK-OFDM system over normal (G.652) fiber.
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
Venue: arXiv cs.DS 2016
Year: 2016

We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed step-by-step to an algorithm in random order. For each request, one option has to be selected so as to maximize a monotone submodular function while ensuring feasibility. For our results, we assume that we are given an offline algorithm computing an $α$-approximation for the respective problem. This way, we separate computational limitations from the ones due to the online nature. When only focusing on the online aspect, we can assume $α= 1$. In the submodular secretary problem, feasibility constraints are cardinality constraints. That is, out of a randomly ordered stream of entities, one has to select a subset size $k$. For this problem, we present a $0.31α$-competitive algorithm for all $k$, which asymptotically reaches competitive ratio $\fracα{e}$ for large $k$. In submodular secretary matching, one side of a bipartite graph is revealed online. Upon arrival, each node has to be matched permanently to an offline node or discarded irrevocably. We give an $\fracα{4}$-competitive algorithm. In both cases, we improve over previously best known competitive ratios, using a generalization of the algorithm for the classic secretary problem. Furthermore, we give an $O(αd^{-\frac{2}{B-1}})$-competitive algorithm for submodular function maximization subject to linear packing constraints. Here, $d$ is the column sparsity, that is the maximal number of none-zero entries in a column of the constraint matrix, and $B$ is the minimal capacity of the constraints. Notably, this bound is independent of the total number of constraints. We improve the algorithm to be $O(αd^{-\frac{1}{B-1}})$-competitive if both $d$ and $B$ are known to the algorithm beforehand.
Labeling of Query Words using Conditional Random Field
Venue: arXiv cs.IR 2016
Year: 2016

This paper describes our approach on Query Word Labeling as an attempt in the shared task on Mixed Script Information Retrieval at Forum for Information Retrieval Evaluation (FIRE) 2015. The query is written in Roman script and the words were in English or transliterated from Indian regional languages. A total of eight Indian languages were present in addition to English. We also identified the Named Entities and special symbols as part of our task. A CRF based machine learning framework was used for labeling the individual words with their corresponding language labels. We used a dictionary based approach for language identification. We also took into account the context of the word while identifying the language. Our system demonstrated an overall accuracy of 75.5% for token level language identification. The strict F-measure scores for the identification of token level language labels for Bengali, English and Hindi are 0.7486, 0.892 and 0.7972 respectively. The overall weighted F-measure of our system was 0.7498.
Service Function Chaining Resource Allocation: A Survey
Venue: arXiv cs.NI 2016
Year: 2016

Service Function Chaining (SFC) is a crucial technology for future Internet. It aims to overcome the limitation of current deployment models which is rigid and static. Application of this technology relies on algorithms that can optimally mapping SFC to substrate network. This category of algorithms is referred as "Service Function Chaining Resource Allocation (SFC-RA)" algorithms or "VNF placement (VNFP)" algorithms. This paper presents a survey of current researches in SFC-RA algorithms. After presenting the formulation and related problems, several variants of SFC-RA problem are summarized. At last, we discussed several future research directions.
Asymmetric Degrees of Freedom of the Full-Duplex MIMO 3-Way Channel with Unicast and Broadcast Messages
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we characterize the asymmetric total degrees of freedom (DoF) of a multiple-input multiple-output (MIMO) 3-way channel. Each node has a separate-antenna full-duplex MIMO transceiver with a different number of antennas, where each antenna can be configured for either signal transmission or reception. We study this system under two message configurations; the first configuration is when each node has two unicast messages to be delivered to the two other nodes, while the second configuration is when each node has two unicast messages as well as one broadcast message to be delivered to the two other nodes. For each configuration, we first derive upper bounds on the total DoF of the system. Cut-set bounds in conjunction with genie-aided bounds are derived to characterize the achievable total DoF. Afterwards, we analytically derive the optimal number of transmit and receive antennas at each node to maximize the total DoF of the system, subject to the total number of antennas at each node. Finally, the achievable schemes for each configuration are constructed. The proposed schemes are mainly based on zero-forcing and null-space transmit beamforming.
Efficient sampling-based bottleneck pathfinding over cost maps
Venue: arXiv cs.RO 2016
Year: 2016

We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map $\mathcal{M}:\mathbb{R}^d\rightarrow \mathbb{R}$, which assigns to every point in space a real value, we wish to find a path connecting two given points, that minimizes the maximal value with respect to~$\mathcal{M}$. We demonstrate the capabilities of our algorithm, which we call bottleneck tree (BTT), on several challenging instances of the problem involving multiple agents, where it outperforms the state-of-the-art cost-map planning technique T-RRT*. On the theoretical side, we study the asymptotic properties of our method and consider the special setting where the computed trajectories must be monotone in all coordinates. This constraint arises in cases where the problem involves the coordination of multiple agents that are restricted to forward motions along predefined paths.
Union is strength in lossy image compression
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we present a comparison between different techniques of image compression. First, the image is divided in blocks which are organized according to a certain scan. Later, several compression techniques are applied, combined or alone. Such techniques are: wavelets (Haar's basis), Karhunen-Loeve Transform, etc. Simulations show that the combined versions are the best, with minor Mean Squared Error (MSE), and higher Peak Signal to Noise Ratio (PSNR) and better image quality, even in the presence of noise.
On Approximating Maximum Independent Set of Rectangles
Venue: arXiv cs.DS 2016
Year: 2016

We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of $n$ axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no two of them overlap. MISR is a basic geometric optimization problem with many applications, that has been studied extensively. Until recently, the best approximation algorithm for it achieved an $O(\log \log n)$-approximation factor. In a recent breakthrough, Adamaszek and Wiese provided a quasi-polynomial time approximation scheme: a $(1-ε)$-approximation algorithm with running time $n^{O(\operatorname{poly}(\log n)/ε)}$. Despite this result, obtaining a PTAS or even a polynomial-time constant-factor approximation remains a challenging open problem. In this paper we make progress towards this goal by providing an algorithm for MISR that achieves a $(1 - ε)$-approximation in time $n^{O(\operatorname{poly}(\log\log{n} / ε))}$. We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.
Kalman's shrinkage for wavelet-based despeckling of SAR images
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a new probability density function (pdf) is proposed to model the statistics of wavelet coefficients, and a simple Kalman's filter is derived from the new pdf using Bayesian estimation theory. Specifically, we decompose the speckled image into wavelet subbands, we apply the Kalman's filter to the high subbands, and reconstruct a despeckled image from the modified detail coefficients. Experimental results demonstrate that our method compares favorably to several other despeckling methods on test synthetic aperture radar (SAR) images.
Denoising based on wavelets and deblurring via self-organizing map for Synthetic Aperture Radar images
Venue: arXiv cs.CV 2016
Year: 2016

This work deals with unsupervised image deblurring. We present a new deblurring procedure on images provided by low-resolution synthetic aperture radar (SAR) or simply by multimedia in presence of multiplicative (speckle) or additive noise, respectively. The method we propose is defined as a two-step process. First, we use an original technique for noise reduction in wavelet domain. Then, the learning of a Kohonen self-organizing map (SOM) is performed directly on the denoised image to take out it the blur. This technique has been successfully applied to real SAR images, and the simulation results are presented to demonstrate the effectiveness of the proposed algorithms.
Left-corner Methods for Syntactic Modeling with Universal Structural Constraints
Venue: arXiv cs.CL 2016
Year: 2016

The primary goal in this thesis is to identify better syntactic constraint or bias, that is language independent but also efficiently exploitable during sentence processing. We focus on a particular syntactic construction called center-embedding, which is well studied in psycholinguistics and noted to cause particular difficulty for comprehension. Since people use language as a tool for communication, one expects such complex constructions to be avoided for communication efficiency. From a computational perspective, center-embedding is closely relevant to a left-corner parsing algorithm, which can capture the degree of center-embedding of a parse tree being constructed. This connection suggests left-corner methods can be a tool to exploit the universal syntactic constraint that people avoid generating center-embedded structures. We explore such utilities of center-embedding as well as left-corner methods extensively through several theoretical and empirical examinations. Our primary task is unsupervised grammar induction. In this task, the input to the algorithm is a collection of sentences, from which the model tries to extract the salient patterns on them as a grammar. This is a particularly hard problem although we expect the universal constraint may help in improving the performance since it can effectively restrict the possible search space for the model. We build the model by extending the left-corner parsing algorithm for efficiently tabulating the search space except those involving center-embedding up to a specific degree. We examine the effectiveness of our approach on many treebanks, and demonstrate that often our constraint leads to better parsing performance. We thus conclude that left-corner methods are particularly useful for syntax-oriented systems, as it can exploit efficiently the inherent universal constraints in languages.
Hiding Individuals and Communities in a Social Network
Venue: arXiv cs.SI 2016
Year: 2016

The Internet and social media have fueled enormous interest in social network analysis. New tools continue to be developed and used to analyse our personal connections, with particular emphasis on detecting communities or identifying key individuals in a social network. This raises privacy concerns that are likely to exacerbate in the future. With this in mind, we ask the question: Can individuals or groups actively manage their connections to evade social network analysis tools? By addressing this question, the general public may better protect their privacy, oppressed activist groups may better conceal their existence, and security agencies may better understand how terrorists escape detection. We first study how an individual can evade "network centrality" analysis without compromising his or her influence within the network. We prove that an optimal solution to this problem is hard to compute. Despite this hardness, we demonstrate that even a simple heuristic, whereby attention is restricted to the individual's immediate neighbourhood, can be surprisingly effective in practice. For instance, it could disguise Mohamed Atta's leading position within the WTC terrorist network, and that is by rewiring a strikingly-small number of connections. Next, we study how a community can increase the likelihood of being overlooked by community-detection algorithms. We propose a measure of concealment, expressing how well a community is hidden, and use it to demonstrate the effectiveness of a simple heuristic, whereby members of the community either "unfriend" certain other members, or "befriend" some non-members, in a coordinated effort to camouflage their community.