OpenRaiser/Intern-Atlas huggingface dataset:
Prediction of single well production rate in water-flooding oil fields driven by the fusion of static, temporal and spatial information
Venue: arXiv cs.LG 2023
Year: 2023

It is very difficult to forecast the production rate of oil wells as the output of a single well is sensitive to various uncertain factors, which implicitly or explicitly show the influence of the static, temporal and spatial properties on the oil well production. In this study, a novel machine learning model is constructed to fuse the static geological information, dynamic well production history, and spatial information of the adjacent water injection wells. There are 3 basic modules in this stacking model, which are regarded as the encoders to extract the features from different types of data. One is Multi-Layer Perceptron, which is to analyze the static geological properties of the reservoir that might influence the well production rate. The other two are both LSTMs, which have the input in the form of two matrices rather than vectors, standing for the temporal and the spatial information of the target well. The difference of the two modules is that in the spatial information processing module we take into consideration the time delay of water flooding response, from the injection well to the target well. In addition, we use Symbolic Transfer Entropy to prove the superiorities of the stacking model from the perspective of Causality Discovery. It is proved theoretically and practically that the presented model can make full use of the model structure to integrate the characteristics of the data and the experts' knowledge into the process of machine learning, greatly improving the accuracy and generalization ability of prediction.
Improved Deterministic Leader Election in Diameter-Two Networks
Venue: arXiv cs.DC 2023
Year: 2023

In this paper, we investigate the leader election problem in diameter-two networks. Recently, Chatterjee et al. [DC 2020] studied the leader election in diameter-two networks. They presented a $O(\log n)$-round deterministic {implicit} leader election algorithm which incurs optimal $O(n\log n)$ messages, but a drawback of their algorithm is that it requires knowledge of $n$. An important question -- whether it is possible to remove the assumption on the knowledge of $n$ was left open in their paper. Another interesting open question raised in their paper is whether {\em explicit} leader election can be solved in $\tilde{O}(n)$ messages deterministically. In this paper, we give an affirmative answer to them. Further, we solve the {\em broadcast problem}, another fundamental problem in distributed computing, deterministically in diameter-two networks with $\tilde{O}(n)$ messages and $\tilde{O}(1)$ rounds without the knowledge of $n$. In fact, we address all the open questions raised by Chatterjee et al. for the deterministic leader election problem in diameter-two networks. To the best of our knowledge, this is the first $\tilde{O}(n)$ deterministic result for the explicit leader election in the diameter-two networks, that too without the knowledge of $n$.
KS-DETR: Knowledge Sharing in Attention Learning for Detection Transformer
Venue: arXiv cs.CV 2023
Year: 2023

Scaled dot-product attention applies a softmax function on the scaled dot-product of queries and keys to calculate weights and then multiplies the weights and values. In this work, we study how to improve the learning of scaled dot-product attention to improve the accuracy of DETR. Our method is based on the following observations: using ground truth foreground-background mask (GT Fg-Bg Mask) as additional cues in the weights/values learning enables learning much better weights/values; with better weights/values, better values/weights can be learned. We propose a triple-attention module in which the first attention is a plain scaled dot-product attention, the second/third attention generates high-quality weights/values (with the assistance of GT Fg-Bg Mask) and shares the values/weights with the first attention to improve the quality of values/weights. The second and third attentions are removed during inference. We call our method knowledge-sharing DETR (KS-DETR), which is an extension of knowledge distillation (KD) in the way that the improved weights and values of the teachers (the second and third attentions) are directly shared, instead of mimicked, by the student (the first attention) to enable more efficient knowledge transfer from the teachers to the student. Experiments on various DETR-like methods show consistent improvements over the baseline methods on the MS COCO benchmark. Code is available at https://github.com/edocanonymous/KS-DETR.
Drugs Resistance Analysis from Scarce Health Records via Multi-task Graph Representation
Venue: arXiv cs.AI 2023
Year: 2023

Clinicians prescribe antibiotics by looking at the patient's health record with an experienced eye. However, the therapy might be rendered futile if the patient has drug resistance. Determining drug resistance requires time-consuming laboratory-level testing while applying clinicians' heuristics in an automated way is difficult due to the categorical or binary medical events that constitute health records. In this paper, we propose a novel framework for rapid clinical intervention by viewing health records as graphs whose nodes are mapped from medical events and edges as correspondence between events in given a time window. A novel graph-based model is then proposed to extract informative features and yield automated drug resistance analysis from those high-dimensional and scarce graphs. The proposed method integrates multi-task learning into a common feature extracting graph encoder for simultaneous analyses of multiple drugs as well as stabilizing learning. On a massive dataset comprising over 110,000 patients with urinary tract infections, we verify the proposed method is capable of attaining superior performance on the drug resistance prediction problem. Furthermore, automated drug recommendations resemblant to laboratory-level testing can also be made based on the model resistance analysis.
Learning Agile Flights through Narrow Gaps with Varying Angles using Onboard Sensing
Venue: arXiv cs.RO 2023
Year: 2023

