OpenRaiser/Intern-Atlas huggingface dataset:
Numerically Stable Evaluation of Moments of Random Gram Matrices with Applications
Venue: arXiv cs.IT 2017
Year: 2017

This paper is focuses on the computation of the positive moments of one-side correlated random Gram matrices. Closed-form expressions for the moments can be obtained easily, but numerical evaluation thereof is prone to numerical stability, especially in high-dimensional settings. This letter provides a numerically stable method that efficiently computes the positive moments in closed-form. The developed expressions are more accurate and can lead to higher accuracy levels when fed to moment based-approaches. As an application, we show how the obtained moments can be used to approximate the marginal distribution of the eigenvalues of random Gram matrices.
Discrete approximations of the affine Gaussian derivative model for visual receptive fields
Venue: arXiv cs.CV 2017
Year: 2017

The affine Gaussian derivative model can in several respects be regarded as a canonical model for receptive fields over a spatial image domain: (i) it can be derived by necessity from scale-space axioms that reflect structural properties of the world, (ii) it constitutes an excellent model for the receptive fields of simple cells in the primary visual cortex and (iii) it is covariant under affine image deformations, which enables more accurate modelling of image measurements under the local image deformations caused by the perspective mapping, compared to the more commonly used Gaussian derivative model based on derivatives of the rotationally symmetric Gaussian kernel. This paper presents a theory for discretizing the affine Gaussian scale-space concept underlying the affine Gaussian derivative model, so that scale-space properties hold also for the discrete implementation. Two ways of discretizing spatial smoothing with affine Gaussian kernels are presented: (i) by solving semi-discretized affine diffusion equation, which has derived by necessity from the requirements of a semi-group structure over scale as parameterized by a family of spatial covariance matrices and obeying non-creation of new structures from any finer to any coarser scale in terms of non-enhancement of local extrema and (ii) approximating these semi-discrete affine receptive fields by parameterized families of 3x3-kernels as obtained from an additional discretization along the scale direction. The latter discrete approach can be optionally complemented by spatial subsampling at coarser scales, leading to the notion of affine hybrid pyramids. Using these theoretical results, we outline hybrid architectures for discrete approximations of affine covariant receptive field families, to be used as a first processing layer for affine covariant and affine invariant visual operations at higher levels.
Shallow and Deep Networks Intrusion Detection System: A Taxonomy and Survey
Venue: arXiv cs.CR 2017
Year: 2017

Intrusion detection has attracted a considerable interest from researchers and industries. The community, after many years of research, still faces the problem of building reliable and efficient IDS that are capable of handling large quantities of data, with changing patterns in real time situations. The work presented in this manuscript classifies intrusion detection systems (IDS). Moreover, a taxonomy and survey of shallow and deep networks intrusion detection systems is presented based on previous and current works. This taxonomy and survey reviews machine learning techniques and their performance in detecting anomalies. Feature selection which influences the effectiveness of machine learning (ML) IDS is discussed to explain the role of feature selection in the classification and training phase of ML IDS. Finally, a discussion of the false and true positive alarm rates is presented to help researchers model reliable and efficient machine learning based intrusion detection systems.
An SDN Approach for an Energy Efficient Heterogeneous Communication Network in Disaster Scenarios
Venue: arXiv cs.NI 2017
Year: 2017

Wireless access technologies have been extensively developed aiming to give users the ability to connect to their expected networks anytime, anywhere. This leads to an increment of the number of wireless interfaces integrated into a single mobile device, hence, it allows the device to be able to connect to multiple access networks. However, in some specific cases such as natural disasters, having an uncorrupted and timely information exchanging means is critical for affected victims to survive or to connect to the outside world. This is because the essential network infrastructures in these cases could be destroyed causing a large number of systems to stop working. In that cases, the victims need a heterogeneous communications network in which they can communicate, without a doubt, by using different wireless access technologies, i.e., Bluetooth or Wi-Fi. The network must also be able to smoothly change the access technologies, or called a vertical handover, to ensure QoS for ongoing applications. In addition, the network must have a mechanism to save energy. For hese reasons, an SDN approach, which has been proposed in a previous work, is considered. The performance of the system has been validated by a set of experiments in a real testbed. The obtained results show that the proposed vertical handover can save at least 24.42 per cent of the energy consumed by the wireless communication. The handover delay with different UDP traffic is less than 150ms. Moreover, the network allows a device using Bluetooth to talk with another one using Wi-Fi over a heterogeneous connection where the end-to-end jitter is mainly below 20ms and the packet loss rate is as small as 0.2 per cent.
A Learning-based Variable Size Part Extraction Architecture for 6D Object Pose Recovery in Depth
Venue: arXiv cs.CV 2017
Year: 2017

