OpenRaiser/Intern-Atlas huggingface dataset:
Computing Accessibility Metrics for Argentina
Venue: arXiv cs.SI 2020
Year: 2020

We present a tool to calculate distances and travel times between a set of origins and a set of destinations, using different modes of transport in Argentina. The input data for the tool is a set of destinations (a geo-referenced list of points of city amenities or "opportunities", such as firms, schools, hospitals, parks, banks or retail, etc.) and a set of origins characterized by their geographic coordinates that could be interpreted as households or other. The tool determines, from each origin, which is the closest destination, depending on the distance or travel time and the mode of transport (on foot, by bicycle, by car, and by public transport). The sets of origins and destinations are large sets, which can contain up to several thousand points. We applied and developed algorithms to improve the scalability of the different parts of the procedure. For the public transportation network, we pre-processed the reachable lines from each point and used quad-trees to determine the distance between said points and the bus line's path. A second objective of this project was to rely only on open data, such as Open Street Map (OSM) data, together with making this tool open source. Therefore, the successful development and implementation of this tool is potentially beneficial to both public sector agencies as well as NGOs and other civil society organizations that focus their work on the design and implementation of public policies, aimed at improving accessibility in cities as a way to reduce spatial inequalities and social exclusion.
Accelerating Smooth Games by Manipulating Spectral Shapes
Venue: arXiv cs.LG 2020
Year: 2020

We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimization. Shapes spanning the complex plane capture the added numerical challenges in solving smooth games. In this framework, we describe gradient-based methods, such as extragradient, as transformations on the spectral shape. Using this perspective, we propose an optimal algorithm for bilinear games. For smooth and strongly monotone operators, we identify a continuum between convex minimization, where acceleration is possible using Polyak's momentum, and the worst case where gradient descent is optimal. Finally, going beyond first-order methods, we propose an accelerated version of consensus optimization.
Cyberphysical Blockchain-Enabled Peer-to-Peer Energy Trading
Venue: arXiv cs.DC 2020
Year: 2020

Scalability and security problems of the centralized architecture models in cyberphysical systems have great potential to be solved by novel blockchain based distributed models.A decentralized energy trading system takes advantage of various sources and effectively coordinates the energy to ensure optimal utilization of the available resources. It achieves that goal by managing physical, social and business infrastructures using technologies such as Internet of Things (IoT), cloud computing and network systems. Addressing the importance of blockchain-enabled energy trading in the context of cyberphysical systems, this article provides a thorough overview of the P2P energy trading and the utilization of blockchain to enhance the efficiency and the overall performance including the degree of decentralization, scalability and the security of the systems. Three blockchain based energy trading models have been proposed to overcome the technical challenges and market barriers for better adoption of this disruptive technology.
Improving PKI, BGP, and DNS Using Blockchain: A Systematic Review
Venue: arXiv cs.CR 2020
Year: 2020

The Internet has many backbone components on top of which the whole world is connected. It is important to make these components, like Border Gateway Protocol (BGP), Domain Name System (DNS), and Public Key Infrastructure (PKI), secure and work without any interruption. All of the aforementioned components have vulnerabilities, mainly because of their dependence on the centralized parties, that should be resolved. Blockchain is revolutionizing the concept of today's Internet, primarily because of its degree of decentralization and security properties. In this paper, we discuss how blockchain provides nearly complete solutions to the open challenges for these network backbone components.
Verifying Cryptographic Security Implementations in C Using Automated Model Extraction
Venue: arXiv cs.CR 2020
Year: 2020

This thesis presents an automated method for verifying security properties of protocol implementations written in the C language. We assume that each successful run of a protocol follows the same path through the C code, justified by the fact that typical security protocols have linear structure. We then perform symbolic execution of that path to extract a model expressed in a process calculus similar to the one used by the CryptoVerif tool. The symbolic execution uses a novel algorithm that allows symbolic variables to represent bitstrings of potentially unknown length to model incoming protocol messages. The extracted models do not use pointer-addressed memory, but they may still contain low-level details concerning message formats. In the next step we replace the message formatting expressions by abstract tupling and projection operators. The properties of these operators, such as the projection operation being the inverse of the tupling operation, are typically only satisfied with respect to inputs of correct types. Therefore we typecheck the model to ensure that all type-safety constraints are satisfied. The resulting model can then be verified with CryptoVerif to obtain a computational security result directly, or with ProVerif, to obtain a computational security result by invoking a computational soundness theorem. Our method achieves high automation and does not require user input beyond what is necessary to specify the properties of the cryptographic primitives and the desired security goals. We evaluated the method on several protocol implementations, totalling over 3000 lines of code. The biggest case study was a 1000-line implementation that was independently written without verification in mind. We found several flaws that were acknowledged and fixed by the authors, and were able to verify the fixed code without any further modifications to it.
A Two stage Adaptive Knowledge Transfer Evolutionary Multi-tasking Based on Population Distribution for Multi/Many-Objective Optimization
Venue: arXiv cs.NE 2020
Year: 2020

