OpenRaiser/Intern-Atlas huggingface dataset:
Studying a set of properties of inconsistency indices for pairwise comparisons
Venue: arXiv cs.AI 2016
Year: 2016

Pairwise comparisons between alternatives are a well-established tool to decompose decision problems into smaller and more easily tractable sub-problems. However, due to our limited rationality, the subjective preferences expressed by decision makers over pairs of alternatives can hardly ever be consistent. Therefore, several inconsistency indices have been proposed in the literature to quantify the extent of the deviation from complete consistency. Only recently, a set of properties has been proposed to define a family of functions representing inconsistency indices. The scope of this paper is twofold. Firstly, it expands the set of properties by adding and justifying a new one. Secondly, it continues the study of inconsistency indices to check whether or not they satisfy the above mentioned properties. Out of the four indices considered in this paper, in its present form, two fail to satisfy some properties. An adjusted version of one index is proposed so that it fulfills them.
Understanding the Detection of View Fraud in Video Content Portals
Venue: arXiv cs.CY 2016
Year: 2016

While substantial effort has been devoted to understand fraudulent activity in traditional online advertising (search and banner), more recent forms such as video ads have received little attention. The understanding and identification of fraudulent activity (i.e., fake views) in video ads for advertisers, is complicated as they rely exclusively on the detection mechanisms deployed by video hosting portals. In this context, the development of independent tools able to monitor and audit the fidelity of these systems are missing today and needed by both industry and regulators. In this paper we present a first set of tools to serve this purpose. Using our tools, we evaluate the performance of the audit systems of five major online video portals. Our results reveal that YouTube's detection system significantly outperforms all the others. Despite this, a systematic evaluation indicates that it may still be susceptible to simple attacks. Furthermore, we find that YouTube penalizes its videos' public and monetized view counters differently, the former being more aggressive. This means that views identified as fake and discounted from the public view counter are still monetized. We speculate that even though YouTube's policy puts in lots of effort to compensate users after an attack is discovered, this practice places the burden of the risk on the advertisers, who pay to get their ads displayed.
On the Displacement for Covering a Unit Interval with Randomly Placed Sensors
Venue: arXiv cs.DS 2016
Year: 2016

Consider $n$ mobile sensors placed independently at random with the uniform distribution on a barrier represented as the unit line segment $[0,1]$. The sensors have identical sensing radius, say $r$. When a sensor is displaced on the line a distance equal to $d$ it consumes energy (in movement) which is proportional to some (fixed) power $a > 0$ of the distance $d$ traveled. The energy consumption of a system of $n$ sensors thus displaced is defined as the sum of the energy consumptions for the displacement of the individual sensors. We focus on the problem of energy efficient displacement of the sensors so that in their final placement the sensor system ensures coverage of the barrier and the energy consumed for the displacement of the sensors to these final positions is minimized in expectation. In particular, we analyze the problem of displacing the sensors from their initial positions so as to attain coverage of the unit interval and derive trade-offs for this displacement as a function of the sensor range. We obtain several tight bounds in this setting thus generalizing several of the results of [10] to any power $a >0$.
Estimating Mutual Information by Local Gaussian Approximation
Venue: arXiv cs.IT 2016
Year: 2016

Estimating mutual information (MI) from samples is a fundamental problem in statistics, machine learning, and data analysis. Recently it was shown that a popular class of non-parametric MI estimators perform very poorly for strongly dependent variables and have sample complexity that scales exponentially with the true MI. This undesired behavior was attributed to the reliance of those estimators on local uniformity of the underlying (and unknown) probability density function. Here we present a novel semi-parametric estimator of mutual information, where at each sample point, densities are {\em locally} approximated by a Gaussians distribution. We demonstrate that the estimator is asymptotically unbiased. We also show that the proposed estimator has a superior performance compared to several baselines, and is able to accurately measure relationship strengths over many orders of magnitude.
Ergodic Energy Management Leveraging Resource Variability in Distribution Grids
Venue: arXiv cs.SY 2016
Year: 2016

