OpenRaiser/Intern-Atlas huggingface dataset:
Lyndon Words, the Three Squares Lemma, and Primitive Squares
Venue: arXiv cs.DM 2020
Year: 2020

We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which considers three overlapping squares which do not necessarily share a common prefix. We also give an improved upper bound of $n\log_2 n$ on the maximum number of (occurrences of) primitively rooted squares in a string of length $n$, also using arguments based on Lyndon words. To the best of our knowledge, the only known upper bound was $n \log_ϕn \approx 1.441n\log_2 n$, where $ϕ$ is the golden ratio, reported by Fraenkel and Simpson [TCS 1999] obtained via the Three Squares Lemma.
Unifying Optimization Methods for Color Filter Design
Venue: arXiv cs.CV 2020
Year: 2020

Through optimization we can solve for a filter that when the camera views the world through this filter, it is more colorimetric. Previous work solved for the filter that best satisfied the Luther condition: the camera spectral sensitivities after filtering were approximately a linear transform from the CIE XYZ color matching functions. A more recent method optimized for the filter that maximized the Vora-Value (a measure which relates to the closeness of the vector spaces spanned by the camera sensors and human vision sensors). The optimized Luther- and Vora-filters are different from one another. In this paper we begin by observing that the function defining the Vora-Value is equivalent to the Luther-condition optimization if we use the orthonormal basis of the XYZ color matching functions, i.e. we linearly transform the XYZ sensitivities to a set of orthonormal basis. In this formulation, the Luther-optimization algorithm is shown to almost optimize the Vora-Value. Moreover, experiments demonstrate that the modified orthonormal Luther-method finds the same color filter compared to the Vora-Value filter optimization. Significantly, our modified algorithm is simpler in formulation and also converges faster than the direct Vora-Value method.
On the Empirical Neural Tangent Kernel of Standard Finite-Width Convolutional Neural Network Architectures
Venue: arXiv cs.LG 2020
Year: 2020

The Neural Tangent Kernel (NTK) is an important milestone in the ongoing effort to build a theory for deep learning. Its prediction that sufficiently wide neural networks behave as kernel methods, or equivalently as random feature models, has been confirmed empirically for certain wide architectures. It remains an open question how well NTK theory models standard neural network architectures of widths common in practice, trained on complex datasets such as ImageNet. We study this question empirically for two well-known convolutional neural network architectures, namely AlexNet and LeNet, and find that their behavior deviates significantly from their finite-width NTK counterparts. For wider versions of these networks, where the number of channels and widths of fully-connected layers are increased, the deviation decreases.
Improved Circular $k$-Mismatch Sketches
Venue: arXiv cs.DS 2020
Year: 2020

The shift distance $\mathsf{sh}(S_1,S_2)$ between two strings $S_1$ and $S_2$ of the same length is defined as the minimum Hamming distance between $S_1$ and any rotation (cyclic shift) of $S_2$. We study the problem of sketching the shift distance, which is the following communication complexity problem: Strings $S_1$ and $S_2$ of length $n$ are given to two identical players (encoders), who independently compute sketches (summaries) $\mathtt{sk}(S_1)$ and $\mathtt{sk}(S_2)$, respectively, so that upon receiving the two sketches, a third player (decoder) is able to compute (or approximate) $\mathsf{sh}(S_1,S_2)$ with high probability. This paper primarily focuses on the more general $k$-mismatch version of the problem, where the decoder is allowed to declare a failure if $\mathsf{sh}(S_1,S_2)>k$, where $k$ is a parameter known to all parties. Andoni et al. (STOC'13) introduced exact circular $k$-mismatch sketches of size $\widetilde{O}(k+D(n))$, where $D(n)$ is the number of divisors of $n$. Andoni et al. also showed that their sketch size is optimal in the class of linear homomorphic sketches. We circumvent this lower bound by designing a (non-linear) exact circular $k$-mismatch sketch of size $\widetilde{O}(k)$; this size matches communication-complexity lower bounds. We also design $(1\pm \varepsilon)$-approximate circular $k$-mismatch sketch of size $\widetilde{O}(\min(\varepsilon^{-2}\sqrt{k}, \varepsilon^{-1.5}\sqrt{n}))$, which improves upon an $\widetilde{O}(\varepsilon^{-2}\sqrt{n})$-size sketch of Crouch and McGregor (APPROX'11).
How do Agile Software Startups deal with uncertainties by Covid-19 pandemic?
Venue: arXiv cs.SE 2020
Year: 2020

