OpenRaiser/Intern-Atlas huggingface dataset:
You, the Web and Your Device: Longitudinal Characterization of Browsing Habits
Venue: arXiv cs.CY 2021
Year: 2021

Understanding how people interact with the web is key for a variety of applications, e.g., from the design of effective web pages to the definition of successful online marketing campaigns. Browsing behavior has been traditionally represented and studied by means of clickstreams, i.e., graphs whose vertices are web pages, and edges are the paths followed by users. Obtaining large and representative data to extract clickstreams is however challenging. The evolution of the web questions whether browsing behavior is changing and, by consequence, whether properties of clickstreams are changing. This paper presents a longitudinal study of clickstreams in from 2013 to 2016. We evaluate an anonymized dataset of HTTP traces captured in a large ISP, where thousands of households are connected. We first propose a methodology to identify actual URLs requested by users from the massive set of requests automatically fired by browsers when rendering web pages. Then, we characterize web usage patterns and clickstreams, taking into account both the temporal evolution and the impact of the device used to explore the web. Our analyses precisely quantify various aspects of clickstreams and uncover interesting patterns, such as the typical short paths followed by people while navigating the web, the fast increasing trend in browsing from mobile devices and the different roles of search engines and social networks in promoting content. Finally, we contribute a dataset of anonymized clickstreams to the community to foster new studies (anonymized clickstreams are available to the public at http://bigdata.polito.it/clickstream).
Effective Divergence Analysis for Linear Recurrence Sequences
Venue: arXiv cs.CC 2021
Year: 2021

We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomial-time algorithm which takes as input a divergent rational linear recurrence sequence and computes effective fine-grained lower bounds on the growth rate of the sequence.
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
Venue: arXiv cs.DS 2021
Year: 2021

Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For $n$-vertex and $m$-edge graphs, the best known algorithms run in $\widetilde{O}(m\sqrt{n})$ time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) new (near-)linear-time data reduction rules for both the unweighted and the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementations for computing matchings in real-world graphs: the average speedup factor is 4.7 in the unweighted case and 12.72 in the weighted case.
Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms
Venue: arXiv cs.GT 2021
Year: 2021

We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with $n$ buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering the best of two simple pricing rules: one that imitates the revenue optimal mchanism, namely the Myersonian mechanism, via the taxation principle and the other that posts a uniform price. Our pricing rules are rather generalizable and yield the first improvement over long-established approximation factors in several settings. We design factor-revealing mathematical programs that crisply capture the approximation factor of our SPP mechanism. In the single-unit setting, our SPP mechanism yields a better approximation factor than the state of the art prior to our work (Azar, Chiplunkar & Kaplan, 2018). In the multi-unit setting, our SPP mechanism yields the first improved approximation factor over the state of the art after over nine years (Yan, 2011 and Chakraborty et al., 2010). Our results on SPP mechanisms immediately imply improved performance guarantees for the equivalent free-order prophet inequality problem. In the position auction setting, our SPP mechanism yields the first higher-than $1-1/e$ approximation factor. In eager second-price (ESP) auctions, our two simple pricing rules lead to the first improved approximation factor that is strictly greater than what is obtained by the SPP mechanism in the single-unit setting.
Optimal Algorithms for Right-Sizing Data Centers- Extended Version
Venue: arXiv cs.DS 2021
Year: 2021

Electricity cost is a dominant and rapidly growing expense in data centers. Unfortunately, much of the consumed energy is wasted because servers are idle for extended periods of time. We study a capacity management problem that dynamically right-sizes a data center, matching the number of active servers with the varying demand for computing capacity. We resort to a data-center optimization problem introduced by Lin, Wierman, Andrew and Thereska that, over a time horizon, minimizes a combined objective function consisting of operating cost, modeled by a sequence of convex functions, and server switching cost. All prior work addresses a continuous setting in which the number of active servers, at any time, may take a fractional value. In this paper, we investigate for the first time the discrete data-center optimization problem where the number of active servers, at any time, must be integer valued. Thereby we seek truly feasible solutions. First, we show that the offline problem can be solved in polynomial time. Second, we study the online problem and extend the algorithm {\em Lazy Capacity Provisioning\/} (LCP) by Lin et al. to the discrete setting. We prove that LCP is 3-competitive. Moreover, we show that no deterministic online algorithm can achieve a competitive ratio smaller than~3. In addition, we develop a randomized online algorithm that is 2-competitive against an oblivious adversary. Moreover, we prove that 2 is a lower bound for the competitive ratio of randomized online algorithms, so our algorithm is optimal. Finally, we address the continuous setting and give a lower bound of~2 on the best competitiveness of online algorithms. This matches an upper bound by Bansal et al. We prove that all lower bounds still hold in a problem variant with more restricted operating cost functions, introduced by Lin et al.
SySeVR: A Framework for Using Deep Learning to Detect Software Vulnerabilities
Venue: arXiv cs.LG 2021
Year: 2021