State-of-the-art techniques for 6D object pose recovery depend on occlusion-free point clouds to accurately register objects in 3D space. To deal with this shortcoming, we introduce a novel architecture called Iterative Hough Forest with Histogram of Control Points that is capable of estimating the 6D pose of occluded and cluttered objects given a candidate 2D bounding box. Our Iterative Hough Forest (IHF) is learnt using parts extracted only from the positive samples. These parts are represented with Histogram of Control Points (HoCP), a "scale-variant" implicit volumetric description, which we derive from recently introduced Implicit B-Splines (IBS). The rich discriminative information provided by the scale-variant HoCP features is leveraged during inference. An automatic variable size part extraction framework iteratively refines the object's initial pose that is roughly aligned due to the extraction of coarsest parts, the ones occupying the largest area in image pixels. The iterative refinement is accomplished based on finer (smaller) parts that are represented with more discriminative control point descriptors by using our Iterative Hough Forest. Experiments conducted on a publicly available dataset report that our approach show better registration performance than the state-of-the-art methods.
Crowdsourcing Ground Truth for Medical Relation Extraction
Venue: arXiv cs.CL 2017
Year: 2017

Cognitive computing systems require human labeled data for evaluation, and often for training. The standard practice used in gathering this data minimizes disagreement between annotators, and we have found this results in data that fails to account for the ambiguity inherent in language. We have proposed the CrowdTruth method for collecting ground truth through crowdsourcing, that reconsiders the role of people in machine learning based on the observation that disagreement between annotators provides a useful signal for phenomena such as ambiguity in the text. We report on using this method to build an annotated data set for medical relation extraction for the $cause$ and $treat$ relations, and how this data performed in a supervised training experiment. We demonstrate that by modeling ambiguity, labeled data gathered from crowd workers can (1) reach the level of quality of domain experts for this task while reducing the cost, and (2) provide better training data at scale than distant supervision. We further propose and validate new weighted measures for precision, recall, and F-measure, that account for ambiguity in both human and machine performance on this task.
A Modularity Bug in Java 8
Venue: arXiv cs.PL 2017
Year: 2017

We demonstrate a modularity bug in the interface system of Java 8 on the practical example of a textbook design of a modular interface for vector spaces. Our example originates in our teaching of modular object-oriented design in Java 8 to undergraduate students, simply following standard programming practices and mathematical definitions. The bug shows up as a compilation error and should be fixed with a language extension due to the importance of best practices (design fidelity).
Searching edges in the overlap of two plane graphs
Venue: arXiv cs.CG 2017
Year: 2017

Consider a pair of plane straight-line graphs, whose edges are colored red and blue, respectively, and let n be the total complexity of both graphs. We present a O(n log n)-time O(n)-space technique to preprocess such pair of graphs, that enables efficient searches among the red-blue intersections along edges of one of the graphs. Our technique has a number of applications to geometric problems. This includes: (1) a solution to the batched red-blue search problem [Dehne et al. 2006] in O(n log n) queries to the oracle; (2) an algorithm to compute the maximum vertical distance between a pair of 3D polyhedral terrains one of which is convex in O(n log n) time, where n is the total complexity of both terrains; (3) an algorithm to construct the Hausdorff Voronoi diagram of a family of point clusters in the plane in O((n+m) log^3 n) time and O(n+m) space, where n is the total number of points in all clusters and m is the number of crossings between all clusters; (4) an algorithm to construct the farthest-color Voronoi diagram of the corners of n axis-aligned rectangles in O(n log^2 n) time; (5) an algorithm to solve the stabbing circle problem for n parallel line segments in the plane in optimal O(n log n) time. All these results are new or improve on the best known algorithms.
Sampling a Network to Find Nodes of Interest
Venue: arXiv cs.SI 2017
Year: 2017

The focus of the current research is to identify people of interest in social networks. We are especially interested in studying dark networks, which represent illegal or covert activity. In such networks, people are unlikely to disclose accurate information when queried. We present REDLEARN, an algorithm for sampling dark networks with the goal of identifying as many nodes of interest as possible. We consider two realistic lying scenarios, which describe how individuals in a dark network may attempt to conceal their connections. We test and present our results on several real-world multilayered networks, and show that REDLEARN achieves up to a 340% improvement over the next best strategy.
An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

