OpenRaiser/Intern-Atlas huggingface dataset:
ORFEL: efficient detection of defamation or illegitimate promotion in online recommendation
Venue: arXiv cs.SI 2016
Year: 2016

What if a successful company starts to receive a torrent of low-valued (one or two stars) recommendations in its mobile apps from multiple users within a short (say one month) period of time? Is it legitimate evidence that the apps have lost in quality, or an intentional plan (via lockstep behavior) to steal market share through defamation? In the case of a systematic attack to one's reputation, it might not be possible to manually discern between legitimate and fraudulent interaction within the huge universe of possibilities of user-product recommendation. Previous works have focused on this issue, but none of them took into account the context, modeling, and scale that we consider in this paper. Here, we propose the novel method Online-Recommendation Fraud ExcLuder (ORFEL) to detect defamation and/or illegitimate promotion of online products by using vertex-centric asynchronous parallel processing of bipartite (users-products) graphs. With an innovative algorithm, our results demonstrate both efficacy and efficiency -- over 95% of potential attacks were detected, and ORFEL was at least two orders of magnitude faster than the state-of-the-art. Over a novel methodology, our main contributions are: (1) a new algorithmic solution; (2) one scalable approach; and (3) a novel context and modeling of the problem, which now addresses both defamation and illegitimate promotion. Our work deals with relevant issues of the Web 2.0, potentially augmenting the credibility of online recommendation to prevent losses to both customers and vendors.
Representing Meaning with a Combination of Logical and Distributional Models
Venue: arXiv cs.CL 2016
Year: 2016

NLP tasks differ in the semantic information they require, and at this time no single se- mantic representation fulfills all requirements. Logic-based representations characterize sentence structure, but do not capture the graded aspect of meaning. Distributional models give graded similarity ratings for words and phrases, but do not capture sentence structure in the same detail as logic-based approaches. So it has been argued that the two are complementary. We adopt a hybrid approach that combines logic-based and distributional semantics through probabilistic logic inference in Markov Logic Networks (MLNs). In this paper, we focus on the three components of a practical system integrating logical and distributional models: 1) Parsing and task representation is the logic-based part where input problems are represented in probabilistic logic. This is quite different from representing them in standard first-order logic. 2) For knowledge base construction we form weighted inference rules. We integrate and compare distributional information with other sources, notably WordNet and an existing paraphrase collection. In particular, we use our system to evaluate distributional lexical entailment approaches. We use a variant of Robinson resolution to determine the necessary inference rules. More sources can easily be added by mapping them to logical rules; our system learns a resource-specific weight that corrects for scaling differences between resources. 3) In discussing probabilistic inference, we show how to solve the inference problems efficiently. To evaluate our approach, we use the task of textual entailment (RTE), which can utilize the strengths of both logic-based and distributional representations. In particular we focus on the SICK dataset, where we achieve state-of-the-art results.
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization
Venue: arXiv cs.CV 2016
Year: 2016

We present a robust and real-time monocular six degree of freedom relocalization system. Our system trains a convolutional neural network to regress the 6-DOF camera pose from a single RGB image in an end-to-end manner with no need of additional engineering or graph optimisation. The algorithm can operate indoors and outdoors in real time, taking 5ms per frame to compute. It obtains approximately 2m and 6 degree accuracy for large scale outdoor scenes and 0.5m and 10 degree accuracy indoors. This is achieved using an efficient 23 layer deep convnet, demonstrating that convnets can be used to solve complicated out of image plane regression problems. This was made possible by leveraging transfer learning from large scale classification data. We show the convnet localizes from high level features and is robust to difficult lighting, motion blur and different camera intrinsics where point based SIFT registration fails. Furthermore we show how the pose feature that is produced generalizes to other scenes allowing us to regress pose with only a few dozen training examples. PoseNet code, dataset and an online demonstration is available on our project webpage, at http://mi.eng.cam.ac.uk/projects/relocalisation/
DiscoverFriends: Secure Social Network Communication in Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2016
Year: 2016

This paper presents a secure communication application called DiscoverFriends. Its purpose is to securely communicate to a group of online friends while bypassing their respective social networking servers under a mobile ad hoc network environment. DiscoverFriends leverages Bloom filters and a hybrid encryption technique with a self-organized public-key management scheme to securely identify friends and provide authentication. Additionally, DiscoverFriends enables anonymous location check-ins by utilizing a new cryptographic primitive called Function Secret Sharing. Finally, to the best of our knowledge, DiscoverFriends implements and evaluates the first Android multi-hop WiFi direct protocol using IPv6.
Localized eigenvectors of the non-backtracking matrix
Venue: arXiv cs.SI 2016
Year: 2016

