OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Interaction Networks with Rethinking Mechanism for Document-level Sentiment Analysis
Venue: arXiv cs.CL 2022
Year: 2022

Document-level Sentiment Analysis (DSA) is more challenging due to vague semantic links and complicate sentiment information. Recent works have been devoted to leveraging text summarization and have achieved promising results. However, these summarization-based methods did not take full advantage of the summary including ignoring the inherent interactions between the summary and document. As a result, they limited the representation to express major points in the document, which is highly indicative of the key sentiment. In this paper, we study how to effectively generate a discriminative representation with explicit subject patterns and sentiment contexts for DSA. A Hierarchical Interaction Networks (HIN) is proposed to explore bidirectional interactions between the summary and document at multiple granularities and learn subject-oriented document representations for sentiment classification. Furthermore, we design a Sentiment-based Rethinking mechanism (SR) by refining the HIN with sentiment label information to learn a more sentiment-aware document representation. We extensively evaluate our proposed models on three public datasets. The experimental results consistently demonstrate the effectiveness of our proposed models and show that HIN-SR outperforms various state-of-the-art methods.
Reliable Spanners for Metric Spaces
Venue: arXiv cs.CG 2022
Year: 2022

A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.
Surface Normal Estimation of Tilted Images via Spatial Rectifier
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we present a spatial rectifier to estimate surface normals of tilted images. Tilted images are of particular interest as more visual data are captured by arbitrarily oriented sensors such as body-/robot-mounted cameras. Existing approaches exhibit bounded performance on predicting surface normals because they were trained using gravity-aligned images. Our two main hypotheses are: (1) visual scene layout is indicative of the gravity direction; and (2) not all surfaces are equally represented by a learned estimator due to the structured distribution of the training data, thus, there exists a transformation for each tilted image that is more responsive to the learned estimator than others. We design a spatial rectifier that is learned to transform the surface normal distribution of a tilted image to the rectified one that matches the gravity-aligned training data distribution. Along with the spatial rectifier, we propose a novel truncated angular loss that offers a stronger gradient at smaller angular errors and robustness to outliers. The resulting estimator outperforms the state-of-the-art methods including data augmentation baselines not only on ScanNet and NYUv2 but also on a new dataset called Tilt-RGBD that includes considerable roll and pitch camera motion.
Energy Efficient Computing Systems: Architectures, Abstractions and Modeling to Techniques and Standards
Venue: arXiv cs.AR 2022
Year: 2022

Computing systems have undergone several inflexion points - while Moore's law guided the semiconductor industry to cram more and more transistors and logic into the same volume, the limits of instruction-level parallelism (ILP) and the end of Dennard's scaling drove the industry towards multi-core chips. We have now entered the era of domain-specific architectures for new workloads like AI and ML. These trends continue, arguably with other limits, along with challenges imposed by tighter integration, extreme form factors and diverse workloads, making systems more complex from an energy efficiency perspective. Many research surveys have covered different aspects of techniques in hardware and microarchitecture across devices, servers, HPC, data center systems along with software, algorithms, frameworks for energy efficiency and thermal management. Somewhat in parallel, the semiconductor industry has developed techniques and standards around specification, modeling and verification of complex chips; these areas have not been addressed in detail by previous research surveys. This survey aims to bring these domains together and is composed of a systematic categorization of key aspects of building energy efficient systems - (a) specification - the ability to precisely specify the power intent or properties at different layers (b) modeling and simulation of the entire system or subsystem (hardware or software or both) so as to be able to perform what-if analysis, (c) techniques used for implementing energy efficiency at different levels of the stack, (d) verification techniques used to provide guarantees that the functionality of complex designs are preserved, and (e) energy efficiency standards and consortiums that aim to standardize different aspects of energy efficiency, including cross-layer optimizations.
Meet MASKS: A novel Multi-Classifier's verification approach
Venue: arXiv cs.AI 2022
Year: 2022

In this study, a new ensemble approach for classifiers is introduced. A verification method for better error elimination is developed through the integration of multiple classifiers. A multi-agent system comprised of multiple classifiers is designed to verify the satisfaction of the safety property. In order to examine the reasoning concerning the aggregation of the distributed knowledge, a logical model has been proposed. To verify predefined properties, a Multi-Agent Systems' Knowledge-Sharing algorithm (MASKS) has been formulated and developed. As a rigorous evaluation, we applied this model to the Fashion-MNIST, MNIST, and Fruit-360 datasets, where it reduced the error rate to approximately one-tenth of the individual classifiers.
Buffer Pool Aware Query Scheduling via Deep Reinforcement Learning
Venue: arXiv cs.DB 2022
Year: 2022

