OpenRaiser/Intern-Atlas huggingface dataset:
Age of Information of a Power Constrained Scheduler in the Presence of a Power Constrained Adversary
Venue: arXiv cs.IT 2023
Year: 2023

We consider a time slotted communication network consisting of a base station (BS), an adversary, $N$ users and $N_s$ communication channels. Both the BS and the adversary have average power constraints and the probability of successful transmission of an update packet depends on the transmission power of the BS and the blocking power of the adversary. We provide a universal lower bound for the average age for this communication network. We prove that the uniform scheduling algorithm with any feasible transmission power choosing policy is $4$ optimal; and the max-age user choosing policy is $2$ optimal. In the second part of the paper, we consider the setting where the BS chooses a transmission policy and the adversary chooses a blocking policy from the set of randomized stationary policies. We show that the Nash equilibrium point may or may not exist for this communication network. We find special cases where the Nash equilibrium always exists.
Graphical House Allocation
Venue: arXiv cs.GT 2023
Year: 2023

The classical house allocation problem involves assigning $n$ houses (or items) to $n$ agents according to their preferences. A key criterion in such problems is satisfying some fairness constraints such as envy-freeness. We consider a generalization of this problem wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of all pairwise envy values over all edges in a social graph. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied problem of linear arrangements. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NP-hardness results for disjoint unions of paths, cycles, stars, or cliques, and fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call separability which results in efficient parameterized algorithms for finding optimal allocations.
Explainability and Robustness of Deep Visual Classification Models
Venue: arXiv cs.CV 2023
Year: 2023

In the computer vision community, Convolutional Neural Networks (CNNs), first proposed in the 1980's, have become the standard visual classification model. Recently, as alternatives to CNNs, Capsule Networks (CapsNets) and Vision Transformers (ViTs) have been proposed. CapsNets, which were inspired by the information processing of the human brain, are considered to have more inductive bias than CNNs, whereas ViTs are considered to have less inductive bias than CNNs. All three classification models have received great attention since they can serve as backbones for various downstream tasks. However, these models are far from being perfect. As pointed out by the community, there are two weaknesses in standard Deep Neural Networks (DNNs). One of the limitations of DNNs is the lack of explainability. Even though they can achieve or surpass human expert performance in the image classification task, the DNN-based decisions are difficult to understand. In many real-world applications, however, individual decisions need to be explained. The other limitation of DNNs is adversarial vulnerability. Concretely, the small and imperceptible perturbations of inputs can mislead DNNs. The vulnerability of deep neural networks poses challenges to current visual classification models. The potential threats thereof can lead to unacceptable consequences. Besides, studying model adversarial vulnerability can lead to a better understanding of the underlying models. Our research aims to address the two limitations of DNNs. Specifically, we focus on deep visual classification models, especially the core building parts of each classification model, e.g. dynamic routing in CapsNets and self-attention module in ViTs.
DADAgger: Disagreement-Augmented Dataset Aggregation
Venue: arXiv cs.LG 2023
Year: 2023

DAgger is an imitation algorithm that aggregates its original datasets by querying the expert on all samples encountered during training. In order to reduce the number of samples queried, we propose a modification to DAgger, known as DADAgger, which only queries the expert for state-action pairs that are out of distribution (OOD). OOD states are identified by measuring the variance of the action predictions of an ensemble of models on each state, which we simulate using dropout. Testing on the Car Racing and Half Cheetah environments achieves comparable performance to DAgger but with reduced expert queries, and better performance than a random sampling baseline. We also show that our algorithm may be used to build efficient, well-balanced training datasets by running with no initial data and only querying the expert to resolve uncertainty.
Online Learning of Smooth Functions
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we study the online learning of real-valued functions where the hidden function is known to have certain smoothness properties. Specifically, for $q \ge 1$, let $\mathcal F_q$ be the class of absolutely continuous functions $f: [0,1] \to \mathbb R$ such that $\|f'\|_q \le 1$. For $q \ge 1$ and $d \in \mathbb Z^+$, let $\mathcal F_{q,d}$ be the class of functions $f: [0,1]^d \to \mathbb R$ such that any function $g: [0,1] \to \mathbb R$ formed by fixing all but one parameter of $f$ is in $\mathcal F_q$. For any class of real-valued functions $\mathcal F$ and $p>0$, let $\text{opt}_p(\mathcal F)$ be the best upper bound on the sum of $p^{\text{th}}$ powers of absolute prediction errors that a learner can guarantee in the worst case. In the single-variable setup, we find new bounds for $\text{opt}_p(\mathcal F_q)$ that are sharp up to a constant factor. We show for all $\varepsilon \in (0, 1)$ that $\text{opt}_{1+\varepsilon}(\mathcal{F}_{\infty}) = Θ(\varepsilon^{-\frac{1}{2}})$ and $\text{opt}_{1+\varepsilon}(\mathcal{F}_q) = Θ(\varepsilon^{-\frac{1}{2}})$ for all $q \ge 2$. We also show for $\varepsilon \in (0,1)$ that $\text{opt}_2(\mathcal F_{1+\varepsilon})=Θ(\varepsilon^{-1})$. In addition, we obtain new exact results by proving that $\text{opt}_p(\mathcal F_q)=1$ for $q \in (1,2)$ and $p \ge 2+\frac{1}{q-1}$. In the multi-variable setup, we establish inequalities relating $\text{opt}_p(\mathcal F_{q,d})$ to $\text{opt}_p(\mathcal F_q)$ and show that $\text{opt}_p(\mathcal F_{\infty,d})$ is infinite when $p<d$ and finite when $p>d$. We also obtain sharp bounds on learning $\mathcal F_{\infty,d}$ for $p < d$ when the number of trials is bounded.
Building Coverage Estimation with Low-resolution Remote Sensing Imagery
Venue: arXiv cs.CV 2023
Year: 2023