Multi-tasking optimization can usually achieve better performance than traditional single-tasking optimization through knowledge transfer between tasks. However, current multi-tasking optimization algorithms have some deficiencies. For high similarity problems, the knowledge that can accelerate the convergence rate of tasks has not been fully taken advantages of. For low similarity problems, the probability of generating negative transfer is high, which may result in optimization performance degradation. In addition, some knowledge transfer methods proposed previously do not fully consider how to deal with the situation in which the population falls into local optimum. To solve these issues, a two-stage adaptive knowledge transfer evolutionary multi-tasking optimization algorithm based on population distribution, labeled as EMT-PD, is proposed. EMT-PD can accelerate and improve the convergence performance of tasks based on the knowledge extracted from the probability model that reflects the search trend of the whole population. At the first transfer stage, an adaptive weight is used to adjust the step size of individual's search, which can reduce the impact of negative transfer. At the second stage of knowledge transfer, the individual's search range is further adjusted dynamically, which can improve the diversity of population and be beneficial for jumping out of local optimum. Experimental results on multi-tasking multi-objective optimization test suites show that EMT-PD is superior to other six state-of-the-art evolutionary multi/single-tasking algorithms. To further investigate the effectiveness of EMT-PD on many-objective optimization problems, a multi-tasking many-objective test suite is also designed in this paper. The experimental results on the new test suite also demonstrate the competitiveness of EMT-PD.
Modeling Information Need of Users in Search Sessions
Venue: arXiv cs.IR 2020
Year: 2020

Users issue queries to Search Engines, and try to find the desired information in the results produced. They repeat this process if their information need is not met at the first place. It is crucial to identify the important words in a query that depict the actual information need of the user and will determine the course of a search session. To this end, we propose a sequence-to-sequence based neural architecture that leverages the set of past queries issued by users, and results that were explored by them. Firstly, we employ our model for predicting the words in the current query that are important and would be retained in the next query. Additionally, as a downstream application of our model, we evaluate it on the widely popular task of next query suggestion. We show that our intuitive strategy of capturing information need can yield superior performance at these tasks on two large real-world search log datasets.
Towards Scalable Dataframe Systems
Venue: arXiv cs.DB 2020
Year: 2020

Dataframes are a popular abstraction to represent, prepare, and analyze data. Despite the remarkable success of dataframe libraries in Rand Python, dataframes face performance issues even on moderately large datasets. Moreover, there is significant ambiguity regarding dataframe semantics. In this paper we lay out a vision and roadmap for scalable dataframe systems. To demonstrate the potential in this area, we report on our experience building MODIN, a scaled-up implementation of the most widely-used and complex dataframe API today, Python's pandas. With pandas as a reference, we propose a simple data model and algebra for dataframes to ground discussion in the field. Given this foundation, we lay out an agenda of open research opportunities where the distinct features of dataframes will require extending the state of the art in many dimensions of data management. We discuss the implications of signature data-frame features including flexible schemas, ordering, row/column equivalence, and data/metadata fluidity, as well as the piecemeal, trial-and-error-based approach to interacting with dataframes.
Closing the AI Accountability Gap: Defining an End-to-End Framework for Internal Algorithmic Auditing
Venue: arXiv cs.CY 2020
Year: 2020

Rising concern for the societal implications of artificial intelligence systems has inspired a wave of academic and journalistic literature in which deployed systems are audited for harm by investigators from outside the organizations deploying the algorithms. However, it remains challenging for practitioners to identify the harmful repercussions of their own systems prior to deployment, and, once deployed, emergent issues can become difficult or impossible to trace back to their source. In this paper, we introduce a framework for algorithmic auditing that supports artificial intelligence system development end-to-end, to be applied throughout the internal organization development lifecycle. Each stage of the audit yields a set of documents that together form an overall audit report, drawing on an organization's values or principles to assess the fit of decisions made throughout the process. The proposed auditing framework is intended to contribute to closing the accountability gap in the development and deployment of large-scale artificial intelligence systems by embedding a robust process to ensure audit integrity.
Automated Discovery of Data Transformations for Robotic Process Automation
Venue: arXiv cs.AI 2020
Year: 2020

