OpenRaiser/Intern-Atlas huggingface dataset:
SonicChain: A Wait-free, Pseudo-Static Approach Toward Concurrency in Blockchains
Venue: arXiv cs.DC 2021
Year: 2021

Blockchains have a two-sided reputation: they are praised for disrupting some of our institutions through innovative technology for good, yet notorious for being slow and expensive to use. In this work, we tackle this issue with concurrency, yet we aim to take a radically different approach by valuing simplicity. We embrace the simplicity through two steps: first, we formulate a simple runtime mechanism to deal with conflicts called concurrency delegation. This method is much simpler and has less overhead, particularly in scenarios where conflicting transactions are relatively rare. Moreover, to further reduce the number of conflicting transactions, we propose using static annotations attached to each transaction, provided by the programmer. These annotations are pseudo-static: they are static with respect to the lifetime of the transaction, and therefore are free to use information such as the origin and parameters of the transaction. We propose a distributor component that can use the output of this pseudo-static annotations and use them to effectively distribute transactions between threads in the least-conflicting way. We name the outcome of a system combining concurrency delegation and pseudo-static annotations as SonicChain. We evaluate SonicChain for both validation and authoring tasks against a common workload in blockchains, namely, balance transfers, and observe that it performs expectedly well while introducing very little overhead and additional complexity to the system.
Improved Point Transformation Methods For Self-Supervised Depth Prediction
Venue: arXiv cs.CV 2021
Year: 2021

Given stereo or egomotion image pairs, a popular and successful method for unsupervised learning of monocular depth estimation is to measure the quality of image reconstructions resulting from the learned depth predictions. Continued research has improved the overall approach in recent years, yet the common framework still suffers from several important limitations, particularly when dealing with points occluded after transformation to a novel viewpoint. While prior work has addressed this problem heuristically, this paper introduces a z-buffering algorithm that correctly and efficiently handles occluded points. Because our algorithm is implemented with operators typical of machine learning libraries, it can be incorporated into any existing unsupervised depth learning framework with automatic support for differentiation. Additionally, because points having negative depth after transformation often signify erroneously shallow depth predictions, we introduce a loss function to penalize this undesirable behavior explicitly. Experimental results on the KITTI data set show that the z-buffer and negative depth loss both improve the performance of a state of the art depth-prediction network.
Stochastic Spatio-Temporal Optimization for Control and Co-Design of Systems in Robotics and Applied Physics
Venue: arXiv cs.RO 2021
Year: 2021

Correlated with the trend of increasing degrees of freedom in robotic systems is a similar trend of rising interest in Spatio-Temporal systems described by Partial Differential Equations (PDEs) among the robotics and control communities. These systems often exhibit dramatic under-actuation, high dimensionality, bifurcations, and multimodal instabilities. Their control represents many of the current-day challenges facing the robotics and automation communities. Not only are these systems challenging to control, but the design of their actuation is an NP-hard problem on its own. Recent methods either discretize the space before optimization, or apply tools from linear systems theory under restrictive linearity assumptions in order to arrive at a control solution. This manuscript provides a novel sampling-based stochastic optimization framework based entirely in Hilbert spaces suitable for the general class of \textit{semi-linear} SPDEs which describes many systems in robotics and applied physics. This framework is utilized for simultaneous policy optimization and actuator co-design optimization. The resulting algorithm is based on variational optimization, and performs joint episodic optimization of the feedback control law and the actuation design over episodes. We study first and second order systems, and in doing so, extend several results to the case of second order SPDEs. Finally, we demonstrate the efficacy of the proposed approach with several simulated experiments on a variety of SPDEs in robotics and applied physics including an infinite degree-of-freedom soft robotic manipulator.
A maximum entropy model of bounded rational decision-making with prior beliefs and market feedback
Venue: arXiv cs.IT 2021
Year: 2021

Bounded rationality is an important consideration stemming from the fact that agents often have limits on their processing abilities, making the assumption of perfect rationality inapplicable to many real tasks. We propose an information-theoretic approach to the inference of agent decisions under Smithian competition. The model explicitly captures the boundedness of agents (limited in their information-processing capacity) as the cost of information acquisition for expanding their prior beliefs. The expansion is measured as the Kullblack-Leibler divergence between posterior decisions and prior beliefs. When information acquisition is free, the homo economicus agent is recovered, while in cases when information acquisition becomes costly, agents instead revert to their prior beliefs. The maximum entropy principle is used to infer least-biased decisions based upon the notion of Smithian competition formalised within the Quantal Response Statistical Equilibrium framework. The incorporation of prior beliefs into such a framework allowed us to systematically explore the effects of prior beliefs on decision-making in the presence of market feedback, as well as importantly adding a temporal interpretation to the framework. We verified the proposed model using Australian housing market data, showing how the incorporation of prior knowledge alters the resulting agent decisions. Specifically, it allowed for the separation of past beliefs and utility maximisation behaviour of the agent as well as the analysis into the evolution of agent beliefs.
Network Size Estimation in Small-World Networks under Byzantine Faults
Venue: arXiv cs.DC 2021
Year: 2021