Contemporary electricity distribution systems are being challenged by the variability of renewable energy sources. Slow response times and long energy management periods cannot efficiently integrate intermittent renewable generation and demand. Yet stochasticity can be judiciously coupled with system flexibilities to enhance grid operation efficiency. Voltage magnitudes for instance can transiently exceed regulation limits, while smart inverters can be overloaded over short time intervals. To implement such a mode of operation, an ergodic energy management framework is developed here. Considering a distribution grid with distributed energy sources and a feed-in tariff program, active power curtailment and reactive power compensation are formulated as a stochastic optimization problem. Tighter operational constraints are enforced in an average sense, while looser margins are enforced to be satisfied at all times. Stochastic dual subgradient solvers are developed based on exact and approximate grid models of varying complexity. Numerical tests on a real-world 56-bus distribution grid and the IEEE 123-bus test feeder relying on both grid models corroborate the advantages of the novel schemes over their deterministic alternatives.
Event-Trigger Based Robust-Optimal Control for Energy Harvesting Transmitter
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies an online algorithm for an energy harvesting transmitter, where the transmission (completion) time is considered as the system performance. Unlike the existing online algorithms which more or less require the knowledge on the future behavior of the energy-harvesting rate, we consider a practical but significantly more challenging scenario where the energy-harvesting rate is assumed to be totally unknown. Our design is formulated as a robust-optimal control problem which aims to optimize the worst-case performance. The transmit power is designed only based on the current battery energy level and the data queue length directly monitored by the transmitter itself. Specifically, we apply an event-trigger approach in which the transmitter continuously monitors the battery energy and triggers an event when a significant change occurs. Once an event is triggered, the transmit power is updated according to the solution to the robust-optimal control problem, which is given in a simple analytic form. We present numerical results on the transmission time achieved by the proposed design and demonstrate its robust-optimality.
Statistical Properties of Loss Rate Estimators in Tree Topology
Venue: arXiv cs.NI 2016
Year: 2016

Three types of explicit estimators are proposed here to estimate the loss rates of the links in a network of the tree topology. All of them are derived by the maximum likelihood principle and proved to be either asymptotic unbiased or unbiased. In addition, a set of formulae are derived to compute the efficiencies and variances of the estimators that also cover some of the estimators proposed previously. The formulae unveil that the variance of the estimates obtained by a maximum likelihood estimator for the pass rate of the root link of a multicast tree is equal to the variance of the pass rate of the multicast tree divided by the pass rate of the tree connected to the root link. Using the formulae, we are able to evaluate the estimators proposed so far and select an estimator for a data set.
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of non-preemptively scheduling $n$ jobs, each job $j$ with a release time $t_j$, a deadline $d_j$, and a processing time $p_j$, on $m$ parallel identical machines. Cieliebak et al. (2004) considered the two constraints $|d_j-t_j|\leq λp_j$ and $|d_j-t_j|\leq p_j +σ$ and showed the problem to be NP-hard for any $λ>1$ and for any $σ\geq 2$. We complement their results by parameterized complexity studies: we show that, for any $λ>1$, the problem remains weakly NP-hard even for $m=2$ and strongly W[1]-hard parameterized by $m$. We present a pseudo-polynomial-time algorithm for constant $m$ and $λ$ and a fixed-parameter tractability result for the parameter $m$ combined with $σ$.
Unconstrained Face Verification using Deep CNN Features
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present an algorithm for unconstrained face verification based on deep convolutional features and evaluate it on the newly released IARPA Janus Benchmark A (IJB-A) dataset. The IJB-A dataset includes real-world unconstrained faces from 500 subjects with full pose and illumination variations which are much harder than the traditional Labeled Face in the Wild (LFW) and Youtube Face (YTF) datasets. The deep convolutional neural network (DCNN) is trained using the CASIA-WebFace dataset. Extensive experiments on the IJB-A dataset are provided.
Capacity and Power Scaling Laws for Finite Antenna MIMO Amplify-and-Forward Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a novel framework that can be used to study the capacity and power scaling properties of linear multiple-input multiple-output (MIMO) $d\times d$ antenna amplify-and-forward (AF) relay networks. In particular, we model these networks as random dynamical systems (RDS) and calculate their $d$ Lyapunov exponents. Our analysis can be applied to systems with any per-hop channel fading distribution, although in this contribution we focus on Rayleigh fading. Our main results are twofold: 1) the total transmit power at the $n$th node will follow a deterministic trajectory through the network governed by the network's maximum Lyapunov exponent, 2) the capacity of the $i$th eigenchannel at the $n$th node will follow a deterministic trajectory through the network governed by the network's $i$th Lyapunov exponent. Before concluding, we concentrate on some applications of our results. In particular, we show how the Lyapunov exponents are intimately related to the rate at which the eigenchannel capacities diverge from each other, and how this relates to the amplification strategy and number of antennas at each relay. We also use them to determine the extra cost in power associated with each extra multiplexed data stream.
Vaporous Marketing: Uncovering Pervasive Electronic Cigarette Advertisements on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