The dissipation of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has already taken on pandemic proportions, affecting over 100 countries in a couple of weeks. The evolution of the disease and its economic impact is highly uncertain, which brings challenges for newly created software companies. Software startups are companies that create innovative software products and services in a dynamic and fast-growing market. Agile Software Methods aims to enable startups in responding to uncertainty caused by Covid-19. This paper investigates the impact of Covid-19 in a real software startup context to understand how they have reacted against uncertainties caused by Covid-19. As a research methodology, action research within Di2Win, a Brazilian software startup, has been applied. The study was carried out throughout six sprints, during the quarantine. Practices employed to mitigate threats while simultaneously allowing teams to remain open to opportunities and challenges are detailed. This paper shares lessons learned that could help agile software startups improve their way of work in an uncertain environment caused by the Covid-19 pandemic.
Dynamic of Stochastic Gradient Descent with State-Dependent Noise
Venue: arXiv cs.LG 2020
Year: 2020

Stochastic gradient descent (SGD) and its variants are mainstream methods to train deep neural networks. Since neural networks are non-convex, more and more works study the dynamic behavior of SGD and the impact to its generalization, especially the escaping efficiency from local minima. However, these works take the over-simplified assumption that the covariance of the noise in SGD is (or can be upper bounded by) constant, although it is actually state-dependent. In this work, we conduct a formal study on the dynamic behavior of SGD with state-dependent noise. Specifically, we show that the covariance of the noise of SGD in the local region of the local minima is a quadratic function of the state. Thus, we propose a novel power-law dynamic with state-dependent diffusion to approximate the dynamic of SGD. We prove that, power-law dynamic can escape from sharp minima exponentially faster than flat minima, while the previous dynamics can only escape sharp minima polynomially faster than flat minima. Our experiments well verified our theoretical results. Inspired by our theory, we propose to add additional state-dependent noise into (large-batch) SGD to further improve its generalization ability. Experiments verify that our method is effective.
DeepAbstract: Neural Network Abstraction for Accelerating Verification
Venue: arXiv cs.LO 2020
Year: 2020

While abstraction is a classic tool of verification to scale it up, it is not used very often for verifying neural networks. However, it can help with the still open task of scaling existing algorithms to state-of-the-art network architectures. We introduce an abstraction framework applicable to fully-connected feed-forward neural networks based on clustering of neurons that behave similarly on some inputs. For the particular case of ReLU, we additionally provide error bounds incurred by the abstraction. We show how the abstraction reduces the size of the network, while preserving its accuracy, and how verification results on the abstract network can be transferred back to the original network.
A Parameterized Family of Meta-Submodular Functions
Venue: arXiv cs.DS 2020
Year: 2020

Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular minimization) also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems. We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. Functions in this parameterized family are called \emph{$γ$-meta-submodular}. We develop local search algorithms with approximation factors that depend only on the parameter $γ$. We show that the $γ$-meta-submodular families include well-known classes of functions such as meta-submodular functions ($γ=0$), metric diversity functions and proportionally submodular functions (both with $γ=1$), diversity functions based on negative-type distances or Jensen-Shannon divergence (both with $γ=2$), and $σ$-semi metric diversity functions ($γ= σ$).
Competitive Balance in Team Sports Games
Venue: arXiv cs.SI 2020
Year: 2020

Competition is a primary driver of player satisfaction and engagement in multiplayer online games. Traditional matchmaking systems aim at creating matches involving teams of similar aggregated individual skill levels, such as Elo score or TrueSkill. However, team dynamics cannot be solely captured using such linear predictors. Recently, it has been shown that nonlinear predictors that target to learn probability of winning as a function of player and team features significantly outperforms these linear skill-based methods. In this paper, we show that using final score difference provides yet a better prediction metric for competitive balance. We also show that a linear model trained on a carefully selected set of team and individual features achieves almost the performance of the more powerful neural network model while offering two orders of magnitude inference speed improvement. This shows significant promise for implementation in online matchmaking systems.
Lattice Representation Learning
Venue: arXiv cs.LG 2020
Year: 2020

In this article we introduce theory and algorithms for learning discrete representations that take on a lattice that is embedded in an Euclidean space. Lattice representations possess an interesting combination of properties: a) they can be computed explicitly using lattice quantization, yet they can be learned efficiently using the ideas we introduce in this paper, b) they are highly related to Gaussian Variational Autoencoders, allowing designers familiar with the latter to easily produce discrete representations from their models and c) since lattices satisfy the axioms of a group, their adoption can lead into a way of learning simple algebras for modeling binary operations between objects through symbolic formalisms, yet learn these structures also formally using differentiation techniques. This article will focus on laying the groundwork for exploring and exploiting the first two properties, including a new mathematical result linking expressions used during training and inference time and experimental validation on two popular datasets.
DeepTracking-Net: 3D Tracking with Unsupervised Learning of Continuous Flow
Venue: arXiv cs.CV 2020
Year: 2020