We study the fundamental problem of counting the number of nodes in a sparse network (of unknown size) under the presence of a large number of Byzantine nodes. We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power, and can deviate arbitrarily from the protocol. Our main contribution is a randomized distributed algorithm that estimates the size of a network under the presence of a large number of Byzantine nodes. In particular, our algorithm estimates the size of a sparse, "small-world", expander network with up to $O(n^{1 - δ})$ Byzantine nodes, where $n$ is the (unknown) network size and $δ$ can be be any arbitrarily small (but fixed) positive constant. Our algorithm outputs a (fixed) constant factor estimate of $\log(n)$ with high probability; the correct estimate of the network size will be known to a large fraction ($(1 - ε)$-fraction, for any fixed positive constant $ε$) of the honest nodes. Our algorithm is fully distributed, lightweight, and simple to implement, runs in $O(\log^3{n})$ rounds, and requires nodes to send and receive messages of only small-sized messages per round; any node's local computation cost per round is also small.
Less is More: Pre-train a Strong Text Encoder for Dense Retrieval Using a Weak Decoder
Venue: arXiv cs.LG 2021
Year: 2021

Dense retrieval requires high-quality text sequence embeddings to support effective search in the representation space. Autoencoder-based language models are appealing in dense retrieval as they train the encoder to output high-quality embedding that can reconstruct the input texts. However, in this paper, we provide theoretical analyses and show empirically that an autoencoder language model with a low reconstruction loss may not provide good sequence representations because the decoder may take shortcuts by exploiting language patterns. To address this, we propose a new self-learning method that pre-trains the autoencoder using a \textit{weak} decoder, with restricted capacity and attention flexibility to push the encoder to provide better text representations. Our experiments on web search, news recommendation, and open domain question answering show that our pre-trained model significantly boosts the effectiveness and few-shot ability of dense retrieval models. Our code is available at https://github.com/microsoft/SEED-Encoder/.
HandTailor: Towards High-Precision Monocular 3D Hand Recovery
Venue: arXiv cs.CV 2021
Year: 2021

3D hand pose estimation and shape recovery are challenging tasks in computer vision. We introduce a novel framework HandTailor, which combines a learning-based hand module and an optimization-based tailor module to achieve high-precision hand mesh recovery from a monocular RGB image. The proposed hand module unifies perspective projection and weak perspective projection in a single network towards accuracy-oriented and in-the-wild scenarios. The proposed tailor module then utilizes the coarsely reconstructed mesh model provided by the hand module as initialization, and iteratively optimizes an energy function to obtain better results. The tailor module is time-efficient, costs only 8ms per frame on a modern CPU. We demonstrate that HandTailor can get state-of-the-art performance on several public benchmarks, with impressive qualitative results on in-the-wild experiments. Code and video are available on our project webpage https://sites.google.com/view/handtailor.
A matrix approach to detect temporal behavioral patterns at electric vehicle charging stations
Venue: arXiv cs.LG 2021
Year: 2021

Based on the electric vehicle (EV) arrival times and the duration of EV connection to the charging station, we identify charging patterns and derive groups of charging stations with similar charging patterns applying two approaches. The ruled based approach derives the charging patterns by specifying a set of time intervals and a threshold value. In the second approach, we combine the modified l-p norm (as a matrix dissimilarity measure) with hierarchical clustering and apply them to automatically identify charging patterns and groups of charging stations associated with such patterns. A dataset collected in a large network of public charging stations is used to test both approaches. Using both methods, we derived charging patterns. The first, rule-based approach, performed well at deriving predefined patterns and the latter, hierarchical clustering, showed the capability of delivering unexpected charging patterns.
Data Structures Lower Bounds and Popular Conjectures
Venue: arXiv cs.CC 2021
Year: 2021

In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li and several data structure like problems such as non-adaptive function inversion of Hellman and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.
A Unified System for Data Analytics and In Situ Query Processing
Venue: arXiv cs.DB 2021
Year: 2021