In this extended abstract, we propose a new technique for query scheduling with the explicit goal of reducing disk reads and thus implicitly increasing query performance. We introduce SmartQueue, a learned scheduler that leverages overlapping data reads among incoming queries and learns a scheduling strategy that improves cache hits. SmartQueue relies on deep reinforcement learning to produce workload-specific scheduling strategies that focus on long-term performance benefits while being adaptive to previously-unseen data access patterns. We present results from a proof-of-concept prototype, demonstrating that learned schedulers can offer significant performance improvements over hand-crafted scheduling heuristics. Ultimately, we make the case that this is a promising research direction at the intersection of machine learning and databases.
FedOCR: Communication-Efficient Federated Learning for Scene Text Recognition
Venue: arXiv cs.CV 2022
Year: 2022

While scene text recognition techniques have been widely used in commercial applications, data privacy has rarely been taken into account by this research community. Most existing algorithms have assumed a set of shared or centralized training data. However, in practice, data may be distributed on different local devices that can not be centralized to share due to the privacy restrictions. In this paper, we study how to make use of decentralized datasets for training a robust scene text recognizer while keeping them stay on local devices. To the best of our knowledge, we propose the first framework leveraging federated learning for scene text recognition, which is trained with decentralized datasets collaboratively. Hence we name it FedOCR. To make FedCOR fairly suitable to be deployed on end devices, we make two improvements including using lightweight models and hashing techniques. We argue that both are crucial for FedOCR in terms of the communication efficiency of federated learning. The simulations on decentralized datasets show that the proposed FedOCR achieves competitive results to the models that are trained with centralized data, with fewer communication costs and higher-level privacy-preserving.
Towards Overcoming the Undercutting Problem
Venue: arXiv cs.CR 2022
Year: 2022

Mining processes of Bitcoin and similar cryptocurrencies are currently incentivized with voluntary transaction fees and fixed block rewards which will halve gradually to zero. In the setting where optional and arbitrary transaction fee becomes the remaining incentive, Carlsten et al.\ [CCS~2016] find that an undercutting attack can become the equilibrium strategy for miners. In undercutting, the attacker deliberately forks an existing chain by leaving wealthy transactions unclaimed to attract petty complaint miners to its fork. We observe that two simplifying assumptions in [CCS~2016] of fees arriving at fixed rates and miners collecting {\em all} accumulated fees regardless of block size limit are often infeasible in practice and find that they are inaccurately inflating the profitability of undercutting. Studying Bitcoin and Monero blockchain data, we find that the fees deliberately left out by an undercutter may not be attractive to other miners (hence to the attacker itself): the deliberately left out transactions may not fit into a new block without "squeezing out" some other to-be transactions, and thus claimable fees in the next round cannot be raised arbitrarily. This work views undercutting and shifting among chains rationally as mining strategies of rational miners. We model profitability of undercutting strategy with block size limit present, which bounds the claimable fees in a round and gives rise to a pending (cushion) transaction set. In the proposed model, we first identify the conditions necessary to make undercutting profitable. We then present an easy-to-deploy defense against undercutting by selectively assembling transactions into the new block to invalidate the identified conditions. Under a typical setting with undercutters present, applying this avoidance technique is a Nash Equilibrium. Finally, we complement the above analytical results with experiments.
Improving the dilation of a metric graph by adding edges
Venue: arXiv cs.CG 2022
Year: 2022

Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of $k$ edges, which $k$ edges do we add to produce a minimum-dilation graph? The special case where $k=1$ has been studied in the past, but no major breakthroughs have been made for $k > 1$. We provide the first positive result, an $O(k)$-approximation algorithm that runs in $O(n^3 \log n)$ time.
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this problem introduced by Huang, Tang, Wu, and Zhang (TALG 2019), who show that their algorithm has a competitive ratio of 0.6534. We show that assumptions in their analysis can be weakened, allowing us to replace their derivation of a crucial function $g$ on the unit square with a linear program that computes the values of a best possible $g$ under these assumptions on a discretized unit square. We show that the discretization does not incur much error, and show computationally that we can obtain a competitive ratio of 0.6629. To compute the bound over our discretized unit square we use parallelization, and still needed two days of computing on a 64-core machine. Furthermore, by modifying our linear program somewhat, we can show computationally an upper bound on our approach of 0.6688; any further progress beyond this bound will require either further weakening in the assumptions of $g$ or a stronger analysis than that of Huang et al.
Object Handovers: a Review for Robotics
Venue: arXiv cs.RO 2022
Year: 2022