In the case of graph partitioning, the emergence of localized eigenvectors can cause the standard spectral method to fail. To overcome this problem, the spectral method using a non-backtracking matrix was proposed. Based on numerical experiments on several examples of real networks, it is clear that the non-backtracking matrix does not exhibit localization of eigenvectors. However, we show that localized eigenvectors of the non-backtracking matrix can exist outside the spectral band, which may lead to deterioration in the performance of graph partitioning.
A Survey on Wireless Security: Technical Challenges, Recent Advances and Future Trends
Venue: arXiv cs.IT 2016
Year: 2016

This paper examines the security vulnerabilities and threats imposed by the inherent open nature of wireless communications and to devise efficient defense mechanisms for improving the wireless network security. We first summarize the security requirements of wireless networks, including their authenticity, confidentiality, integrity and availability issues. Next, a comprehensive overview of security attacks encountered in wireless networks is presented in view of the network protocol architecture, where the potential security threats are discussed at each protocol layer. We also provide a survey of the existing security protocols and algorithms that are adopted in the existing wireless network standards, such as the Bluetooth, Wi-Fi, WiMAX, and the long-term evolution (LTE) systems. Then, we discuss the state-of-the-art in physical-layer security, which is an emerging technique of securing the open communications environment against eavesdropping attacks at the physical layer. We also introduce the family of various jamming attacks and their counter-measures, including the constant jammer, intermittent jammer, reactive jammer, adaptive jammer and intelligent jammer. Additionally, we discuss the integration of physical-layer security into existing authentication and cryptography mechanisms for further securing wireless networks. Finally, some technical challenges which remain unresolved at the time of writing are summarized and the future trends in wireless security are discussed.
A large neighbourhood based heuristic for two-echelon routing problems
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we address two optimisation problems arising in the context of city logistics and two-level transportation systems. The two-echelon vehicle routing problem and the two-echelon location routing problem seek to produce vehicle itineraries to deliver goods to customers, with transits through intermediate facilities. To efficiently solve these problems, we propose a hybrid metaheuristic which combines enumerative local searches with destroy-and-repair principles, as well as some tailored operators to optimise the selections of intermediate facilities. We conduct extensive computational experiments to investigate the contribution of these operators to the search performance, and measure the performance of the method on both problem classes. The proposed algorithm finds the current best known solutions, or better ones, for 95% of the two-echelon vehicle routing problem benchmark instances. Overall, for both problems, it achieves high-quality solutions within short computing times. Finally, for future reference, we resolve inconsistencies between different versions of benchmark instances, document their differences, and provide them all online in a unified format.
Synapse: Synthetic Application Profiler and Emulator
Venue: arXiv cs.DC 2016
Year: 2016

We introduce Synapse motivated by the needs to estimate and emulate workload execution characteristics on high-performance and distributed heterogeneous resources. Synapse has a platform independent application profiler, and the ability to emulate profiled workloads on a variety of heterogeneous resources. Synapse is used as a proxy application (or "representative application") for real workloads, with the added advantage that it can be tuned at arbitrary levels of granularity in ways that are simply not possible using real applications. Experiments show that automated profiling using Synapse represents application characteristics with high fidelity. Emulation using Synapse can reproduce the application behavior in the original runtime environment, as well as reproducing properties when used in a different run-time environments.
Network Topology Identification using PCA and its Graph Theoretic Interpretations
Venue: arXiv cs.LG 2016
Year: 2016

We solve the problem of identifying (reconstructing) network topology from steady state network measurements. Concretely, given only a data matrix $\mathbf{X}$ where the $X_{ij}$ entry corresponds to flow in edge $i$ in configuration (steady-state) $j$, we wish to find a network structure for which flow conservation is obeyed at all the nodes. This models many network problems involving conserved quantities like water, power, and metabolic networks. We show that identification is equivalent to learning a model $\mathbf{A_n}$ which captures the approximate linear relationships between the different variables comprising $\mathbf{X}$ (i.e. of the form $\mathbf{A_n X \approx 0}$) such that $\mathbf{A_n}$ is full rank (highest possible) and consistent with a network node-edge incidence structure. The problem is solved through a sequence of steps like estimating approximate linear relationships using Principal Component Analysis, obtaining f-cut-sets from these approximate relationships, and graph realization from f-cut-sets (or equivalently f-circuits). Each step and the overall process is polynomial time. The method is illustrated by identifying topology of a water distribution network. We also study the extent of identifiability from steady-state data.
Combating Fraud in Online Social Networks: Detecting Stealthy Facebook Like Farms
Venue: arXiv cs.SI 2016
Year: 2016