In today's world data is being generated at a high rate due to which it has become inevitable to analyze and quickly get results from this data. Most of the relational databases primarily support SQL querying with a limited support for complex data analysis. Due to this reason, data scientists have no other option, but to use a different system for complex data analysis. Due to this, data science frameworks are in huge demand. But to use such a framework, all the data needs to be loaded into it. This requires significant data movement across multiple systems, which can be expensive. We believe that it has become the need of the hour to come up with a single system which can perform both data analysis tasks and SQL querying. This will save the data scientists from the expensive data transfer operation across systems. In our work, we present DaskDB, a system built over the Python's Dask framework, which is a scalable data science system having support for both data analytics and in situ SQL query processing over heterogeneous data sources. DaskDB supports invoking any Python APIs as User-Defined Functions (UDF) over SQL queries. So, it can be easily integrated with most existing Python data science applications, without modifying the existing code. Since joining two relations is a very vital but expensive operation, so a novel distributed learned index is also introduced to improve the join performance. Our experimental evaluation demonstrates that DaskDB significantly outperforms existing systems.
Harnessing Tensor Structures -- Multi-Mode Reservoir Computing and Its Application in Massive MIMO
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we introduce a new neural network (NN) structure, multi-mode reservoir computing (Multi-Mode RC). It inherits the dynamic mechanism of RC and processes the forward path and loss optimization of the NN using tensor as the underlying data format. Multi-Mode RC exhibits less complexity compared with conventional RC structures (e.g. single-mode RC) with comparable generalization performance. Furthermore, we introduce an alternating least square-based learning algorithm for Multi-Mode RC as well as conduct the associated theoretical analysis. The result can be utilized to guide the configuration of NN parameters to sufficiently circumvent over-fitting issues. As a key application, we consider the symbol detection task in multiple-input-multiple-output (MIMO) orthogonal-frequency-division-multiplexing (OFDM) systems with massive MIMO employed at the base stations (BSs). Thanks to the tensor structure of massive MIMO-OFDM signals, our online learning-based symbol detection method generalizes well in terms of bit error rate even using a limited online training set. Evaluation results suggest that the Multi-Mode RC-based learning framework can efficiently and effectively combat practical constraints of wireless systems (i.e. channel state information (CSI) errors and hardware non-linearity) to enable robust and adaptive learning-based communications over the air.
FIXME: Enhance Software Reliability with Hybrid Approaches in Cloud
Venue: arXiv cs.SE 2021
Year: 2021

With the promise of reliability in cloud, more enterprises are migrating to cloud. The process of continuous integration/deployment (CICD) in cloud connects developers who need to deliver value faster and more transparently with site reliability engineers (SREs) who need to manage applications reliably. SREs feed back development issues to developers, and developers commit fixes and trigger CICD to redeploy. The release cycle is more continuous than ever, thus the code to production is faster and more automated. To provide this higher level agility, the cloud platforms become more complex in the face of flexibility with deeper layers of virtualization. However, reliability does not come for free with all these complexities. Software engineers and SREs need to deal with wider information spectrum from virtualized layers. Therefore, providing correlated information with true positive evidences is critical to identify the root cause of issues quickly in order to reduce mean time to recover (MTTR), performance metrics for SREs. Similarity, knowledge, or statistics driven approaches have been effective, but with increasing data volume and types, an individual approach is limited to correlate semantic relations of different data sources. In this paper, we introduce FIXME to enhance software reliability with hybrid diagnosis approaches for enterprises. Our evaluation results show using hybrid diagnosis approach is about 17% better in precision. The results are helpful for both practitioners and researchers to develop hybrid diagnosis in the highly dynamic cloud environment.
Domain Adaptive Learning Based on Sample-Dependent and Learnable Kernels
Venue: arXiv cs.LG 2021
Year: 2021

Reproducing Kernel Hilbert Space (RKHS) is the common mathematical platform for various kernel methods in machine learning. The purpose of kernel learning is to learn an appropriate RKHS according to different machine learning scenarios and training samples. Because RKHS is uniquely generated by the kernel function, kernel learning can be regarded as kernel function learning. This paper proposes a Domain Adaptive Learning method based on Sample-Dependent and Learnable Kernels (SDLK-DAL). The first contribution of our work is to propose a sample-dependent and learnable Positive Definite Quadratic Kernel function (PDQK) framework. Unlike learning the exponential parameter of Gaussian kernel function or the coefficient of kernel combinations, the proposed PDQK is a positive definite quadratic function, in which the symmetric positive semi-definite matrix is the learnable part in machine learning applications. The second contribution lies on that we apply PDQK to Domain Adaptive Learning (DAL). Our approach learns the PDQK through minimizing the mean discrepancy between the data of source domain and target domain and then transforms the data into an optimized RKHS generated by PDQK. We conduct a series of experiments that the RKHS determined by PDQK replaces those in several state-of-the-art DAL algorithms, and our approach achieves better performance.
AI Can Stop Mass Shootings, and More
Venue: arXiv cs.CY 2021
Year: 2021