This paper addresses the problem of traversing through unknown, tilted, and narrow gaps for quadrotors using Deep Reinforcement Learning (DRL). Previous learning-based methods relied on accurate knowledge of the environment, including the gap's pose and size. In contrast, we integrate onboard sensing and detect the gap from a single onboard camera. The training problem is challenging for two reasons: a precise and robust whole-body planning and control policy is required for variable-tilted and narrow gaps, and an effective Sim2Real method is needed to successfully conduct real-world experiments. To this end, we propose a learning framework for agile gap traversal flight, which successfully trains the vehicle to traverse through the center of the gap at an approximate attitude to the gap with aggressive tilted angles. The policy trained only in a simulation environment can be transferred into different domains with fine-tuning while maintaining the success rate. Our proposed framework, which integrates onboard sensing and a neural network controller, achieves a success rate of 84.51% in real-world experiments, with gap orientations up to 60deg. To the best of our knowledge, this is the first paper that performs the learning-based variable-tilted narrow gap traversal flight in the real world, without prior knowledge of the environment.
Considering Layerwise Importance in the Lottery Ticket Hypothesis
Venue: arXiv cs.CV 2023
Year: 2023

The Lottery Ticket Hypothesis (LTH) showed that by iteratively training a model, removing connections with the lowest global weight magnitude and rewinding the remaining connections, sparse networks can be extracted. This global comparison removes context information between connections within a layer. Here we study means for recovering some of this layer distributional context and generalise the LTH to consider weight importance values rather than global weight magnitudes. We find that given a repeatable training procedure, applying different importance metrics leads to distinct performant lottery tickets with little overlapping connections. This strongly suggests that lottery tickets are not unique
An agent-based model of the 2020 international policy diffusion in response to the COVID-19 pandemic with particle filter
Venue: arXiv cs.MA 2023
Year: 2023

Global problems, such as pandemics and climate change, require rapid international coordination and diffusion of policy. These phenomena are rare however, with one notable example being the international policy response to the COVID-19 pandemic in early 2020. Here we build an agent-based model of this rapid policy diffusion, where countries constitute the agents and with the principal mechanism for diffusion being peer mimicry. Since it is challenging to predict accurately the policy diffusion curve, we utilize data assimilation, that is an ``on-line'' feed of data to constrain the model against observations. The specific data assimilation algorithm we apply is a particle filter because of its convenient implementation, its ability to handle categorical variables and because the model is not overly computationally expensive, hence a more efficient algorithm is not required. We find that the model alone is able to predict the policy diffusion relatively well with an ensemble of at least 100 simulation runs. The particle filter however improves the fit to the data, reliably so from 500 runs upwards, and increasing filtering frequency results in improved prediction.
Complexity of Manipulating and Controlling Approval-Based Multiwinner Voting
Venue: arXiv cs.GT 2023
Year: 2023

We investigate the complexity of several manipulation and control problems under numerous prevalent approval-based multiwinner voting rules. Particularly, the rules we study include approval voting (AV), satisfaction approval voting (SAV), net-satisfaction approval voting (NSAV), proportional approval voting (PAV), approval-based Chamberlin-Courant voting (ABCCV), minimax approval voting (MAV), etc. We show that these rules generally resist the strategic types scrutinized in the paper, with only a few exceptions. In addition, we also obtain many fixed-parameter tractability results for these problems with respect to several natural parameters, and derive polynomial-time algorithms for certain special cases.
An End-To-End Encrypted Cache System with Time-Dependent Access Control
Venue: arXiv cs.CR 2023
Year: 2023

Due to the increasing use of encrypted communication, such as Transport Layer Security (TLS), encrypted cache systems are a promising approach for providing communication efficiency and privacy. Cache-22 is an encrypted cache system (Emura et al. ISITA 2020) that makes it possible to significantly reduce communication between a cache server and a service provider. In the final procedure of Cache-22, the service provider sends the corresponding decryption key to the user via TLS and this procedure allows the service provider to control which users can access the contents. For example, if a user has downloaded ciphertexts of several episodes of a show, the service provider can decide to provide some of the contents (e.g., the first episode) available for free while requiring a fee for the remaining contents. However, no concrete access control method has been implemented in the original Cache-22 system. In this paper, we add a scalable access control protocol to Cache-22. Specifically, we propose a time-dependent access control that requires a communication cost of $O(\log T_{\sf max})$ where $T_{\sf max}$ is the maximum time period. Although the protocol is stateful, we can provide time-dependent access control with scalability at the expense of this key management. We present experimental results and demonstrate that the modified system is effective for controlling access rights. We also observe a relationship between cache capacity and network traffic because the number of duplicated contents is higher than that in the original Cache-22 system, due to time-dependent access control.
Approximate spectral clustering with eigenvector selection and self-tuned $k$
Venue: arXiv cs.LG 2023
Year: 2023