This article surveys the literature on human-robot object handovers. A handover is a collaborative joint action where an agent, the giver, gives an object to another agent, the receiver. The physical exchange starts when the receiver first contacts the object held by the giver and ends when the giver fully releases the object to the receiver. However, important cognitive and physical processes begin before the physical exchange, including initiating implicit agreement with respect to the location and timing of the exchange. From this perspective, we structure our review into the two main phases delimited by the aforementioned events: 1) a pre-handover phase, and 2) the physical exchange. We focus our analysis on the two actors (giver and receiver) and report the state of the art of robotic givers (robot-to-human handovers) and the robotic receivers (human-to-robot handovers). We report a comprehensive list of qualitative and quantitative metrics commonly used to assess the interaction. While focusing our review on the cognitive level (e.g., prediction, perception, motion planning, learning) and the physical level (e.g., motion, grasping, grip release) of the handover, we briefly discuss also the concepts of safety, social context, and ergonomics. We compare the behaviours displayed during human-to-human handovers to the state of the art of robotic assistants, and identify the major areas of improvement for robotic assistants to reach performance comparable to human interactions. Finally, we propose a minimal set of metrics that should be used in order to enable a fair comparison among the approaches.
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
Venue: arXiv cs.GT 2022
Year: 2022

We consider the $\varepsilon$-Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions that all of them simultaneously consider to be of approximately the same value (up to $\varepsilon$). This problem was recently shown to be PPA-complete, for $n$ agents and $n$ cuts, even for very simple valuation functions. In a quest to understand the root of the complexity of the problem, we consider the setting where there is only a constant number of agents, and we consider both the computational complexity and the query complexity of the problem. For agents with monotone valuation functions, we show a dichotomy: for two agents the problem is polynomial-time solvable, whereas for three or more agents it becomes PPA-complete. Similarly, we show that for two monotone agents the problem can be solved with polynomially-many queries, whereas for three or more agents, we provide exponential query complexity lower bounds. These results are enabled via an interesting connection to a monotone Borsuk-Ulam problem, which may be of independent interest. For agents with general valuations, we show that the problem is PPA-complete and admits exponential query complexity lower bounds, even for two agents.
Out-of-distribution Generalization via Partial Feature Decorrelation
Venue: arXiv cs.LG 2022
Year: 2022

Most deep-learning-based image classification methods assume that all samples are generated under an independent and identically distributed (IID) setting. However, out-of-distribution (OOD) generalization is more common in practice, which means an agnostic context distribution shift between training and testing environments. To address this problem, we present a novel Partial Feature Decorrelation Learning (PFDL) algorithm, which jointly optimizes a feature decomposition network and the target image classification model. The feature decomposition network decomposes feature embeddings into the independent and the correlated parts such that the correlations between features will be highlighted. Then, the correlated features help learn a stable feature representation by decorrelating the highlighted correlations while optimizing the image classification model. We verify the correlation modeling ability of the feature decomposition network on a synthetic dataset. The experiments on real-world datasets demonstrate that our method can improve the backbone model's accuracy on OOD image classification datasets.
On the Maximum Entropy of a Sum of Independent Discrete Random Variables
Venue: arXiv cs.IT 2022
Year: 2022

Let $ X_1, \ldots, X_n $ be independent random variables taking values in the alphabet $ \{0, 1, \ldots, r\} $, and $ S_n = \sum_{i = 1}^n X_i $. The Shepp--Olkin theorem states that, in the binary case ($ r = 1 $), the Shannon entropy of $ S_n $ is maximized when all the $ X_i $'s are uniformly distributed, i.e., Bernoulli(1/2). In an attempt to generalize this theorem to arbitrary finite alphabets, we obtain a lower bound on the maximum entropy of $ S_n $ and prove that it is tight in several special cases. In addition to these special cases, an argument is presented supporting the conjecture that the bound represents the optimal value for all $ n, r $, i.e., that $ H(S_n) $ is maximized when $ X_1, \ldots, X_{n-1} $ are uniformly distributed over $ \{0, r\} $, while the probability mass function of $ X_n $ is a mixture (with explicitly defined non-zero weights) of the uniform distributions over $ \{0, r\} $ and $ \{1, \ldots, r-1\} $.
Online Continual Learning under Extreme Memory Constraints
Venue: arXiv cs.CV 2022
Year: 2022