As businesses increasingly rely on social networking sites to engage with their customers, it is crucial to understand and counter reputation manipulation activities, including fraudulently boosting the number of Facebook page likes using like farms. To this end, several fraud detection algorithms have been proposed and some deployed by Facebook that use graph co-clustering to distinguish between genuine likes and those generated by farm-controlled profiles. However, as we show in this paper, these tools do not work well with stealthy farms whose users spread likes over longer timespans and like popular pages, aiming to mimic regular users. We present an empirical analysis of the graph-based detection tools used by Facebook and highlight their shortcomings against more sophisticated farms. Next, we focus on characterizing content generated by social networks accounts on their timelines, as an indicator of genuine versus fake social activity. We analyze a wide range of features extracted from timeline posts, which we group into two main classes: lexical and non-lexical. We postulate and verify that like farm accounts tend to often re-share content, use fewer words and poorer vocabulary, and more often generate duplicate comments and likes compared to normal users. We extract relevant lexical and non-lexical features and and use them to build a classifier to detect like farms accounts, achieving significantly higher accuracy, namely, at least 99% precision and 93% recall.
Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks
Venue: arXiv cs.CV 2016
Year: 2016

State-of-the-art object detection networks depend on region proposal algorithms to hypothesize object locations. Advances like SPPnet and Fast R-CNN have reduced the running time of these detection networks, exposing region proposal computation as a bottleneck. In this work, we introduce a Region Proposal Network (RPN) that shares full-image convolutional features with the detection network, thus enabling nearly cost-free region proposals. An RPN is a fully convolutional network that simultaneously predicts object bounds and objectness scores at each position. The RPN is trained end-to-end to generate high-quality region proposals, which are used by Fast R-CNN for detection. We further merge RPN and Fast R-CNN into a single network by sharing their convolutional features---using the recently popular terminology of neural networks with 'attention' mechanisms, the RPN component tells the unified network where to look. For the very deep VGG-16 model, our detection system has a frame rate of 5fps (including all steps) on a GPU, while achieving state-of-the-art object detection accuracy on PASCAL VOC 2007, 2012, and MS COCO datasets with only 300 proposals per image. In ILSVRC and COCO 2015 competitions, Faster R-CNN and RPN are the foundations of the 1st-place winning entries in several tracks. Code has been made publicly available.
Socially Driven News Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

The participatory Web has enabled the ubiquitous and pervasive access of information, accompanied by an increase of speed and reach in information sharing. Data dissemination services such as news aggregators are expected to provide up-to-date, real-time information to the end users. News aggregators are in essence recommendation systems that filter and rank news stories in order to select the few that will appear on the users front screen at any time. One of the main challenges in such systems is to address the recency and latency problems, that is, to identify as soon as possible how important a news story is. In this work we propose an integrated framework that aims at predicting the importance of news items upon their publication with a focus on recent and highly popular news, employing resampling strategies, and at translating the result into concrete news rankings. We perform an extensive experimental evaluation using real-life datasets of the proposed framework as both a stand-alone system and when applied to news recommendations from Google News. Additionally, we propose and evaluate a combinatorial solution to the augmentation of official media recommendations with social information. Results show that the proposed approach complements and enhances the news rankings generated by state-of-the-art systems.
Capacity of the Energy Harvesting Channel with a Finite Battery
Venue: arXiv cs.IT 2016
Year: 2016

We consider an energy harvesting channel, in which the transmitter is powered by an exogenous stochastic energy harvesting process $E_t$, such that $0\leq E_t\leq\bar{E}$, which can be stored in a battery of finite size $\bar{B}$. We provide a simple and insightful formula for the approximate capacity of this channel with bounded guarantee on the approximation gap independent of system parameters. This approximate characterization of the capacity identifies two qualitatively different operating regimes for this channel: in the large battery regime, when $\bar{B}\geq \bar{E}$, the capacity is approximately equal to that of an AWGN channel with an average power constraint equal to the average energy harvesting rate, i.e. it depends only on the mean of $E_t$ and is (almost) independent of the distribution of $E_t$ and the exact value of $\bar{B}$. In particular, this suggests that a battery size $\bar{B}\approx\bar{E}$ is approximately sufficient to extract the infinite battery capacity of the system. In the small battery regime, when $\bar{B}<\bar{E}$, we clarify the dependence of the capacity on the distribution of $E_t$ and the value of $\bar{B}$. There are three steps to proving this result which can be of interest in their own right: 1) we characterize the capacity of this channel as an $n$-letter mutual information rate under various assumptions on the availability of energy arrival information; 2) we characterize the approximately optimal online power control policy that maximizes the long-term average throughput of the system; 3) we show that the information-theoretic capacity of this channel is equal, within a constant gap, to its long-term average throughput. This last result provides a connection between the information- and communication-theoretic formulations of the energy-harvesting communication problem that have been so far studied in isolation.
What's the Point: Semantic Segmentation with Point Supervision
Venue: arXiv cs.CV 2016
Year: 2016

