OpenRaiser/Intern-Atlas huggingface dataset:
PGLP: Customizable and Rigorous Location Privacy through Policy Graph
Venue: arXiv cs.CR 2020
Year: 2020

Location privacy has been extensively studied in the literature. However, existing location privacy models are either not rigorous or not customizable, which limits the trade-off between privacy and utility in many real-world applications. To address this issue, we propose a new location privacy notion called PGLP, i.e., \textit{Policy Graph based Location Privacy}, providing a rich interface to release private locations with customizable and rigorous privacy guarantee. First, we design the privacy metrics of PGLP by extending differential privacy. Specifically, we formalize a user's location privacy requirements using a \textit{location policy graph}, which is expressive and customizable. Second, we investigate how to satisfy an arbitrarily given location policy graph under adversarial knowledge. We find that a location policy graph may not always be viable and may suffer \textit{location exposure} when the attacker knows the user's mobility pattern. We propose efficient methods to detect location exposure and repair the policy graph with optimal utility. Third, we design a private location trace release framework that pipelines the detection of location exposure, policy graph repair, and private trajectory release with customizable and rigorous location privacy. Finally, we conduct experiments on real-world datasets to verify the effectiveness of the privacy-utility trade-off and the efficiency of the proposed algorithms.
Rational Solutions of First Order Algebraic Ordinary Differential Equations
Venue: arXiv cs.SC 2020
Year: 2020