This paper deals with the problem of 3D tracking, i.e., to find dense correspondences in a sequence of time-varying 3D shapes. Despite deep learning approaches have achieved promising performance for pairwise dense 3D shapes matching, it is a great challenge to generalize those approaches for the tracking of 3D time-varying geometries. In this paper, we aim at handling the problem of 3D tracking, which provides the tracking of the consecutive frames of 3D shapes. We propose a novel unsupervised 3D shape registration framework named DeepTracking-Net, which uses the deep neural networks (DNNs) as auxiliary functions to produce spatially and temporally continuous displacement fields for 3D tracking of objects in a temporal order. Our key novelty is that we present a novel temporal-aware correspondence descriptor (TCD) that captures spatio-temporal essence from consecutive 3D point cloud frames. Specifically, our DeepTracking-Net starts with optimizing a randomly initialized latent TCD. The TCD is then decoded to regress a continuous flow (i.e. a displacement vector field) which assigns a motion vector to every point of time-varying 3D shapes. Our DeepTracking-Net jointly optimizes TCDs and DNNs' weights towards the minimization of an unsupervised alignment loss. Experiments on both simulated and real data sets demonstrate that our unsupervised DeepTracking-Net outperforms the current supervised state-of-the-art method. In addition, we prepare a new synthetic 3D data, named SynMotions, to the 3D tracking and recognition community.
Community-Based Data Integration of Course and Job Data in Support of Personalized Career-Education Recommendations
Venue: arXiv cs.IR 2020
Year: 2020

How does your education impact your professional career? Ideally, the courses you take help you identify, get hired for, and perform the job you always wanted. However, not all courses provide skills that transfer to existing and future jobs; skill terms used in course descriptions might be different from those listed in job advertisements; and there might exist a considerable skill gap between what is taught in courses and what is needed for a job. In this study, we propose a novel method to integrate extensive course description and job advertisement data by leveraging heterogeneous data integration and community detection. The innovative heterogeneous graph approach along with identified skill communities enables cross-domain information recommendation, e.g., given an educational profile, job recommendations can be provided together with suggestions on education opportunities for re- and upskilling in support of lifelong learning.
Freely scalable and reconfigurable optical hardware for deep learning
Venue: arXiv cs.ET 2020
Year: 2020

As deep neural network (DNN) models grow ever-larger, they can achieve higher accuracy and solve more complex problems. This trend has been enabled by an increase in available compute power; however, efforts to continue to scale electronic processors are impeded by the costs of communication, thermal management, power delivery and clocking. To improve scalability, we propose a digital optical neural network (DONN) with intralayer optical interconnects and reconfigurable input values. The near path-length-independence of optical energy consumption enables information locality between a transmitter and arbitrarily arranged receivers, which allows greater flexibility in architecture design to circumvent scaling limitations. In a proof-of-concept experiment, we demonstrate optical multicast in the classification of 500 MNIST images with a 3-layer, fully-connected network. We also analyze the energy consumption of the DONN and find that optical data transfer is beneficial over electronics when the spacing of computational units is on the order of >10 micrometers.
Circumvention by design -- dark patterns in cookie consents for online news outlets
Venue: arXiv cs.HC 2020
Year: 2020

To ensure that users of online services understand what data are collected and how they are used in algorithmic decision-making, the European Union's General Data Protection Regulation (GDPR) specifies informed consent as a minimal requirement. For online news outlets consent is commonly elicited through interface design elements in the form of a pop-up. We have manually analyzed 300 data collection consent notices from news outlets that are built to ensure compliance with GDPR. The analysis uncovered a variety of strategies or dark patterns that circumvent the intent of GDPR by design. We further study the presence and variety of these dark patterns in these "cookie consents" and use our observations to specify the concept of dark pattern in the context of consent elicitation.
WikipediaBot: Automated Adversarial Manipulation of Wikipedia Articles
Venue: arXiv cs.CR 2020
Year: 2020

This paper presents an automated adversarial mechanism called WikipediaBot. WikipediaBot allows an adversary to create and control a bot infrastructure for the purpose of adversarial edits of Wikipedia articles. The WikipediaBot is a self-contained mechanism with modules for generating credentials for Wikipedia editors, bypassing login protections, and a production of contextually-relevant adversarial edits for target Wikipedia articles that evade conventional detection. The contextually-relevant adversarial edits are generated using an adversarial Markov chain that incorporates a linguistic manipulation attack known as MIM or malware-induced misperceptions. Because the nefarious use of WikipediaBot could result in harmful damages to the integrity of wide range of Wikipedia articles, we provide an elaborate discussion about the implications, detection, and defenses Wikipedia could employ to address the threat of automated adversarial manipulations and acts of Wikipedia vandalism.
Bi-Level Graph Neural Networks for Drug-Drug Interaction Prediction
Venue: arXiv cs.CE 2020
Year: 2020