Building coverage statistics provide crucial insights into the urbanization, infrastructure, and poverty level of a region, facilitating efforts towards alleviating poverty, building sustainable cities, and allocating infrastructure investments and public service provision. Global mapping of buildings has been made more efficient with the incorporation of deep learning models into the pipeline. However, these models typically rely on high-resolution satellite imagery which are expensive to collect and infrequently updated. As a result, building coverage data are not updated timely especially in developing regions where the built environment is changing quickly. In this paper, we propose a method for estimating building coverage using only publicly available low-resolution satellite imagery that is more frequently updated. We show that having a multi-node quantile regression layer greatly improves the model's spatial and temporal generalization. Our model achieves a coefficient of determination ($R^2$) as high as 0.968 on predicting building coverage in regions of different levels of development around the world. We demonstrate that the proposed model accurately predicts the building coverage from raw input images and generalizes well to unseen countries and continents, suggesting the possibility of estimating global building coverage using only low-resolution remote sensing data.
Accurate, Low-latency, Efficient SAR Automatic Target Recognition on FPGA
Venue: arXiv cs.AR 2023
Year: 2023

Synthetic aperture radar (SAR) automatic target recognition (ATR) is the key technique for remote-sensing image recognition. The state-of-the-art convolutional neural networks (CNNs) for SAR ATR suffer from \emph{high computation cost} and \emph{large memory footprint}, making them unsuitable to be deployed on resource-limited platforms, such as small/micro satellites. In this paper, we propose a comprehensive GNN-based model-architecture {co-design} on FPGA to address the above issues. \emph{Model design}: we design a novel graph neural network (GNN) for SAR ATR. The proposed GNN model incorporates GraphSAGE layer operators and attention mechanism, achieving comparable accuracy as the state-of-the-art work with near $1/100$ computation cost. Then, we propose a pruning approach including weight pruning and input pruning. While weight pruning through lasso regression reduces most parameters without accuracy drop, input pruning eliminates most input pixels with negligible accuracy drop. \emph{Architecture design}: to fully unleash the computation parallelism within the proposed model, we develop a novel unified hardware architecture that can execute various computation kernels (feature aggregation, feature transformation, graph pooling). The proposed hardware design adopts the Scatter-Gather paradigm to efficiently handle the irregular computation {patterns} of various computation kernels. We deploy the proposed design on an embedded FPGA (AMD Xilinx ZCU104) and evaluate the performance using MSTAR dataset. Compared with the state-of-the-art CNNs, the proposed GNN achieves comparable accuracy with $1/3258$ computation cost and $1/83$ model size. Compared with the state-of-the-art CPU/GPU, our FPGA accelerator achieves $14.8\times$/$2.5\times$ speedup (latency) and is $62\times$/$39\times$ more energy efficient.
Identifying Personal Data Processing for Code Review
Venue: arXiv cs.SE 2023
Year: 2023

Code review is a critical step in the software development life cycle, which assesses and boosts the code's effectiveness and correctness, pinpoints security issues, and raises its quality by adhering to best practices. Due to the increased need for personal data protection motivated by legislation, code reviewers need to understand where personal data is located in software systems and how it is handled. Although most recent work on code review focuses on security vulnerabilities, privacy-related techniques are not easy for code reviewers to implement, making their inclusion in the code review process challenging. In this paper, we present ongoing work on a new approach to identifying personal data processing, enabling developers and code reviewers in drafting privacy analyses and complying with regulations such as the General Data Protection Regulation (GDPR).
Reconstructing words using queries on subwords or factors
Venue: arXiv cs.DM 2023
Year: 2023