Background: Twitter has become the "wild-west" of marketing and promotional strategies for advertisement agencies. Electronic cigarettes have been heavily marketed across Twitter feeds, offering discounts, "kid-friendly" flavors, algorithmically generated false testimonials, and free samples. Methods:All electronic cigarette keyword related tweets from a 10% sample of Twitter spanning January 2012 through December 2014 (approximately 850,000 total tweets) were identified and categorized as Automated or Organic by combining a keyword classification and a machine trained Human Detection algorithm. A sentiment analysis using Hedonometrics was performed on Organic tweets to quantify the change in consumer sentiments over time. Commercialized tweets were topically categorized with key phrasal pattern matching. Results:The overwhelming majority (80%) of tweets were classified as automated or promotional in nature. The majority of these tweets were coded as commercialized (83.65% in 2013), up to 33% of which offered discounts or free samples and appeared on over a billion twitter feeds as impressions. The positivity of Organic (human) classified tweets has decreased over time (5.84 in 2013 to 5.77 in 2014) due to a relative increase in the negative words ban,tobacco,doesn't,drug,against,poison,tax and a relative decrease in the positive words like haha,good,cool. Automated tweets are more positive than organic (6.17 versus 5.84) due to a relative increase in the marketing words best,win,buy,sale,health,discount and a relative decrease in negative words like bad, hate, stupid, don't. Conclusions:Due to the youth presence on Twitter and the clinical uncertainty of the long term health complications of electronic cigarette consumption, the protection of public health warrants scrutiny and potential regulation of social media marketing.
Improve the Evaluation of Fluency Using Entropy for Machine Translation Evaluation Metrics
Venue: arXiv cs.CL 2016
Year: 2016

The widely-used automatic evaluation metrics cannot adequately reflect the fluency of the translations. The n-gram-based metrics, like BLEU, limit the maximum length of matched fragments to n and cannot catch the matched fragments longer than n, so they can only reflect the fluency indirectly. METEOR, which is not limited by n-gram, uses the number of matched chunks but it does not consider the length of each chunk. In this paper, we propose an entropy-based method, which can sufficiently reflect the fluency of translations through the distribution of matched words. This method can easily combine with the widely-used automatic evaluation metrics to improve the evaluation of fluency. Experiments show that the correlations of BLEU and METEOR are improved on sentence level after combining with the entropy-based method on WMT 2010 and WMT 2012.
Energy Structure of Optimal Positional Strategies in Mean Payoff Games
Venue: arXiv cs.GT 2016
Year: 2016

This note studies structural aspects concerning Optimal Positional Strategies (OPSs) in Mean Payoff Games (MPGs), it is a contribution to understanding the relationship between OPSs in MPGs and Small Energy-Progress Measures (SEPMs) in reweighted Energy Games (EGs). Firstly, it is observed that the space of all OPSs, $\texttt{opt}_ΓΣ^M_0$, admits a unique complete decomposition in terms of so-called extremal-SEPM{s} in reweighted EG{s}; this points out what we called the "Energy-Lattice $\mathcal{X}^*_Γ$ of $\texttt{opt}_ΓΣ^M_0$". Secondly, it is offered a pseudo-polynomial total-time recursive procedure for enumerating (w/o repetitions) all the elements of $\mathcal{X}^*_Γ$, and for computing the corresponding partitioning of $\texttt{opt}_ΓΣ^M_0$. It is observed that the corresponding recursion tree defines an additional lattice $\mathcal{B}^*_Γ$, whose elements are certain subgames $Γ'\subseteq Γ$ that we call basic subgames. The extremal-SEPMs of a given \MPG $Γ$ coincide with the least-SEPMs of the basic subgames of $Γ$; so, $\mathcal{X}^*_Γ$ is the energy-lattice comprising all and only the least-SEPMs of the \emph{basic} subgames of $Γ$. The complexity of the proposed enumeration for both $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ is $O(|V|^3|E|W |\mathcal{B}^*_Γ|)$ total time and $O(|V||E|)+Θ\big(|E| \mathcal{B}^*_Γ|\big)$ working space. Finally, it is constructed an \MPG $Γ$ for which $|\mathcal{B}^*_Γ| > |\mathcal{X}^*_Γ|$, this proves that $\mathcal{B}^*_Γ$ and $\mathcal{X}^*_Γ$ are not isomorphic.
A novel sampling theorem on the rotation group
Venue: arXiv cs.IT 2016
Year: 2016

We develop a novel sampling theorem for functions defined on the three-dimensional rotation group SO(3) by connecting the rotation group to the three-torus through a periodic extension. Our sampling theorem requires $4L^3$ samples to capture all of the information content of a signal band-limited at $L$, reducing the number of required samples by a factor of two compared to other equiangular sampling theorems. We present fast algorithms to compute the associated Fourier transform on the rotation group, the so-called Wigner transform, which scale as $O(L^4)$, compared to the naive scaling of $O(L^6)$. For the common case of a low directional band-limit $N$, complexity is reduced to $O(N L^3)$. Our fast algorithms will be of direct use in speeding up the computation of directional wavelet transforms on the sphere. We make our SO3 code implementing these algorithms publicly available.
A Survey on Contextual Multi-armed Bandits
Venue: arXiv cs.LG 2016
Year: 2016