Social networks allow rapid spread of ideas and innovations while the negative information can also propagate widely. When the cascades with different opinions reaching the same user, the cascade arriving first is the most likely to be taken by the user. Therefore, once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget $k$, the rumor blocking problem asks for $k$ seed users to trigger the spread of the positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of $(1-1/e-δ)$ by a classic greedy algorithm combined with Monte Carlo simulation with the running time of $O(\frac{k^3mn\ln n}{δ^2})$, where $n$ and $m$ are the number of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm which runs in $O(\frac{km\ln n}{δ^2})$ expected time and provides a $(1-1/e-δ)$-approximation with a high probability. The experimentally results on both the real-world and synthetic social networks have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.
Reinforcement Learning based Embodied Agents Modelling Human Users Through Interaction and Multi-Sensory Perception
Venue: arXiv cs.HC 2017
Year: 2017

This paper extends recent work in interactive machine learning (IML) focused on effectively incorporating human feedback. We show how control and feedback signals complement each other in systems which model human reward. We demonstrate that simultaneously incorporating human control and feedback signals can improve interactive robotic systems' performance on a self-mirrored movement control task where an RL-agent controlled right arm attempts to match the preprogrammed movement pattern of the left arm. We illustrate the impact of varying human feedback parameters on task performance by investigating the probability of giving feedback on each time step and the likelihood of given feedback being correct. We further illustrate that varying the temporal decay with which the agent incorporates human feedback has a significant impact on task performance. We found that smearing human feedback over time steps improves performance and we show varying the probability of feedback at each time step, and an increased likelihood of those feedbacks being 'correct' can impact agent performance. We conclude that understanding latent variables in human feedback is crucial for learning algorithms acting in human-machine interaction domains.
On Rivest-Vuillemin Conjecture for Fourteen Variables
Venue: arXiv cs.CC 2017
Year: 2017

A boolean function $f(x_1,...,x_n)$ is \textit{weakly symmetric} if it is invariant under a transitive permutation group on its variables. A boolean function $f(x_1,...,x_n)$ is \textit{elusive} if we have to check all $x_1$,..., $x_n$ to determine the output of $f(x_1,...,x_n)$ in the worst-case. It is conjectured that every nontrivial monotone weakly symmetric boolean function is elusive, which has been open for a long time. In this paper, we report that this conjecture is true for $n=14$.
Managing Risk of Bidding in Display Advertising
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, we deal with the uncertainty of bidding for display advertising. Similar to the financial market trading, real-time bidding (RTB) based display advertising employs an auction mechanism to automate the impression level media buying; and running a campaign is no different than an investment of acquiring new customers in return for obtaining additional converted sales. Thus, how to optimally bid on an ad impression to drive the profit and return-on-investment becomes essential. However, the large randomness of the user behaviors and the cost uncertainty caused by the auction competition may result in a significant risk from the campaign performance estimation. In this paper, we explicitly model the uncertainty of user click-through rate estimation and auction competition to capture the risk. We borrow an idea from finance and derive the value at risk for each ad display opportunity. Our formulation results in two risk-aware bidding strategies that penalize risky ad impressions and focus more on the ones with higher expected return and lower risk. The empirical study on real-world data demonstrates the effectiveness of our proposed risk-aware bidding strategies: yielding profit gains of 15.4% in offline experiments and up to 17.5% in an online A/B test on a commercial RTB platform over the widely applied bidding strategies.
Closure structures parameterized by systems of isotone Galois connections
Venue: arXiv cs.LO 2017
Year: 2017

We study properties of classes of closure operators and closure systems parameterized by systems of isotone Galois connections. The parameterizations express stronger requirements on idempotency and monotony conditions of closure operators. The present approach extends previous approaches to fuzzy closure operators which appeared in analysis of object-attribute data with graded attributes and reasoning with if-then rules in graded setting and is also related to analogous results developed in linear temporal logic. In the paper, we present foundations of the operators and include examples of general problems in data analysis where such operators appear.
Rate Optimal Binary Linear Locally Repairable Codes with Small Availability
Venue: arXiv cs.IT 2017
Year: 2017