Continual Learning (CL) aims to develop agents emulating the human ability to sequentially learn new tasks while being able to retain knowledge obtained from past experiences. In this paper, we introduce the novel problem of Memory-Constrained Online Continual Learning (MC-OCL) which imposes strict constraints on the memory overhead that a possible algorithm can use to avoid catastrophic forgetting. As most, if not all, previous CL methods violate these constraints, we propose an algorithmic solution to MC-OCL: Batch-level Distillation (BLD), a regularization-based CL approach, which effectively balances stability and plasticity in order to learn from data streams, while preserving the ability to solve old tasks through distillation. Our extensive experimental evaluation, conducted on three publicly available benchmarks, empirically demonstrates that our approach successfully addresses the MC-OCL problem and achieves comparable accuracy to prior distillation methods requiring higher memory overhead.
Efficient Compactions Between Storage Tiers with PrismDB
Venue: arXiv cs.DB 2022
Year: 2022

In recent years, emerging storage hardware technologies have focused on divergent goals: better performance or lower cost-per-bit. Correspondingly, data systems that employ these technologies are typically optimized either to be fast (but expensive) or cheap (but slow). We take a different approach: by architecting a storage engine to natively utilize two tiers of fast and low-cost storage technologies, we can achieve a Pareto-efficient balance between performance and cost-per-bit. This paper presents the design and implementation of PrismDB, a novel key-value store that exploits two extreme ends of the spectrum of modern NVMe storage technologies (3D XPoint and QLC NAND) simultaneously. Our key contribution is how to efficiently migrate and compact data between two different storage tiers. Inspired by the classic cost-benefit analysis of log cleaning, we develop a new algorithm for multi-tiered storage compaction that balances the benefit of reclaiming space for hot objects in fast storage with the cost of compaction I/O in slow storage. Compared to the standard use of RocksDB on flash in datacenters today, PrismDB's average throughput on tiered storage is 3.3$\times$ faster and its read tail latency is 2$\times$ better, using equivalently priced hardware.
Sample-Efficient Training of Robotic Guide Using Human Path Prediction Network
Venue: arXiv cs.RO 2022
Year: 2022

Training a robot that engages with people is challenging; it is expensive to directly involve people in the training process, which requires numerous data samples. This paper presents an alternative approach for resolving this problem. We propose a human path prediction network (HPPN) that generates a user's future trajectory based on sequential robot actions and human responses using a recurrent-neural-network structure. Subsequently, an evolution-strategy-based robot training method using only the virtual human movements generated using the HPPN is presented. It is demonstrated that our proposed method permits sample-efficient training of a robotic guide for visually impaired people. By collecting only 1.5 K episodes from real users, we were able to train the HPPN and generate more than 100 K virtual episodes required for training the robot. The trained robot precisely guided blindfolded participants along a target path. Furthermore, using virtual episodes, we investigated a new reward design that prioritizes human comfort during the robot's guidance without incurring additional costs. This sample-efficient training method is expected to be widely applicable to future robots that interact physically with humans.
Approaching Neural Chinese Word Segmentation as a Low-Resource Machine Translation Task
Venue: arXiv cs.CL 2022
Year: 2022

Chinese word segmentation has entered the deep learning era which greatly reduces the hassle of feature engineering. Recently, some researchers attempted to treat it as character-level translation, which further simplified model designing, but there is a performance gap between the translation-based approach and other methods. This motivates our work, in which we apply the best practices from low-resource neural machine translation to supervised Chinese segmentation. We examine a series of techniques including regularization, data augmentation, objective weighting, transfer learning, and ensembling. Compared to previous works, our low-resource translation-based method maintains the effortless model design, yet achieves the same result as state of the art in the constrained evaluation without using additional data.
RGB cameras failures and their effects in autonomous driving applications
Venue: arXiv cs.CV 2022
Year: 2022

RGB cameras are one of the most relevant sensors for autonomous driving applications. It is undeniable that failures of vehicle cameras may compromise the autonomous driving task, possibly leading to unsafe behaviors when images that are subsequently processed by the driving system are altered. To support the definition of safe and robust vehicle architectures and intelligent systems, in this paper we define the failure modes of a vehicle camera, together with an analysis of effects and known mitigations. Further, we build a software library for the generation of the corresponding failed images and we feed them to six object detectors for mono and stereo cameras and to the self-driving agent of an autonomous driving simulator. The resulting misbehaviors with respect to operating with clean images allow a better understanding of failures effects and the related safety risks in image-based applications.