The semantic image segmentation task presents a trade-off between test time accuracy and training-time annotation cost. Detailed per-pixel annotations enable training accurate models but are very time-consuming to obtain, image-level class labels are an order of magnitude cheaper but result in less accurate models. We take a natural step from image-level annotation towards stronger supervision: we ask annotators to point to an object if one exists. We incorporate this point supervision along with a novel objectness potential in the training loss function of a CNN model. Experimental results on the PASCAL VOC 2012 benchmark reveal that the combined effect of point-level supervision and objectness potential yields an improvement of 12.9% mIOU over image-level supervision. Further, we demonstrate that models trained with point-level supervision are more accurate than models trained with image-level, squiggle-level or full supervision given a fixed annotation budget.
A natural counting of lambda terms
Venue: arXiv cs.LO 2016
Year: 2016

We study the sequences of numbers corresponding to lambda terms of given sizes, where the size is this of lambda terms with de Bruijn indices in a very natural model where all the operators have size 1. For plain lambda terms, the sequence corresponds to two families of binary trees for which we exhibit bijections. We study also the distribution of normal forms, head normal forms and strongly normalizing terms. In particular we show that strongly normalizing terms are of density 0 among plain terms.
An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
Venue: arXiv cs.LG 2016
Year: 2016

We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be below some pre-fixed budget. The learning agent competes with an arbitrary set of context-dependent policies. This problem was introduced by Badanidiyuru et al. (2014), who gave a computationally inefficient algorithm with near-optimal regret bounds for it. We give a computationally efficient algorithm for this problem with slightly better regret bounds, by generalizing the approach of Agarwal et al. (2014) for the non-constrained version of the problem. The computational time of our algorithm scales logarithmically in the size of the policy space. This answers the main open question of Badanidiyuru et al. (2014). We also extend our results to a variant where there are no knapsack constraints but the objective is an arbitrary Lipschitz concave function of the sum of outcome vectors.
On the Prior Sensitivity of Thompson Sampling
Venue: arXiv cs.LG 2016
Year: 2016

The empirically successful Thompson Sampling algorithm for stochastic bandits has drawn much interest in understanding its theoretical properties. One important benefit of the algorithm is that it allows domain knowledge to be conveniently encoded as a prior distribution to balance exploration and exploitation more effectively. While it is generally believed that the algorithm's regret is low (high) when the prior is good (bad), little is known about the exact dependence. In this paper, we fully characterize the algorithm's worst-case dependence of regret on the choice of prior, focusing on a special yet representative case. These results also provide insights into the general sensitivity of the algorithm to the choice of priors. In particular, with $p$ being the prior probability mass of the true reward-generating model, we prove $O(\sqrt{T/p})$ and $O(\sqrt{(1-p)T})$ regret upper bounds for the bad- and good-prior cases, respectively, as well as \emph{matching} lower bounds. Our proofs rely on the discovery of a fundamental property of Thompson Sampling and make heavy use of martingale theory, both of which appear novel in the literature, to the best of our knowledge.
Aperiodic String Transducers
Venue: arXiv cs.FL 2016
Year: 2016

Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable functions. This result has recently been lifted to FO definable functions, with equivalent representations by means of aperiodic 2DFT and aperiodic 1-bounded SST, extending a well-known result on regular languages. In this paper, we give three direct transformations: i) from 1-bounded SST to 2DFT, ii) from 2DFT to copyless SST, and iii) from k-bounded to 1-bounded SST. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that FO definable string-to-string functions are equivalent to SST whose transition monoid is finite and aperiodic, and to aperiodic copyless SST.
Localized Multiple Kernel Learning---A Convex Approach
Venue: arXiv cs.LG 2016
Year: 2016

We propose a localized approach to multiple kernel learning that can be formulated as a convex optimization problem over a given cluster structure. For which we obtain generalization error guarantees and derive an optimization algorithm based on the Fenchel dual representation. Experiments on real-world datasets from the application domains of computational biology and computer vision show that convex localized multiple kernel learning can achieve higher prediction accuracies than its global and non-convex local counterparts.