We introduce Bi-GNN for modeling biological link prediction tasks such as drug-drug interaction (DDI) and protein-protein interaction (PPI). Taking drug-drug interaction as an example, existing methods using machine learning either only utilize the link structure between drugs without using the graph representation of each drug molecule, or only leverage the individual drug compound structures without using graph structure for the higher-level DDI graph. The key idea of our method is to fundamentally view the data as a bi-level graph, where the highest level graph represents the interaction between biological entities (interaction graph), and each biological entity itself is further expanded to its intrinsic graph representation (representation graphs), where the graph is either flat like a drug compound or hierarchical like a protein with amino acid level graph, secondary structure, tertiary structure, etc. Our model not only allows the usage of information from both the high-level interaction graph and the low-level representation graphs, but also offers a baseline for future research opportunities to address the bi-level nature of the data.
Discrepancy Minimization via a Self-Balancing Walk
Venue: arXiv cs.DS 2020
Year: 2020

We study discrepancy minimization for vectors in $\mathbb{R}^n$ under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms for logarithmic bounds for the Komlós conjecture.
Raising Expectations: Automating Expected Cost Analysis with Types
Venue: arXiv cs.PL 2020
Year: 2020

This article presents a type-based analysis for deriving upper bounds on the expected execution cost of probabilistic programs. The analysis is naturally compositional, parametric in the cost model, and supports higher order functions and inductive data types. The derived bounds are multivariate polynomials that are functions of data structures. Bound inference is enabled by local type rules that reduce type inference to linear constraint solving. The type system is based on the potential method of amortized analysis and extends automatic amortized resource analysis (AARA) for deterministic programs. A main innovation is that bounds can contain symbolic probabilities, which may appear in data structures and function arguments. Another contribution is a novel soundness proof that establishes the correctness of the derived bounds with respect to a distribution-based operational cost semantics that also includes nontrivial diverging behavior. For cost models like time, derived bounds imply termination with probability one. To highlight the novel ideas, the presentation focuses on linear potential and a core language. However, the analysis is implemented as an extension of Resource Aware ML and supports polynomial bounds and user defined data structures. The effectiveness of the technique is evaluated by analyzing the sample complexity of discrete distributions and with a novel average-case estimation for deterministic programs that combines expected cost analysis with statistical methods.
A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
Venue: arXiv cs.DS 2020
Year: 2020

Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of $P$. Previously, the "continuous" version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our "discrete" version of the problem has not been studied before. We present a linear-time algorithm for the problem.
On Lyapunov Exponents for RNNs: Understanding Information Propagation Using Dynamical Systems Tools
Venue: arXiv cs.LG 2020
Year: 2020

Recurrent neural networks (RNNs) have been successfully applied to a variety of problems involving sequential data, but their optimization is sensitive to parameter initialization, architecture, and optimizer hyperparameters. Considering RNNs as dynamical systems, a natural way to capture stability, i.e., the growth and decay over long iterates, are the Lyapunov Exponents (LEs), which form the Lyapunov spectrum. The LEs have a bearing on stability of RNN training dynamics because forward propagation of information is related to the backward propagation of error gradients. LEs measure the asymptotic rates of expansion and contraction of nonlinear system trajectories, and generalize stability analysis to the time-varying attractors structuring the non-autonomous dynamics of data-driven RNNs. As a tool to understand and exploit stability of training dynamics, the Lyapunov spectrum fills an existing gap between prescriptive mathematical approaches of limited scope and computationally-expensive empirical approaches. To leverage this tool, we implement an efficient way to compute LEs for RNNs during training, discuss the aspects specific to standard RNN architectures driven by typical sequential datasets, and show that the Lyapunov spectrum can serve as a robust readout of training stability across hyperparameters. With this exposition-oriented contribution, we hope to draw attention to this understudied, but theoretically grounded tool for understanding training stability in RNNs.
Estimating Asset Class Health Indices in Power Systems
Venue: arXiv cs.CE 2020
Year: 2020

Power systems have widely adopted the concept of health index to describe asset health statuses and choose proper asset management actions. The existing application and research works have been focused on determining the current or near-future asset health index based on the current condition data. For preventative asset management, it is highly desirable to estimate asset health indices, especially for asset classes in which the assets share similar electrical and/or mechanical characteristics. This important problem has not been sufficiently addressed. This paper proposes a sequence learning based method to estimate health indices for power asset classes. A comprehensive data-driven method based on sequence learning is presented and solid tests are conducted based on real utility data. The proposed method revealed superior performance with comparison to other Estimation methods.