The detection of software vulnerabilities (or vulnerabilities for short) is an important problem that has yet to be tackled, as manifested by the many vulnerabilities reported on a daily basis. This calls for machine learning methods for vulnerability detection. Deep learning is attractive for this purpose because it alleviates the requirement to manually define features. Despite the tremendous success of deep learning in other application domains, its applicability to vulnerability detection is not systematically understood. In order to fill this void, we propose the first systematic framework for using deep learning to detect vulnerabilities in C/C++ programs with source code. The framework, dubbed Syntax-based, Semantics-based, and Vector Representations (SySeVR), focuses on obtaining program representations that can accommodate syntax and semantic information pertinent to vulnerabilities. Our experiments with 4 software products demonstrate the usefulness of the framework: we detect 15 vulnerabilities that are not reported in the National Vulnerability Database. Among these 15 vulnerabilities, 7 are unknown and have been reported to the vendors, and the other 8 have been "silently" patched by the vendors when releasing newer versions of the pertinent software products.
General Value Function Networks
Venue: arXiv cs.LG 2021
Year: 2021

State construction is important for learning in partially observable environments. A general purpose strategy for state construction is to learn the state update using a Recurrent Neural Network (RNN), which updates the internal state using the current internal state and the most recent observation. This internal state provides a summary of the observed sequence, to facilitate accurate predictions and decision-making. At the same time, specifying and training RNNs is notoriously tricky, particularly as the common strategy to approximate gradients back in time, called truncated Back-prop Through Time (BPTT), can be sensitive to the truncation window. Further, domain-expertise--which can usually help constrain the function class and so improve trainability--can be difficult to incorporate into complex recurrent units used within RNNs. In this work, we explore how to use multi-step predictions to constrain the RNN and incorporate prior knowledge. In particular, we revisit the idea of using predictions to construct state and ask: does constraining (parts of) the state to consist of predictions about the future improve RNN trainability? We formulate a novel RNN architecture, called a General Value Function Network (GVFN), where each internal state component corresponds to a prediction about the future represented as a value function. We first provide an objective for optimizing GVFNs, and derive several algorithms to optimize this objective. We then show that GVFNs are more robust to the truncation level, in many cases only requiring one-step gradient updates.
A Robust Color Edge Detection Algorithm Based on Quaternion Hardy Filter
Venue: arXiv cs.CV 2021
Year: 2021

This paper presents a robust filter called quaternion Hardy filter (QHF) for color image edge detection. The QHF can be capable of color edge feature enhancement and noise resistance. It is flexible to use QHF by selecting suitable parameters to handle different levels of noise. In particular, the quaternion analytic signal, which is an effective tool in color image processing, can also be produced by quaternion Hardy filtering with specific parameters. Based on the QHF and the improved Di Zenzo gradient operator, a novel color edge detection algorithm is proposed. Importantly, it can be efficiently implemented by using the fast discrete quaternion Fourier transform technique. From the experimental results, we conclude that the minimum PSNR improvement rate is 2.3% and minimum SSIM improvement rate is 30.2% on the Dataset 3. The experiments demonstrate that the proposed algorithm outperforms several widely used algorithms.
Removing Bias and Incentivizing Precision in Peer-grading
Venue: arXiv cs.GT 2021
Year: 2021

We study peer-grading with competitive graders who enjoy a higher utility when their peers get lower scores. We propose a new mechanism, PEQA, that incentivizes such graders through a score-assignment rule which aggregates the final score from multiple peer-evaluations, and a grading performance score that rewards performance in the peer-grading exercise. PEQA makes grader-bias irrelevant. Additionally, under PEQA, a peer-grader's utility increases monotonically with the reliability of her grading, irrespective of her competitiveness and how her co-graders act. In a reasonably general class of score assignment rules, PEQA uniquely satisfies this utility- reliability monotonicity. When grading is costly and costs are private information, a modified version of PEQA implements the socially optimal effort choices in an equilibrium of the peer-evaluation game. Data from our classroom experiments confirm our theoretical assumptions and show that PEQA outperforms the popular median mechanism.
Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information
Venue: arXiv cs.LG 2021
Year: 2021