Let $f(t, y,y')=\sum_{i=0}^d a_i(t, y)y'^i=0$ be a first order ordinary differential equation with polynomial coefficients. Eremenko in 1999 proved that there exists a constant $C$ such that every rational solution of $f(t, y,y')=0$ is of degree not greater than $C$. Examples show that this degree bound $C$ depends not only on the degrees of $f$ in $t,y,y'$ but also on the coefficients of $f$ viewed as polynomial in $t,y,y'$. In this paper, we show that if $$\max_{i=0}^d \{{\rm deg}(a_i,y)-2(d-i)\}>0 $$ then the degree bound $C$ only depends on the degrees of $f$, and furthermore we present an explicit expression for $C$ in terms of the degrees of $f$.
Intelligent Reflecting Surface Assisted Multi-User MISO Communication: Channel Estimation and Beamforming Design
Venue: arXiv cs.IT 2020
Year: 2020

The concept of reconfiguring wireless propagation environments using intelligent reflecting surfaces (IRS)s has recently emerged, where an IRS comprises of a large number of passive reflecting elements that can smartly reflect the impinging electromagnetic waves for performance enhancement. Previous works have shown promising gains assuming the availability of perfect channel state information (CSI) at the base station (BS) and the IRS, which is impractical due to the passive nature of the reflecting elements. This paper makes one of the preliminary contributions of studying an IRS-assisted multi-user multiple-input single-output (MISO) communication system under imperfect CSI. Different from the few recent works that develop least-squares (LS) estimates of the IRS-assisted channel vectors, we exploit the prior knowledge of the large-scale fading statistics at the BS to derive the Bayesian minimum mean squared error (MMSE) channel estimates under a protocol in which the IRS applies a set of optimal phase shifts vectors over multiple channel estimation sub-phases. The resulting mean squared error (MSE) is both analytically and numerically shown to be lower than that achieved by the LS estimates. Joint designs for the precoding and power allocation at the BS and reflect beamforming at the IRS are proposed to maximize the minimum user signal-to-interference-plus-noise ratio (SINR) subject to a transmit power constraint. Performance evaluation results illustrate the efficiency of the proposed system and study its susceptibility to channel estimation errors.
NLP in FinTech Applications: Past, Present and Future
Venue: arXiv cs.CL 2020
Year: 2020

Financial Technology (FinTech) is one of the worldwide rapidly-rising topics in the past five years according to the statistics of FinTech from Google Trends. In this position paper, we focus on the researches applying natural language processing (NLP) technologies in the finance domain. Our goal is to indicate the position we are now and provide the blueprint for future researches. We go through the application scenarios from three aspects including Know Your Customer (KYC), Know Your Product (KYP), and Satisfy Your Customer (SYC). Both formal documents and informal textual data are analyzed to understand corporate customers and personal customers. Furthermore, we talk over how to dynamically update the features of products from the prospect and the risk points of view. Finally, we discuss satisfying the customers in both B2C and C2C business models. After summarizing the past and the recent challenges, we highlight several promising future research directions in the trend of FinTech and the open finance tendency.
Register transducers are marble transducers
Venue: arXiv cs.FL 2020
Year: 2020

Deterministic two-way transducers define the class of regular functions from words to words. Alur and Cerný introduced an equivalent model of transducers with registers called copyless streaming string transducers. In this paper, we drop the "copyless" restriction on these machines and show that they are equivalent to two-way transducers enhanced with the ability to drop marks, named "marbles", on the input. We relate the maximal number of marbles used with the amount of register copies performed by the streaming string transducer. Finally, we show that the class membership problems associated with these models are decidable. Our results can be interpreted in terms of program optimization for simple recursive and iterative programs.
Palindromic Length of Words with Many Periodic Palindromes
Venue: arXiv cs.FL 2020
Year: 2020

The palindromic length $\text{PL}(v)$ of a finite word $v$ is the minimal number of palindromes whose concatenation is equal to $v$. In 2013, Frid, Puzynina, and Zamboni conjectured that: If $w$ is an infinite word and $k$ is an integer such that $\text{PL}(u)\leq k$ for every factor $u$ of $w$ then $w$ is ultimately periodic. Suppose that $w$ is an infinite word and $k$ is an integer such $\text{PL}(u)\leq k$ for every factor $u$ of $w$. Let $Ω(w,k)$ be the set of all factors $u$ of $w$ that have more than $\sqrt[k]{k^{-1}\vert u\vert}$ palindromic prefixes. We show that $Ω(w,k)$ is an infinite set and we show that for each positive integer $j$ there are palindromes $a,b$ and a word $u\in Ω(w,k)$ such that $(ab)^j$ is a factor of $u$ and $b$ is nonempty. Note that $(ab)^j$ is a periodic word and $(ab)^ia$ is a palindrome for each $i\leq j$. These results justify the following question: What is the palindromic length of a concatenation of a suffix of $b$ and a periodic word $(ab)^j$ with "many" periodic palindromes? It is known that $\lvert\text{PL}(uv)-\text{PL}(u)\rvert\leq \text{PL}(v)$, where $u$ and $v$ are nonempty words. The main result of our article shows that if $a,b$ are palindromes, $b$ is nonempty, $u$ is a nonempty suffix of $b$, $\vert ab\vert$ is the minimal period of $aba$, and $j$ is a positive integer with $j\geq3\text{PL}(u)$ then $\text{PL}(u(ab)^j)-\text{PL}(u)\geq 0$.
Hierarchical Decomposition of Nonlinear Dynamics and Control for System Identification and Policy Distillation
Venue: arXiv cs.LG 2020
Year: 2020

The control of nonlinear dynamical systems remains a major challenge for autonomous agents. Current trends in reinforcement learning (RL) focus on complex representations of dynamics and policies, which have yielded impressive results in solving a variety of hard control tasks. However, this new sophistication and extremely over-parameterized models have come with the cost of an overall reduction in our ability to interpret the resulting policies. In this paper, we take inspiration from the control community and apply the principles of hybrid switching systems in order to break down complex dynamics into simpler components. We exploit the rich representational power of probabilistic graphical models and derive an expectation-maximization (EM) algorithm for learning a sequence model to capture the temporal structure of the data and automatically decompose nonlinear dynamics into stochastic switching linear dynamical systems. Moreover, we show how this framework of switching models enables extracting hierarchies of Markovian and auto-regressive locally linear controllers from nonlinear experts in an imitation learning scenario.
Estimating Silent Data Corruption Rates Using a Two-Level Model
Venue: arXiv cs.DC 2020
Year: 2020

High-performance and safety-critical system architects must accurately evaluate the application-level silent data corruption (SDC) rates of processors to soft errors. Such an evaluation requires error propagation all the way from particle strikes on low-level state up to the program output. Existing approaches that rely on low-level simulations with fault injection cannot evaluate full applications because of their slow speeds, while application-level accelerated fault testing in accelerated particle beams is often impractical. We present a new two-level methodology for application resilience evaluation that overcomes these challenges. The proposed approach decomposes application failure rate estimation into (1) identifying how particle strikes in low-level unprotected state manifest at the architecture-level, and (2) measuring how such architecture-level manifestations propagate to the program output. We demonstrate the effectiveness of this approach on GPU architectures. We also show that using just one of the two steps can overestimate SDC rates and produce different trends---the composition of the two is needed for accurate reliability modeling.
An Environment for Sustainable Research Software in Germany and Beyond: Current State, Open Challenges, and Call for Action
Venue: arXiv cs.GL 2020
Year: 2020

Research software has become a central asset in academic research. It optimizes existing and enables new research methods, implements and embeds research knowledge, and constitutes an essential research product in itself. Research software must be sustainable in order to understand, replicate, reproduce, and build upon existing research or conduct new research effectively. In other words, software must be available, discoverable, usable, and adaptable to new needs, both now and in the future. Research software therefore requires an environment that supports sustainability. Hence, a change is needed in the way research software development and maintenance are currently motivated, incentivized, funded, structurally and infrastructurally supported, and legally treated. Failing to do so will threaten the quality and validity of research. In this paper, we identify challenges for research software sustainability in Germany and beyond, in terms of motivation, selection, research software engineering personnel, funding, infrastructure, and legal aspects. Besides researchers, we specifically address political and academic decision-makers to increase awareness of the importance and needs of sustainable research software practices. In particular, we recommend strategies and measures to create an environment for sustainable research software, with the ultimate goal to ensure that software-driven research is valid, reproducible and sustainable, and that software is recognized as a first class citizen in research. This paper is the outcome of two workshops run in Germany in 2019, at deRSE19 - the first International Conference of Research Software Engineers in Germany - and a dedicated DFG-supported follow-up workshop in Berlin.
A Machine Learning based Framework for KPI Maximization in Emerging Networks using Mobility Parameters
Venue: arXiv cs.NI 2020
Year: 2020

Current LTE network is faced with a plethora of Configuration and Optimization Parameters (COPs), both hard and soft, that are adjusted manually to manage the network and provide better Quality of Experience (QoE). With 5G in view, the number of these COPs are expected to reach 2000 per site, making their manual tuning for finding the optimal combination of these parameters, an impossible fleet. Alongside these thousands of COPs is the anticipated network densification in emerging networks which exacerbates the burden of the network operators in managing and optimizing the network. Hence, we propose a machine learning-based framework combined with a heuristic technique to discover the optimal combination of two pertinent COPs used in mobility, Cell Individual Offset (CIO) and Handover Margin (HOM), that maximizes a specific Key Performance Indicator (KPI) such as mean Signal to Interference and Noise Ratio (SINR) of all the connected users. The first part of the framework leverages the power of machine learning to predict the KPI of interest given several different combinations of CIO and HOM. The resulting predictions are then fed into Genetic Algorithm (GA) which searches for the best combination of the two mentioned parameters that yield the maximum mean SINR for all users. Performance of the framework is also evaluated using several machine learning techniques, with CatBoost algorithm yielding the best prediction performance. Meanwhile, GA is able to reveal the optimal parameter setting combination more efficiently and with three orders of magnitude faster convergence time in comparison to brute force approach.
The ReProVide Query-Sequence Optimization in a Hardware-Accelerated DBMS
Venue: arXiv cs.DB 2020
Year: 2020

Hardware acceleration of database query processing can be done with the help of FPGAs. In particular, they are partially reconfigurable at runtime, which allows for the runtime adaption of the hardware to a variety of queries. Reconfiguration itself, however, takes some time. As the affected area of the FPGA is not available for computations during the reconfiguration, avoiding some of the reconfigurations can improve overall performance. This paper presents optimizations based on query sequences, which reduces the impact of the reconfigurations. Knowledge of upcoming queries is used to (I) speculatively start reconfiguration already when a query is still running and (II) avoid overwriting of reconfigurable regions that will be used again in subsequent queries. We evaluate our optimizations with a calibrated model and measurements for various parameter values. Improvements in execution time of up to 28% can be obtained even with sequences of only two queries.
A Solution for Large Scale Nonlinear Regression with High Rank and Degree at Constant Memory Complexity via Latent Tensor Reconstruction
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes a novel method for learning highly nonlinear, multivariate functions from examples. Our method takes advantage of the property that continuous functions can be approximated by polynomials, which in turn are representable by tensors. Hence the function learning problem is transformed into a tensor reconstruction problem, an inverse problem of the tensor decomposition. Our method incrementally builds up the unknown tensor from rank-one terms, which lets us control the complexity of the learned model and reduce the chance of overfitting. For learning the models, we present an efficient gradient-based algorithm that can be implemented in linear time in the sample size, order, rank of the tensor and the dimension of the input. In addition to regression, we present extensions to classification, multi-view learning and vector-valued output as well as a multi-layered formulation. The method can work in an online fashion via processing mini-batches of the data with constant memory complexity. Consequently, it can fit into systems equipped only with limited resources such as embedded systems or mobile phones. Our experiments demonstrate a favorable accuracy and running time compared to competing methods.
Open Loop In Natura Economic Planning
Venue: arXiv cs.CY 2020
Year: 2020

The debate between the optimal way of allocating societal surplus (i.e. products and services) has been raging, in one form or another, practically forever; following the collapse of the Soviet Union in 1991, the market became the only legitimate form of organisation -- there was no other alternative. Working within the tradition of Marx, Leontief, Kantorovich, Beer and Cockshott, we propose what we deem an automated planning system that aims to operate on unit level (e.g., factories and citizens), rather than on aggregate demand and sectors. We explain why it is both a viable and desirable alternative to current market conditions and position our solution within current societal structures. Our experiments show that it would be trivial to plan for up to 50K industrial goods and 5K final goods in commodity hardware.
Code and Named Entity Recognition in StackOverflow
Venue: arXiv cs.CL 2020
Year: 2020

There is an increasing interest in studying natural language and computer code together, as large corpora of programming texts become readily available on the Internet. For example, StackOverflow currently has over 15 million programming related questions written by 8.5 million users. Meanwhile, there is still a lack of fundamental NLP techniques for identifying code tokens or software-related named entities that appear within natural language sentences. In this paper, we introduce a new named entity recognition (NER) corpus for the computer programming domain, consisting of 15,372 sentences annotated with 20 fine-grained entity types. We trained in-domain BERT representations (BERTOverflow) on 152 million sentences from StackOverflow, which lead to an absolute increase of +10 F-1 score over off-the-shelf BERT. We also present the SoftNER model which achieves an overall 79.10 F$_1$ score for code and named entity recognition on StackOverflow data. Our SoftNER model incorporates a context-independent code token classifier with corpus-level features to improve the BERT-based tagging model. Our code and data are available at: https://github.com/jeniyat/StackOverflowNER/
Navigating the Landscape of Multiplayer Games
Venue: arXiv cs.AI 2020
Year: 2020

Multiplayer games have long been used as testbeds in artificial intelligence research, aptly referred to as the Drosophila of artificial intelligence. Traditionally, researchers have focused on using well-known games to build strong agents. This progress, however, can be better informed by characterizing games and their topological landscape. Tackling this latter question can facilitate understanding of agents and help determine what game an agent should target next as part of its training. Here, we show how network measures applied to response graphs of large-scale games enable the creation of a landscape of games, quantifying relationships between games of varying sizes and characteristics. We illustrate our findings in domains ranging from canonical games to complex empirical games capturing the performance of trained agents pitted against one another. Our results culminate in a demonstration leveraging this information to generate new and interesting games, including mixtures of empirical games synthesized from real world games.
Hierarchical Knowledge Graphs: A Novel Information Representation for Exploratory Search Tasks
Venue: arXiv cs.IR 2020
Year: 2020

In exploratory search tasks, alongside information retrieval, information representation is an important factor in sensemaking. In this paper, we explore a multi-layer extension to knowledge graphs, hierarchical knowledge graphs (HKGs), that combines hierarchical and network visualizations into a unified data representation asa tool to support exploratory search. We describe our algorithm to construct these visualizations, analyze interaction logs to quantitatively demonstrate performance parity with networks and performance advantages over hierarchies, and synthesize data from interaction logs, interviews, and thinkalouds on a testbed data set to demonstrate the utility of the unified hierarchy+network structure in our HKGs. Alongside the above study, we perform an additional mixed methods analysis of the effect of precision and recall on the performance of hierarchical knowledge graphs for two different exploratory search tasks. While the quantitative data shows a limited effect of precision and recall on user performance and user effort, qualitative data combined with post-hoc statistical analysis provides evidence that the type of exploratory search task (e.g., learning versus investigating) can be impacted by precision and recall. Furthermore, our qualitative analyses find that users are unable to perceive differences in the quality of extracted information. We discuss the implications of our results and analyze other factors that more significantly impact exploratory search performance in our experimental tasks.
Standards for Energy Efficient Virtualization, Content Distribution and Big Data in Beyond 5G Networks
Venue: arXiv cs.NI 2020
Year: 2020

Power consumption in communication networks and the supporting computing systems continues to increase due to the increase in traffic and processing requirements, and due to the relatively slower improvements in energy efficiency. Future networks are expected to continue to move computing algorithms and capabilities into the network including increased use of analytics, machine learning and intelligence applied to big data in the network, with content caching and virtualization. This article summarizes the key features of five new IEEE standards currently being developed to improve the energy efficiency of networks beyond 5G.
Determining the Multiplicative Complexity of Boolean Functions using SAT
Venue: arXiv cs.DS 2020
Year: 2020

We present a constructive SAT-based algorithm to determine the multiplicative complexity of a Boolean function, i.e., the smallest number of AND gates in any logic network that consists of 2-input AND gates, 2-input XOR gates, and inverters. In order to speed-up solving time, we make use of several symmetry breaking constraints; these exploit properties of XAGs that may be useful beyond the proposed SAT-based algorithm. We further propose a heuristic post-optimization algorithm to reduce the number of XOR gates once the optimum number of AND gates has been obtained, which also makes use of SAT solvers. Our algorithm is capable to find all optimum XAGs for representatives of all 5-input affine-equivalent classes, and for a set of frequently occurring 6-input functions.