In this survey we cover a few stochastic and adversarial contextual bandit algorithms. We analyze each algorithm's assumption and regret bound.
Fuzzy Longest Common Subsequence Matching With FCM Using R
Venue: arXiv cs.AI 2016
Year: 2016

Capturing the interdependencies between real valued time series can be achieved by finding common similar patterns. The abstraction of time series makes the process of finding similarities closer to the way as humans do. Therefore, the abstraction by means of a symbolic levels and finding the common patterns attracts researchers. One particular algorithm, Longest Common Subsequence, has been used successfully as a similarity measure between two sequences including real valued time series. In this paper, we propose Fuzzy Longest Common Subsequence matching for time series.
Performance Studies of Underwater Wireless Optical Communication Systems with Spatial Diversity: MIMO Scheme
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we analytically study the performance of multiple-input multiple-output underwater wireless optical communication (MIMO UWOC) systems with on-off keying (OOK) modulation. To mitigate turbulence-induced fading, which is amongst the major degrading effects of underwater channels on the propagating optical signal, we use spatial diversity over UWOC links. Furthermore, the effects of absorption and scattering are considered in our analysis. We analytically obtain the exact and an upper bound bit error rate (BER) expressions for both optimal and equal gain combining. In order to more effectively calculate the system BER, we apply Gauss-Hermite quadrature formula as well as approximation to the sum of lognormal random variables. We also apply photon-counting method to evaluate the system BER in the presence of shot noise. Our numerical results indicate an excellent match between the exact and upper bound BER curves. Also {a good match} between {the} analytical results and numerical simulations confirms the accuracy of our derived expressions. Moreover, our results show that spatial diversity can considerably improve the system performance, especially for channels with higher turbulence, e.g., a $3\times1$ MISO transmission in a $25$ {m} coastal water link with log-amplitude variance of $0.16$ can introduce $8$ {dB} performance improvement at the BER of $10^{-9}$.
A Meta-graph Approach to Analyze Subgraph-centric Distributed Programming Models
Venue: arXiv cs.DC 2016
Year: 2016

Component-centric distributed graph processing platforms that use a bulk synchronous parallel (BSP) programming model have gained traction. These address the short-comings of Big Data abstractions/platforms like MapReduce/Hadoop for large-scale graph processing. However, there is limited literature on foundational aspects of the behavior of these component-centric abstractions for different graphs, graph partitioning, and graph algorithms. Here, we propose a analytical approach based on a meta-graph sketch to examine the characteristics of component-centric graph programming models at a coarse granularity. In particular, we apply this sketch to subgraph- and block-centric abstractions, and draw a comparison with vertex-centric models like Google's Pregel. First, we explore the impact of various graph partitioning techniques on the meta-graph, and next consider the impact of the meta-graph on graph algorithms. This decouples the unwieldy large graph and their partitioning specific artifacts from their algorithmic analysis. We use 5 spatial and powerlaw graphs as exemplars, four different partitioning strategies, and PageRank and Breadth First Search as canonical algorithms. These analysis over the meta-graphs provide a reliable measure of the expected number of supersteps, and the communication and computational complexity of the algorithms for various graphs, and the relative merits of subgraph-centric models over vertex-centric ones.
On the security of modern Single Sign-On Protocols: Second-Order Vulnerabilities in OpenID Connect
Venue: arXiv cs.CR 2016
Year: 2016

OAuth is the new de facto standard for delegating authorization in the web. An important limitation of OAuth is the fact that it was designed for authorization and not for authentication. The usage of OAuth for authentication thus leads to serious vulnerabilities as shown by Zhou et. al. in [44] and Chen et. al. in [9]. OpenID Connect was created on top of OAuth to fill this gap by providing federated identity management and user authentication. OpenID Connect was standardized in February 2014, but leading companies like Google, Microsoft, AOL and PayPal are already using it in their web applications [1], [2], [3], [30]. In this paper we describe the OpenID Connect protocol and provide the first in-depth analysis of one of the key features of OpenID Connect: the Discovery and the Dynamic Registration extensions.We present a new class of attacks on OpenID Connect that belong to the category of second-order vulnerabilities. These attacks consist of two phases: First, the injection payload is stored by the legitimate application. Later on, this payload is used in a security-critical operation. Our new class of attacks - called Malicious Endpoints attacks - exploits the OpenID Connect extensions Discovery and Dynamic Registration. These attacks break user authentication, compromise user privacy, and enable Server Side Request Forgery (SSRF), client-side code injection, and Denial-of-Service (DoS). As a result, the security of the OpenID Connect protocol cannot be guaranteed when these extensions are enabled in their present form. We contacted the authors of the OpenID Connect and OAuth specifications. They acknowledged our Malicious Endpoint attacks and recognized the need to improve the specification [29]. We are currently involved in the discussion regarding the mitigation of the existing issues and an extension to the OAuth specification.