Robotic Process Automation (RPA) is a technology for automating repetitive routines consisting of sequences of user interactions with one or more applications. In order to fully exploit the opportunities opened by RPA, companies need to discover which specific routines may be automated, and how. In this setting, this paper addresses the problem of analyzing User Interaction (UI) logs in order to discover routines where a user transfers data from one spreadsheet or (Web) form to another. The paper maps this problem to that of discovering data transformations by example - a problem for which several techniques are available. The paper shows that a naive application of a state-of-the-art technique for data transformation discovery is computationally inefficient. Accordingly, the paper proposes two optimizations that take advantage of the information in the UI log and the fact that data transfers across applications typically involve copying alphabetic and numeric tokens separately. The proposed approach and its optimizations are evaluated using UI logs that replicate a real-life repetitive data transfer routine.
Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
Venue: arXiv cs.LG 2020
Year: 2020

This paper considers the problem of estimating the principal eigenvector of a covariance matrix from independent and identically distributed data samples in streaming settings. The streaming rate of data in many contemporary applications can be high enough that a single processor cannot finish an iteration of existing methods for eigenvector estimation before a new sample arrives. This paper formulates and analyzes a distributed variant of the classical Krasulina's method (D-Krasulina) that can keep up with the high streaming rate of data by distributing the computational load across multiple processing nodes. The analysis shows that---under appropriate conditions---D-Krasulina converges to the principal eigenvector in an order-wise optimal manner; i.e., after receiving $M$ samples across all nodes, its estimation error can be $O(1/M)$. In order to reduce the network communication overhead, the paper also develops and analyzes a mini-batch extension of D-Krasulina, which is termed DM-Krasulina. The analysis of DM-Krasulina shows that it can also achieve order-optimal estimation error rates under appropriate conditions, even when some samples have to be discarded within the network due to communication latency. Finally, experiments are performed over synthetic and real-world data to validate the convergence behaviors of D-Krasulina and DM-Krasulina in high-rate streaming settings.
Represented Value Function Approach for Large Scale Multi Agent Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we consider the problem of large scale multi agent reinforcement learning. Firstly, we studied the representation problem of the pairwise value function to reduce the complexity of the interactions among agents. Secondly, we adopt a l2-norm trick to ensure the trivial term of the approximated value function is bounded. Thirdly, experimental results on battle game demonstrate the effectiveness of the proposed approach.
User Profiling Using Hinge-loss Markov Random Fields
Venue: arXiv cs.SI 2020
Year: 2020

A variety of approaches have been proposed to automatically infer the profiles of users from their digital footprint in social media. Most of the proposed approaches focus on mining a single type of information, while ignoring other sources of available user-generated content (UGC). In this paper, we propose a mechanism to infer a variety of user characteristics, such as, age, gender and personality traits, which can then be compiled into a user profile. To this end, we model social media users by incorporating and reasoning over multiple sources of UGC as well as social relations. Our model is based on a statistical relational learning framework using Hinge-loss Markov Random Fields (HL-MRFs), a class of probabilistic graphical models that can be defined using a set of first-order logical rules. We validate our approach on data from Facebook with more than 5k users and almost 725k relations. We show how HL-MRFs can be used to develop a generic and extensible user profiling framework by leveraging textual, visual, and relational content in the form of status updates, profile pictures and Facebook page likes. Our experimental results demonstrate that our proposed model successfully incorporates multiple sources of information and outperforms competing methods that use only one source of information or an ensemble method across the different sources for modeling of users in social media.
Covert Association of Applications on Edge Devices by Processor Workload
Venue: arXiv cs.CR 2020
Year: 2020