We study word reconstruction problems. Improving a previous result by P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka and M. Rigo, we prove that, for any unknown word $w$ of length $n$ over an alphabet of cardinality $k$, $w$ can be reconstructed from the number of occurrences as subwords (or scattered factors) of $O(k^2\sqrt{n\log_2(n)})$ words. Two previous upper bounds obtained by S. S. Skiena and G. Sundaram are also slightly improved: one when considering information on the existence of subwords instead of on the numbers of their occurrences, and, the other when considering information on the existence of factors.
FATE in AI: Towards Algorithmic Inclusivity and Accessibility
Venue: arXiv cs.CY 2023
Year: 2023

Artificial Intelligence (AI) is at the forefront of modern technology, and its effects are felt in many areas of society. To prevent algorithmic disparities, fairness, accountability, transparency, and ethics (FATE) in AI are being implemented. However, the current discourse on these issues is largely dominated by more economically developed countries (MEDC), leaving out local knowledge, cultural pluralism, and global fairness. This study aims to address this gap by examining FATE-related desiderata, particularly transparency and ethics, in areas of the global South that are underserved by AI. A user study (n=43) and a participatory session (n=30) were conducted to achieve this goal. The results showed that AI models can encode bias and amplify stereotypes. To promote inclusivity, a community-led strategy is proposed to collect and curate representative data for responsible AI design. This will enable the affected community or individuals to monitor the increasing use of AI-powered systems. Additionally, recommendations based on public input are provided to ensure that AI adheres to social values and context-specific FATE needs.
Towards The Creation Of The Future Fish Farm
Venue: arXiv cs.CY 2023
Year: 2023

A fish farm is an area where fish raise and bred for food. Fish farm environments support the care and management of seafood within a controlled environment. Over the past few decades, there has been a remarkable increase in the calorie intake of protein attributed to seafood. Along with this, there are significant opportunities within the fish farming industry for economic development. Determining the fish diseases, monitoring the aquatic organisms, and examining the imbalance in the water element are some key factors that require precise observation to determine the accuracy of the acquired data. Similarly, due to the rapid expansion of aquaculture, new technologies are constantly being implemented in this sector to enhance efficiency. However, the existing approaches have often failed to provide an efficient method of farming fish. This work has kept aside the traditional approaches and opened up new dimensions to perform accurate analysis by adopting a distributed ledger technology. Our work analyses the current state-of-the-art of fish farming and proposes a fish farm ecosystem that relies on a private-by-design architecture based on the Hyperledger Fabric private-permissioned distributed ledger technology. The proposed method puts forward accurate and secure storage of the retrieved data from multiple sensors across the ecosystem so that the adhering entities can exercise their decision based on the acquired data. This study demonstrates a proof-of-concept to signify the efficiency and usability of the future fish farm.
Grammar construction methods for extended deterministic expressions
Venue: arXiv cs.CL 2023
Year: 2023

Extended regular expressions with counting and interleaving are widely used in practice. However the related theoretical studies for this kind of expressions currently cannot meet the need of practical work. This paper develops syntax definitions for extended deterministic expressions and their subclasses, hope to completely solve the long-standing problem that there are no syntax definitions for this kind of expressions, which has become an important reason for restricting the use of extended expressions.
Technology Trends for Massive MIMO towards 6G
Venue: arXiv cs.IT 2023
Year: 2023

At the dawn of the next-generation wireless systems and networks, massive multiple-input multiple-output (MIMO) has been envisioned as one of the enabling technologies. With the continued success of being applied in the 5G and beyond, the massive MIMO technology has demonstrated its advantageousness, integrability, and extendibility. Moreover, several evolutionary features and revolutionizing trends for massive MIMO have gradually emerged in recent years, which are expected to reshape the future 6G wireless systems and networks. Specifically, the functions and performance of future massive MIMO systems will be enabled and enhanced via combining other innovative technologies, architectures, and strategies such as intelligent omni-surfaces (IOSs)/intelligent reflecting surfaces (IRSs), artificial intelligence (AI), THz communications, cell free architecture. Also, more diverse vertical applications based on massive MIMO will emerge and prosper, such as wireless localization and sensing, vehicular communications, non-terrestrial communications, remote sensing, inter-planetary communications.
Radiance Textures for Rasterizing Ray-Traced Data
Venue: arXiv cs.GR 2023
Year: 2023