The recently emerged spectral clustering surpasses conventional clustering methods by detecting clusters of any shape without the convexity assumption. Unfortunately, with a computational complexity of $O(n^3)$, it was infeasible for multiple real applications, where $n$ could be large. This stimulates researchers to propose the approximate spectral clustering (ASC). However, most of ASC methods assumed that the number of clusters $k$ was known. In practice, manual setting of $k$ could be subjective or time consuming. The proposed algorithm has two relevance metrics for estimating $k$ in two vital steps of ASC. One for selecting the eigenvectors spanning the embedding space, and the other to discover the number of clusters in that space. The algorithm used a growing neural gas (GNG) approximation, GNG is superior in preserving input data topology. The experimental setup demonstrates the efficiency of the proposed algorithm and its ability to compete with similar methods where $k$ was set manually.
Commonality in Recommender Systems: Evaluating Recommender Systems to Enhance Cultural Citizenship
Venue: arXiv cs.IR 2023
Year: 2023

Recommender systems have become the dominant means of curating cultural content, significantly influencing individual cultural experience. Since recommender systems tend to optimize for personalized user experience, they can overlook impacts on cultural experience in the aggregate. After demonstrating that existing metrics do not center culture, we introduce a new metric, commonality, that measures the degree to which recommendations familiarize a given user population with specified categories of cultural content. We developed commonality through an interdisciplinary dialogue between researchers in computer science and the social sciences and humanities. With reference to principles underpinning public service media systems in democratic societies, we identify universality of address and content diversity in the service of strengthening cultural citizenship as particularly relevant goals for recommender systems delivering cultural content. We develop commonality as a measure of recommender system alignment with the promotion of content toward a shared cultural experience across a population of users. We empirically compare the performance of recommendation algorithms using commonality with existing metrics, demonstrating that commonality captures a novel property of system behavior complementary to existing metrics. Alongside existing fairness and diversity metrics, commonality contributes to a growing body of scholarship developing `public good' rationales for machine learning systems.
Towards a Deep(er) Understanding of Interaction through Modeling, Simulation, and Optimization
Venue: arXiv cs.HC 2023
Year: 2023

The traditional user-centered design process can hardly keep up with the ever faster technical development and increasingly diverse user preferences. As a solution, we propose to augment the tried-and-tested approach of conducting user studies with simulation and optimization of the entire human-computer interaction loop. This approach allows to better understand phenomena through explicit modeling, build virtual prototypes through simulation, and improve interaction techniques through optimization. Building predictive user models also supports the creation and validation of HCI theories, and constitutes a decisive step towards new, intelligent, and adaptive user interfaces. We report our experience in virtually developing new interaction techniques on the example of acoustic levitation, and present our optimization-based framework for HCI. With this, we strive to gain a better understanding of interaction and at the same time feed the discussion on questions such as which tools and tutorials are necessary to make virtual prototyping more accessible to different audiences.
Delving into Identify-Emphasize Paradigm for Combating Unknown Bias
Venue: arXiv cs.LG 2023
Year: 2023

Dataset biases are notoriously detrimental to model robustness and generalization. The identify-emphasize paradigm appears to be effective in dealing with unknown biases. However, we discover that it is still plagued by two challenges: A, the quality of the identified bias-conflicting samples is far from satisfactory; B, the emphasizing strategies only produce suboptimal performance. In this paper, for challenge A, we propose an effective bias-conflicting scoring method (ECS) to boost the identification accuracy, along with two practical strategies -- peer-picking and epoch-ensemble. For challenge B, we point out that the gradient contribution statistics can be a reliable indicator to inspect whether the optimization is dominated by bias-aligned samples. Then, we propose gradient alignment (GA), which employs gradient statistics to balance the contributions of the mined bias-aligned and bias-conflicting samples dynamically throughout the learning process, forcing models to leverage intrinsic features to make fair decisions. Furthermore, we incorporate self-supervised (SS) pretext tasks into training, which enable models to exploit richer features rather than the simple shortcuts, resulting in more robust models. Experiments are conducted on multiple datasets in various settings, demonstrating that the proposed solution can mitigate the impact of unknown biases and achieve state-of-the-art performance.
Lower Bounds for Intersection Reporting among Flat Objects
Venue: arXiv cs.CG 2023
Year: 2023

Recently, Ezra and Sharir [ES22a] showed an $O(n^{3/2+σ})$ space and $O(n^{1/2+σ})$ query time data structure for ray shooting among triangles in $\mathbb{R}^3$. This improves the upper bound given by the classical $S(n)Q(n)^4=O(n^{4+σ})$ space-time tradeoff for the first time in almost 25 years and in fact lies on the tradeoff curve of $S(n)Q(n)^3=O(n^{3+σ})$. However, it seems difficult to apply their techniques beyond this specific space and time combination. This pheonomenon appears persistently in almost all recent advances of flat object intersection searching, e.g., line-tetrahedron intersection in $\mathbb{R}^4$ [ES22b], triangle-triangle intersection in $\mathbb{R}^4$ [ES22b], or even among flat semialgebraic objects [AAEKS22]. We give a timely explanation to this phenomenon from a lower bound perspective. We prove that given a set $\mathcal{S}$ of $(d-1)$-dimensional simplicies in $\mathbb{R}^d$, any data structure that can report all intersections with small ($n^{o(1)}$) query time must use $Ω(n^{2(d-1)-o(1)})$ space. This dashes the hope of any significant improvement to the tradeoff curves for small query time and almost matches the classical upper bound. We also obtain an almost matching space lower bound of $Ω(n^{6-o(1)})$ for triangle-triangle intersection reporting in $\mathbb{R}^4$ when the query time is small. Along the way, we further develop the previous lower bound techniques by Afshani and Cheng [AC21, AC22].
Degrees and Network Design: New Problems and Approximations
Venue: arXiv cs.DS 2023
Year: 2023

While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an objective, to minimize the maximum degree (e.g., the Minimum Degree Spanning Tree problem), or as constraints which might be violated to give bicriteria approximations (e.g., the Minimum Cost Degree Bounded Spanning Tree problem). We extend the study of degrees in network design in two ways. First, we introduce and study a new variant of the Survivable Network Design Problem where in addition to the traditional objective of minimizing the cost of the chosen edges, we add a constraint that the $\ell_p$-norm of the node degree vector is bounded by an input parameter. This interpolates between the classical settings of maximum degree (the $\ell_{\infty}$-norm) and the number of edges (the $\ell_1$-degree), and has natural applications in distributed systems and VLSI design. We give a constant bicriteria approximation in both measures using convex programming. Second, we provide a polylogrithmic bicriteria approximation for the Degree Bounded Group Steiner problem on bounded treewidth graphs, solving an open problem from [Kortsarz and Nutov, Discret. Appl. Math. 2022] and [Guo et al., Algorithmica 2022].
Matrix Multiplication and Number On the Forehead Communication
Venue: arXiv cs.CC 2023
Year: 2023

Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly on the other two players' heads, and promised that they are consistent with the inputs of of the other players. The set of all allowed inputs under this promise may be thought of as an order-3 tensor. We surprisingly observe that this tensor is exactly the matrix multiplication tensor, which is widely studied in the design of fast matrix multiplication algorithms. Using this connection, we prove a number of results about both Number On the Forehead communication and matrix multiplication, each by using known results or techniques about the other. For example, we show how the Laser method, a key technique used to design the best matrix multiplication algorithms, can also be used to design communication protocols for a variety of problems. We also show how known lower bounds for Number On the Forehead communication can be used to bound properties of the matrix multiplication tensor such as its zeroing out subrank. Finally, we substantially generalize known methods based on slice-rank for studying communication, and show how they directly relate to the matrix multiplication exponent $ω$.
Precoding-oriented Massive MIMO CSI Feedback Design
Venue: arXiv cs.IT 2023
Year: 2023

Downlink massive multiple-input multiple-output (MIMO) precoding algorithms in frequency division duplexing (FDD) systems rely on accurate channel state information (CSI) feedback from users. In this paper, we analyze the tradeoff between the CSI feedback overhead and the performance achieved by the users in systems in terms of achievable rate. The final goal of the proposed system is to determine the beamforming information (i.e., precoding) from channel realizations. We employ a deep learning-based approach to design the end-to-end precoding-oriented feedback architecture, that includes learned pilots, users' compressors, and base station processing. We propose a loss function that maximizes the sum of achievable rates with minimal feedback overhead. Simulation results show that our approach outperforms previous precoding-oriented methods, and provides more efficient solutions with respect to conventional methods that separate the CSI compression blocks from the precoding processing.