The scheme of application (app) distribution systems involving incentivized third-party app vendors is a desirable option for the emerging edge computing systems. However, such a scheme also brings various security challenges as faced by the current mobile app distribution systems. In this paper, we study a threat named covert device association, in which the vendors of two apps collude to figure out which of their app installations run on the same edge device. If the two colluding apps are popular, the threat can be used to launch various types of further attacks at scale. For example, the user of the compromised edge device, who wishes to remain anonymous to one of the two apps, will be de-anonymized if the user is not anonymous to the other app. Moreover, the coalition of the two apps will have an escalated privilege set that is the union of their individual privilege sets. In this paper, we implement the threat by a reliable and ubiquitous covert channel based on the edge device processor workload. The implementations on three edge devices (two smartphones and an embedded compute board) running Android and Android Things do not require any privileged permissions. Our implementations cover three attack scenarios of 1) two apps running on the same Android phone, 2) an app and a web session in the Tor browser running on the same Android phone, and 3) two apps running on the same Android Things device. Experiments show that the covert channel gives at least 0.25 bps data rate and the covert device association takes at most 3.2 minutes.
Design of Capacity-Approaching Low-Density Parity-Check Codes using Recurrent Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we model Density Evolution (DE) using Recurrent Neural Networks (RNNs) with the aim of designing capacity-approaching Irregular Low-Density Parity-Check (LDPC) codes for binary erasure channels. In particular, we present a method for determining the coefficients of the degree distributions, characterizing the structure of an LDPC code. We refer to our RNN architecture as Neural Density Evolution (NDE) and determine the weights of the RNN that correspond to optimal designs by minimizing a loss function that enforces the properties of asymptotically optimal design, as well as the desired structural characteristics of the code. This renders the LDPC design process highly configurable, as constraints can be added to meet applications' requirements by means of modifying the loss function. In order to train the RNN, we generate data corresponding to the expected channel noise. We analyze the complexity and optimality of NDE theoretically, and compare it with traditional design methods that employ differential evolution. Simulations illustrate that NDE improves upon differential evolution both in terms of asymptotic performance and complexity. Although we focus on asymptotic settings, we evaluate designs found by NDE for finite codeword lengths and observe that performance remains satisfactory across a variety of channels.
A New Store-then-Amplify-and-Forward Protocol for UAV Mobile Relaying
Venue: arXiv cs.IT 2020
Year: 2020

In this letter, we consider the use of an unmanned aerial vehicle (UAV) as a mobile relay to assist the communication between two ground users without a direct link. We propose a novel store-then-amplify-and-forward (SAF) relaying protocol for the UAV to exploit its mobility jointly with the low-complexity AF relaying. Specifically, the received signal from the source is first stored in a buffer at the UAV, then amplified and forwarded to the destination when the UAV flies closer to the destination. With this new SAF protocol, we aim to maximize the throughput of the UAV-enabled relaying system by jointly optimizing the source/UAV transmit power and the UAV trajectory, as well as the time-slot pairing for each data packet received and forwarded by the UAV. As this problem is a non-convex mixed integer optimization problem that is difficult to solve, we propose an efficient algorithm for obtaining a suboptimal solution for it by applying the techniques of Hungary algorithm, alternating optimization and successive convex approximation. Numerical results show that the proposed mobile SAF relaying outperforms the conventional AF relaying without signal storing.
Self-Orthogonality Module: A Network Architecture Plug-in for Learning Orthogonal Filters
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we investigate the empirical impact of orthogonality regularization (OR) in deep learning, either solo or collaboratively. Recent works on OR showed some promising results on the accuracy. In our ablation study, however, we do not observe such significant improvement from existing OR techniques compared with the conventional training based on weight decay, dropout, and batch normalization. To identify the real gain from OR, inspired by the locality sensitive hashing (LSH) in angle estimation, we propose to introduce an implicit self-regularization into OR to push the mean and variance of filter angles in a network towards 90 and 0 simultaneously to achieve (near) orthogonality among the filters, without using any other explicit regularization. Our regularization can be implemented as an architectural plug-in and integrated with an arbitrary network. We reveal that OR helps stabilize the training process and leads to faster convergence and better generalization.
Measuring Diversity in Heterogeneous Information Networks
Venue: arXiv cs.AI 2020
Year: 2020

Diversity is a concept relevant to numerous domains of research varying from ecology, to information theory, and to economics, to cite a few. It is a notion that is steadily gaining attention in the information retrieval, network analysis, and artificial neural networks communities. While the use of diversity measures in network-structured data counts a growing number of applications, no clear and comprehensive description is available for the different ways in which diversities can be measured. In this article, we develop a formal framework for the application of a large family of diversity measures to heterogeneous information networks (HINs), a flexible, widely-used network data formalism. This extends the application of diversity measures, from systems of classifications and apportionments, to more complex relations that can be better modeled by networks. In doing so, we not only provide an effective organization of multiple practices from different domains, but also unearth new observables in systems modeled by heterogeneous information networks. We illustrate the pertinence of our approach by developing different applications related to various domains concerned by both diversity and networks. In particular, we illustrate the usefulness of these new proposed observables in the domains of recommender systems and social media studies, among other fields.