This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a methodology to quickly predict expected tactical descriptions of operational solutions (TDOSs). The problem we address occurs in the context of two-stage stochastic programming where the second stage is demanding computationally. We aim to predict at a high speed the expected TDOS associated with the second stage problem, conditionally on the first stage variables. This may be used in support of the solution to the overall two-stage problem by avoiding the online generation of multiple second stage scenarios and solutions. We formulate the tactical prediction problem as a stochastic optimal prediction program, whose solution we approximate with supervised machine learning. The training dataset consists of a large number of deterministic operational problems generated by controlled probabilistic sampling. The labels are computed based on solutions to these problems (solved independently and offline), employing appropriate aggregation and subselection methods to address uncertainty. Results on our motivating application on load planning for rail transportation show that deep learning models produce accurate predictions in very short computing time (milliseconds or less). The predictive accuracy is close to the lower bounds calculated based on sample average approximation of the stochastic prediction programs.
On the Spanning and Routing Ratio of Directed Theta-Four
Venue: arXiv cs.CG 2021
Year: 2021

We present a routing algorithm for the directed $Θ_4$-graph, here denoted as the $\overrightarrow{Θ_4}}$-graph, that computes a path between any two vertices $s$ and $t$ having length at most $17$ times the Euclidean distance between $s$ and $t$. To compute this path, at each step, the algorithm only uses knowledge of the location of the current vertex, its (at most four) outgoing edges, the destination vertex, and one additional bit of information in order to determine the next edge to follow. This provides the first known online, local, competitive routing algorithm with constant routing ratio for the $Θ_4$-graph, as well as improving the best known upper bound on the spanning ratio of these graphs from $237$ to $17$. We also show that without this additional bit of information, the routing ratio increases to $\sqrt{290} \approx 17.03$.
Investigating the performance of multi-objective optimization when learning Bayesian Networks
Venue: arXiv cs.LG 2021
Year: 2021

Bayesian Networks have been widely used in the last decades in many fields, to describe statistical dependencies among random variables. In general, learning the structure of such models is a problem with considerable theoretical interest that poses many challenges. On the one hand, it is a well-known NP-complete problem, practically hardened by the huge search space of possible solutions. On the other hand, the phenomenon of I-equivalence, i.e., different graphical structures underpinning the same set of statistical dependencies, may lead to multimodal fitness landscapes further hindering maximum likelihood approaches to solve the task. In particular, we exploit the NSGA-II multi-objective optimization procedure in order to explicitly account for both the likelihood of a solution and the number of selected arcs, by setting these as the two objective functions of the method. The aim of this work is to investigate the behavior of NSGA-II and analyse the quality of its solutions. We thus thoroughly examined the optimization results obtained on a wide set of simulated data, by considering both the goodness of the inferred solutions in terms of the objective functions values achieved, and by comparing the retrieved structures with the ground truth, i.e., the networks used to generate the target data. Our results show that NSGA-II can converge to solutions characterized by better likelihood and less arcs than classic approaches, although paradoxically characterized in many cases by a lower similarity with the target network.
Effective Character-augmented Word Embedding for Machine Reading Comprehension
Venue: arXiv cs.CL 2021
Year: 2021

Machine reading comprehension is a task to model relationship between passage and query. In terms of deep learning framework, most of state-of-the-art models simply concatenate word and character level representations, which has been shown suboptimal for the concerned task. In this paper, we empirically explore different integration strategies of word and character embeddings and propose a character-augmented reader which attends character-level representation to augment word embedding with a short list to improve word representations, especially for rare words. Experimental results show that the proposed approach helps the baseline model significantly outperform state-of-the-art baselines on various public benchmarks.
NL4Py: Agent-Based Modeling in Python with Parallelizable NetLogo Workspaces
Venue: arXiv cs.MA 2021
Year: 2021

External control of agent-based models is vital for complex adaptive systems research. Often these experiments require vast numbers of simulation runs and are computationally expensive. NetLogo is the language of choice for most agent-based modelers but lacks direct API access through Python. NL4Py is a Python package for the parallel execution of NetLogo simulations via Python, designed for speed, scalability, and simplicity of use. NL4Py provides access to the large number of open-source machine learning and analytics libraries of Python and enables convenient and efficient parallelization of NetLogo simulations with minimal coding expertise by domain scientists.
Fast and Robust Matching for Multimodal Remote Sensing Image Registration
Venue: arXiv cs.CV 2021
Year: 2021