Presenting real-time rendering of 3D surfaces using radiance textures for fast synthesis of complex incidence-variable effects and environment interactions. This includes iridescence, parallax occlusion and interior mapping, (specular, regular, diffuse, total-internal) reflections with many bounces, refraction, subsurface scattering, transparency, and possibly more. This method divides textures into a matrix of radiance buckets, where each bucket represent some data at various incidence angles. Data can show final pixel color, or deferred rendering ambient occlusion, reflections, shadow map, etc. Resolution of the final synthesized output is the radiance bucket matrix size. Technique can be implemented with a simple fragment shader. The computational footprint of this technique is of simple diffuse-only graphics, but with visual fidelity of complex (off-line) ray-traced render at the cost of storage memory footprint. Balance between computational footprint and storage memory footprint can be easily achieved with variable compression ratio of repetitive radiance scene textures.
GUAP: Graph Universal Attack Through Adversarial Patching
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural networks (GNNs) are a class of effective deep learning models for node classification tasks; yet their predictive capability may be severely compromised under adversarially designed unnoticeable perturbations to the graph structure and/or node data. Most of the current work on graph adversarial attacks aims at lowering the overall prediction accuracy, but we argue that the resulting abnormal model performance may catch attention easily and invite quick counterattack. Moreover, attacks through modification of existing graph data may be hard to conduct if good security protocols are implemented. In this work, we consider an easier attack harder to be noticed, through adversarially patching the graph with new nodes and edges. The attack is universal: it targets a single node each time and flips its connection to the same set of patch nodes. The attack is unnoticeable: it does not modify the predictions of nodes other than the target. We develop an algorithm, named GUAP, that achieves high attack success rate but meanwhile preserves the prediction accuracy. GUAP is fast to train by employing a sampling strategy. We demonstrate that a 5% sampling in each epoch yields 20x speedup in training, with only a slight degradation in attack performance. Additionally, we show that the adversarial patch trained with the graph convolutional network transfers well to other GNNs, such as the graph attention network.
Iterated Decomposition: Improving Science Q&A by Supervising Reasoning Processes
Venue: arXiv cs.CL 2023
Year: 2023

Language models (LMs) can perform complex reasoning either end-to-end, with hidden latent state, or compositionally, with transparent intermediate state. Composition offers benefits for interpretability and safety, but may need workflow support and infrastructure to remain competitive. We describe iterated decomposition, a human-in-the-loop workflow for developing and refining compositional LM programs. We improve the performance of compositions by zooming in on failing components and refining them through decomposition, additional context, chain of thought, etc. To support this workflow, we develop ICE, an open-source tool for visualizing the execution traces of LM programs. We apply iterated decomposition to three real-world tasks and improve the accuracy of LM programs over less compositional baselines: describing the placebo used in a randomized controlled trial (25% to 65%), evaluating participant adherence to a medical intervention (53% to 70%), and answering NLP questions on the Qasper dataset (38% to 69%). These applications serve as case studies for a workflow that, if automated, could keep ML systems interpretable and safe even as they scale to increasingly complex tasks.
UniHD at TSAR-2022 Shared Task: Is Compute All We Need for Lexical Simplification?
Venue: arXiv cs.CL 2023
Year: 2023

Previous state-of-the-art models for lexical simplification consist of complex pipelines with several components, each of which requires deep technical knowledge and fine-tuned interaction to achieve its full potential. As an alternative, we describe a frustratingly simple pipeline based on prompted GPT-3 responses, beating competing approaches by a wide margin in settings with few training instances. Our best-performing submission to the English language track of the TSAR-2022 shared task consists of an ``ensemble'' of six different prompt templates with varying context levels. As a late-breaking result, we further detail a language transfer technique that allows simplification in languages other than English. Applied to the Spanish and Portuguese subset, we achieve state-of-the-art results with only minor modification to the original prompts. Aside from detailing the implementation and setup, we spend the remainder of this work discussing the particularities of prompting and implications for future work. Code for the experiments is available online at https://github.com/dennlinger/TSAR-2022-Shared-Task
Infomaxformer: Maximum Entropy Transformer for Long Time-Series Forecasting Problem
Venue: arXiv cs.LG 2023
Year: 2023

The Transformer architecture yields state-of-the-art results in many tasks such as natural language processing (NLP) and computer vision (CV), since the ability to efficiently capture the precise long-range dependency coupling between input sequences. With this advanced capability, however, the quadratic time complexity and high memory usage prevents the Transformer from dealing with long time-series forecasting problem (LTFP). To address these difficulties: (i) we revisit the learned attention patterns of the vanilla self-attention, redesigned the calculation method of self-attention based the Maximum Entropy Principle. (ii) we propose a new method to sparse the self-attention, which can prevent the loss of more important self-attention scores due to random sampling.(iii) We propose Keys/Values Distilling method motivated that a large amount of feature in the original self-attention map is redundant, which can further reduce the time and spatial complexity and make it possible to input longer time-series. Finally, we propose a method that combines the encoder-decoder architecture with seasonal-trend decomposition, i.e., using the encoder-decoder architecture to capture more specific seasonal parts. A large number of experiments on several large-scale datasets show that our Infomaxformer is obviously superior to the existing methods. We expect this to open up a new solution for Transformer to solve LTFP, and exploring the ability of the Transformer architecture to capture much longer temporal dependencies.