A locally repairable code with availability has the property that every code symbol can be recovered from multiple, disjoint subsets of other symbols of small size. In particular, a code symbol is said to have $(r,t)$-availability if it can be recovered from $t$ disjoint subsets, each of size at most $r$. A code with availability is said to be 'rate-optimal', if its rate is maximum among the class of codes with given locality, availability, and alphabet size. This paper focuses on rate-optimal binary, linear codes with small availability, and makes four contributions. First, it establishes tight upper bounds on the rate of binary linear codes with $(r,2)$ and $(2,3)$ availability. Second, it establishes a uniqueness result for binary rate-optimal codes, showing that for certain classes of binary linear codes with $(r,2)$ and $(2,3)$-availability, any rate optimal code must be a direct sum of shorter rate optimal codes. Third, it presents novel upper bounds on the rates of binary linear codes with $(2,t)$ and $(r,3)$-availability. In particular, the main contribution here is a new method for bounding the number of cosets of the dual of a code with availability, using its covering properties. Finally, it presents a class of locally repairable linear codes associated with convex polyhedra, focusing on the codes associated with the Platonic solids. It demonstrates that these codes are locally repairable with $t = 2$, and that the codes associated with (geometric) dual polyhedra are (coding theoretic) duals of each other.
Efficient Image Set Classification using Linear Regression based Image Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel image set classification technique using linear regression models. Downsampled gallery image sets are interpreted as subspaces of a high dimensional space to avoid the computationally expensive training step. We estimate regression models for each test image using the class specific gallery subspaces. Images of the test set are then reconstructed using the regression models. Based on the minimum reconstruction error between the reconstructed and the original images, a weighted voting strategy is used to classify the test set. We performed extensive evaluation on the benchmark UCSD/Honda, CMU Mobo and YouTube Celebrity datasets for face classification, and ETH-80 dataset for object classification. The results demonstrate that by using only a small amount of training data, our technique achieved competitive classification accuracy and superior computational speed compared with the state-of-the-art methods.
On Centroidal Dynamics and Integrability of Average Angular Velocity
Venue: arXiv cs.RO 2017
Year: 2017

In the literature on robotics and multibody dynamics, the concept of average angular velocity has received considerable attention in recent years. We address the question of whether the average angular velocity defines an orientation framethat depends only on the current robot configuration and provide a simple algebraic condition to check whether this holds. In the language of geometric mechanics, this condition corresponds to requiring the flatness of the mechanical connection associated to the robotic system. Here, however, we provide both a reinterpretation and a proof of this result accessible to readers with a background in rigid body kinematics and multibody dynamics but not necessarily acquainted with differential geometry, still providing precise links to the geometric mechanics literature. This should help spreading the algebraic condition beyond the scope of geometric mechanics,contributing to a proper utilization and understanding of the concept of average angular velocity.
A Chunk Caching Location and Searching Scheme in Content Centric Networking
Venue: arXiv cs.NI 2017
Year: 2017

Content Centric Networking (CCN) is a new network infrastructure around content dissemination and retrieval, shift from host addresses to named data. Each CCN router has a cache to store the chunks passed by it. Therefore the caching strategy about chunk placement can greatly affect the whole CCN performance. This paper proposes an implicit coordinate chunk caching location and searching scheme (CLS) in CCN hierarchical infrastructure. In CLS, there is at most one copy of a chunk cached on the path between a server and a leaf router. This copy is pulled down one level towards the leaf router by a request or pushed up one level towards the server by the cache eviction. Thus, it is possible to store more diverse contents in the whole CCN and improve the network performance. Plus, in order to reduce the server workload and file download time, a caching trail of chunk is created to direct the following request where to find the chunk. Extensive test-bed experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme outperforms existing algorithms.
Predicting Citywide Crowd Flows Using Deep Spatio-Temporal Residual Networks
Venue: arXiv cs.AI 2017
Year: 2017

Forecasting the flow of crowds is of great importance to traffic management and public safety, and very challenging as it is affected by many complex factors, including spatial dependencies (nearby and distant), temporal dependencies (closeness, period, trend), and external conditions (e.g., weather and events). We propose a deep-learning-based approach, called ST-ResNet, to collectively forecast two types of crowd flows (i.e. inflow and outflow) in each and every region of a city. We design an end-to-end structure of ST-ResNet based on unique properties of spatio-temporal data. More specifically, we employ the residual neural network framework to model the temporal closeness, period, and trend properties of crowd traffic. For each property, we design a branch of residual convolutional units, each of which models the spatial properties of crowd traffic. ST-ResNet learns to dynamically aggregate the output of the three residual neural networks based on data, assigning different weights to different branches and regions. The aggregation is further combined with external factors, such as weather and day of the week, to predict the final traffic of crowds in each and every region. We have developed a real-time system based on Microsoft Azure Cloud, called UrbanFlow, providing the crowd flow monitoring and forecasting in Guiyang City of China. In addition, we present an extensive experimental evaluation using two types of crowd flows in Beijing and New York City (NYC), where ST-ResNet outperforms nine well-known baselines.