While image registration has been studied in remote sensing community for decades, registering multimodal data [e.g., optical, LiDAR, SAR, and map] remains a challenging problem because of significant nonlinear intensity differences between such data. To address this problem, this paper presents a fast and robust matching framework integrating local descriptors for multimodal registration. In the proposed framework, a local descriptor, such as Histogram of Oriented Gradient (HOG), Local Self Similarity (LSS), or Speeded-Up Robust Feature (SURF), is first extracted at each pixel to form a pixel-wise feature representation of an image. Then we define a similarity measure based on the feature representation in frequency domain using the 3 Dimensional Fast Fourier Transform (3DFFT) technique, followed by a template matching scheme to detect control points between images. In this procedure, we also propose a novel pixel-wise feature representation using orientated gradients of images, which is named channel features of orientated gradients (CFOG). This novel feature is an extension of the pixel-wise HOG descriptors, and outperforms that both in matching performance and computational efficiency. The major advantage of the proposed framework includes: (1) structural similarity representation using the pixel-wise feature description and (2) high computational efficiency due to the use of 3DFFT. Experimental results on different types of multimodal images show the superior matching performance of the proposed framework than the state-of-the-art methods.The proposed matching framework have been used in the software products of a Chinese listed company. The matlab code is available in this manuscript.
Linear Temporal Justification Logics with Past Operators
Venue: arXiv cs.LO 2021
Year: 2021

In this paper we present various temporal justification logics involving both past and future time modalities. We combine Artemov's logic of proofs with linear temporal logic (with both past and future operators), and establish its soundness and completeness. Then we investigate several principles describing the interaction of justification and time.
Bounds on the Error Probability of Raptor Codes under Maximum Likelihood Decoding
Venue: arXiv cs.IT 2021
Year: 2021

In this paper upper and lower bounds on the probability of decoding failure under maximum likelihood decoding are derived for different (nonbinary) Raptor code constructions. In particular four different constructions are considered; (i) the standard Raptor code construction, (ii) a multi-edge type construction, (iii) a construction where the Raptor code is nonbinary but the generator matrix of the LT code has only binary entries, (iv) a combination of (ii) and (iii). The latter construction resembles the one employed by RaptorQ codes, which at the time of writing this article represents the state of the art in fountain codes. The bounds are shown to be tight, and provide an important aid for the design of Raptor codes.
Quantum Algorithms for Structured Prediction
Venue: arXiv cs.LG 2021
Year: 2021

We introduce two quantum algorithms for solving structured prediction problems. We first show that a stochastic gradient descent that uses the quantum minimum finding algorithm and takes its probabilistic failure into account solves the structured prediction problem with a runtime that scales with the square root of the size of the label space, and in $\widetilde O\left(1/ε\right)$ with respect to the precision, $ε$, of the solution. Motivated by robust inference techniques in machine learning, we then introduce another quantum algorithm that solves a smooth approximation of the structured prediction problem with a similar quantum speedup in the size of the label space and a similar scaling in the precision parameter. In doing so, we analyze a variant of stochastic gradient descent for convex optimization in the presence of an additive error in the calculation of the gradients, and show that its convergence rate does not deteriorate if the additive errors are of the order $O(\sqrtε)$. This algorithm uses quantum Gibbs sampling at temperature $Ω(ε)$ as a subroutine. Based on these theoretical observations, we propose a method for using quantum Gibbs samplers to combine feedforward neural networks with probabilistic graphical models for quantum machine learning. Our numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.
Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms
Venue: arXiv cs.CR 2021
Year: 2021

Differential privacy is fast becoming the gold standard in enabling statistical analysis of data while protecting the privacy of individuals. However, practical use of differential privacy still lags behind research progress because research prototypes cannot satisfy the scalability requirements of production deployments. To address this challenge, we present Chorus, a framework for building scalable differential privacy mechanisms which is based on cooperation between the mechanism itself and a high-performance production database management system (DBMS). We demonstrate the use of Chorus to build the first highly scalable implementations of complex mechanisms like Weighted PINQ, MWEM, and the matrix mechanism. We report on our experience deploying Chorus at Uber, and evaluate its scalability on real-world queries.