We propose to build directly upon our longstanding, prior r&d in AI/machine ethics in order to attempt to make real the blue-sky idea of AI that can thwart mass shootings, by bringing to bear its ethical reasoning. The r&d in question is overtly and avowedly logicist in form, and since we are hardly the only ones who have established a firm foundation in the attempt to imbue AI's with their own ethical sensibility, the pursuit of our proposal by those in different methodological camps should, we believe, be considered as well. We seek herein to make our vision at least somewhat concrete by anchoring our exposition to two simulations, one in which the AI saves the lives of innocents by locking out a malevolent human's gun, and a second in which this malevolent agent is allowed by the AI to be neutralized by law enforcement. Along the way, some objections are anticipated, and rebutted.
Multilingual, Temporal and Sentimental Distant-Reading of City Events
Venue: arXiv cs.CY 2021
Year: 2021

Leibniz's Monadology mentions perceptional and sentimental variations of the individual in the city. It is the interaction of people with people and events. Film festivals are highly sentimental events of multicultural cities. Each movie has a different sentimental effect and the interactions with the movies have reflections that can be observed on social media. This analysis aims to apply distant reading on Berlinale tweets collected during the festival. On contrary to close reading, distant reading let authors to observe patterns in large collection of data. The analysis is temporal and sentimental in multilingual domain and strongly positive and negative time intervals are analysed. For this purpose, we trained a deep sentiment network with multilingual embeddings. These multilingual embeddings are aligned in latent space. We trained the network with a multilingual dataset in three languages English, German and Spanish. The trained algorithm has a 0.78 test score and applied on Tweets with Berlinale hashtag during the festival. Although the sentimental analysis does not reflect the award-winning films, we observe weekly routine on the relationship between sentimentality, which can mislead a close reading analysis. We have also remarks on popularity of the director or actors.
Efficient Reinforcement Learning in Resource Allocation Problems Through Permutation Invariant Multi-task Learning
Venue: arXiv cs.LG 2021
Year: 2021

One of the main challenges in real-world reinforcement learning is to learn successfully from limited training samples. We show that in certain settings, the available data can be dramatically increased through a form of multi-task learning, by exploiting an invariance property in the tasks. We provide a theoretical performance bound for the gain in sample efficiency under this setting. This motivates a new approach to multi-task learning, which involves the design of an appropriate neural network architecture and a prioritized task-sampling strategy. We demonstrate empirically the effectiveness of the proposed approach on two real-world sequential resource allocation tasks where this invariance property occurs: financial portfolio optimization and meta federated learning.
L2E: Learning to Exploit Your Opponent
Venue: arXiv cs.LG 2021
Year: 2021

Opponent modeling is essential to exploit sub-optimal opponents in strategic interactions. Most previous works focus on building explicit models to directly predict the opponents' styles or strategies, which require a large amount of data to train the model and lack adaptability to unknown opponents. In this work, we propose a novel Learning to Exploit (L2E) framework for implicit opponent modeling. L2E acquires the ability to exploit opponents by a few interactions with different opponents during training, thus can adapt to new opponents with unknown styles during testing quickly. We propose a novel opponent strategy generation algorithm that produces effective opponents for training automatically. We evaluate L2E on two poker games and one grid soccer game, which are the commonly used benchmarks for opponent modeling. Comprehensive experimental results indicate that L2E quickly adapts to diverse styles of unknown opponents.
Interleaving Computational and Inferential Thinking: Data Science for Undergraduates at Berkeley
Venue: arXiv cs.CY 2021
Year: 2021

The undergraduate data science curriculum at the University of California, Berkeley is anchored in five new courses that emphasize computational thinking, inferential thinking, and working on real-world problems. We believe that interleaving these elements within our core courses is essential to preparing students to engage in data-driven inquiry at the scale that contemporary scientific and industrial applications demand. This new curriculum is already reshaping the undergraduate experience at Berkeley, where these courses have become some of the most popular on campus and have led to a surging interest in a new undergraduate major and minor program in data science.
A Stronger Impossibility for Fully Online Matching
Venue: arXiv cs.DS 2021
Year: 2021

We revisit the fully online matching model (Huang et al., J.\ ACM, 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (STOC 1990), which has recently received a lot of attention (Huang et al., SODA 2019 and FOCS 2020), partly due to applications in ride-sharing platforms. It has been shown that the fully online version is harder than the classic version for which the achievable competitive ratio is at most $0.6317$, rather than precisely $1-\frac{1}{e}\approx 0.6321$. We introduce two new ideas to the construction. By optimizing the parameters of the modified construction numerically, we obtain an improved impossibility result of $0.6297$. Like the previous bound, the new bound even holds for fractional (rather than randomized) algorithms on bipartite graphs.