OpenRaiser/Intern-Atlas huggingface dataset:
Word Segmentation and Morphological Parsing for Sanskrit
Venue: arXiv cs.CL 2022
Year: 2022

We describe our participation in the Word Segmentation and Morphological Parsing (WSMP) for Sanskrit hackathon. We approach the word segmentation task as a sequence labelling task by predicting edit operations from which segmentations are derived. We approach the morphological analysis task by predicting morphological tags and rules that transform inflected words into their corresponding stems. Also, we propose an end-to-end trainable pipeline model for joint segmentation and morphological analysis. Our model performed best in the joint segmentation and analysis subtask (80.018 F1 score) and performed second best in the individual subtasks (segmentation: 96.189 F1 score / analysis: 69.180 F1 score). Finally, we analyse errors made by our models and suggest future work and possible improvements regarding data and evaluation.
A Two-Step Approach to Optimal Dynamic Pricing in Multi-Demand Combinatorial Markets
Venue: arXiv cs.GT 2022
Year: 2022

Online markets are a part of everyday life, and their rules are governed by algorithms. Assuming participants are inherently self-interested, well designed rules can help to increase social welfare. Many algorithms for online markets are based on prices: the seller is responsible for posting prices while buyers make purchases which are most profitable given the posted prices. To make adjustments to the market the seller is allowed to update prices at certain timepoints. Posted prices are an intuitive way to design a market. Despite the fact that each buyer acts selfishly, the seller's goal is often assumed to be that of social welfare maximization. Berger, Eden and Feldman recently considered the case of a market with only three buyers where each buyer has a fixed number of goods to buy and the profit of a bought bundle of items is the sum of profits of the items in the bundle. For such markets, Berger et. al. showed that the seller can maximize social welfare by dynamically updating posted prices before arrival of each buyer. Bérczi, Bérczi-Kovács and Szögi showed that the social welfare can be maximized also when each buyer is ready to buy at most two items. We study the power of posted prices with dynamical updates in more general cases. First, we show that the result of Berger et. al. can be generalized from three to four buyers. Then we show that the result of Bérczi, Bérczi-Kovács and Szögi can be generalized to the case when each buyer is ready to buy up to three items. We also show that a dynamic pricing is possible whenever there are at most two allocations maximizing social welfare.
N-HiTS: Neural Hierarchical Interpolation for Time Series Forecasting
Venue: arXiv cs.LG 2022
Year: 2022

Recent progress in neural forecasting accelerated improvements in the performance of large-scale forecasting systems. Yet, long-horizon forecasting remains a very difficult task. Two common challenges afflicting the task are the volatility of the predictions and their computational complexity. We introduce N-HiTS, a model which addresses both challenges by incorporating novel hierarchical interpolation and multi-rate data sampling techniques. These techniques enable the proposed method to assemble its predictions sequentially, emphasizing components with different frequencies and scales while decomposing the input signal and synthesizing the forecast. We prove that the hierarchical interpolation technique can efficiently approximate arbitrarily long horizons in the presence of smoothness. Additionally, we conduct extensive large-scale dataset experiments from the long-horizon forecasting literature, demonstrating the advantages of our method over the state-of-the-art methods, where N-HiTS provides an average accuracy improvement of almost 20% over the latest Transformer architectures while reducing the computation time by an order of magnitude (50 times). Our code is available at bit.ly/3VA5DoT
Learning Collective Action under Risk Diversity
Venue: arXiv cs.MA 2022
Year: 2022

Collective risk dilemmas (CRDs) are a class of n-player games that represent societal challenges where groups need to coordinate to avoid the risk of a disastrous outcome. Multi-agent systems incurring such dilemmas face difficulties achieving cooperation and often converge to sub-optimal, risk-dominant solutions where everyone defects. In this paper we investigate the consequences of risk diversity in groups of agents learning to play CRDs. We find that risk diversity places new challenges to cooperation that are not observed in homogeneous groups. We show that increasing risk diversity significantly reduces overall cooperation and hinders collective target achievement. It leads to asymmetrical changes in agents' policies -- i.e. the increase in contributions from individuals at high risk is unable to compensate for the decrease in contributions from individuals at low risk -- which overall reduces the total contributions in a population. When comparing RL behaviors to rational individualistic and social behaviors, we find that RL populations converge to fairer contributions among agents. Our results highlight the need for aligning risk perceptions among agents or develop new learning techniques that explicitly account for risk diversity.
Road User Position Prediction in Urban Environments via Locally Weighted Learning
Venue: arXiv cs.CE 2022
Year: 2022

This paper focuses on the problem of predicting the future position of a target road user given its current state, consisting of position and velocity. A weighted average approach is adopted, where the weights are determined from data containing the state trajectories of previously observed road users. In particular, a similarity function is introduced to extract from data those previously observed road users' states that are most similar to the target's one. This formulation results in an easily interpretable model with few parameters to calibrate. The performance of this weighted average model(WAM) is evaluated on the same real-world data as state-of-the-art methods, showing promising results. WAM outperforms the baseline constant velocity model at longer prediction horizons, making WAM suitable for motion planning applications. WAM and a baseline neural network model performs comparably. Still, WAM has only three parameters which are easily interpretable, while the complex neural network model has thousands of parameters which are difficult to analyze.
Augmenting Novelty Search with a Surrogate Model to Engineer Meta-Diversity in Ensembles of Classifiers
Venue: arXiv cs.LG 2022
Year: 2022

Using Neuroevolution combined with Novelty Search to promote behavioural diversity is capable of constructing high-performing ensembles for classification. However, using gradient descent to train evolved architectures during the search can be computationally prohibitive. Here we propose a method to overcome this limitation by using a surrogate model which estimates the behavioural distance between two neural network architectures required to calculate the sparseness term in Novelty Search. We demonstrate a speedup of 10 times over previous work and significantly improve on previous reported results on three benchmark datasets from Computer Vision -- CIFAR-10, CIFAR-100, and SVHN. This results from the expanded architecture search space facilitated by using a surrogate. Our method represents an improved paradigm for implementing horizontal scaling of learning algorithms by making an explicit search for diversity considerably more tractable for the same bounded resources.
Interpretable AI-based Large-scale 3D Pathloss Prediction Model for enabling Emerging Self-Driving Networks
Venue: arXiv cs.NI 2022
Year: 2022

In modern wireless communication systems, radio propagation modeling to estimate pathloss has always been a fundamental task in system design and optimization. The state-of-the-art empirical propagation models are based on measurements in specific environments and limited in their ability to capture idiosyncrasies of various propagation environments. To cope with this problem, ray-tracing based solutions are used in commercial planning tools, but they tend to be extremely time-consuming and expensive. We propose a Machine Learning (ML)-based model that leverages novel key predictors for estimating pathloss. By quantitatively evaluating the ability of various ML algorithms in terms of predictive, generalization and computational performance, our results show that Light Gradient Boosting Machine (LightGBM) algorithm overall outperforms others, even with sparse training data, by providing a 65% increase in prediction accuracy as compared to empirical models and 13x decrease in prediction time as compared to ray-tracing. To address the interpretability challenge that thwarts the adoption of most ML-based models, we perform extensive secondary analysis using SHapley Additive exPlanations (SHAP) method, yielding many practically useful insights that can be leveraged for intelligently tuning the network configuration, selective enrichment of training data in real networks and for building lighter ML-based propagation model to enable low-latency use-cases.
Probe-Based Interventions for Modifying Agent Behavior
Venue: arXiv cs.LG 2022
Year: 2022

Neural nets are powerful function approximators, but the behavior of a given neural net, once trained, cannot be easily modified. We wish, however, for people to be able to influence neural agents' actions despite the agents never training with humans, which we formalize as a human-assisted decision-making problem. Inspired by prior art initially developed for model explainability, we develop a method for updating representations in pre-trained neural nets according to externally-specified properties. In experiments, we show how our method may be used to improve human-agent team performance for a variety of neural networks from image classifiers to agents in multi-agent reinforcement learning settings.
Topology-Preserving Dimensionality Reduction via Interleaving Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Dimensionality reduction techniques are powerful tools for data preprocessing and visualization which typically come with few guarantees concerning the topological correctness of an embedding. The interleaving distance between the persistent homology of Vietoris-Rips filtrations can be used to identify a scale at which topological features such as clusters or holes in an embedding and original data set are in correspondence. We show how optimization seeking to minimize the interleaving distance can be incorporated into dimensionality reduction algorithms, and explicitly demonstrate its use in finding an optimal linear projection. We demonstrate the utility of this framework to data visualization.
A Flexible IAB Architecture for Beyond 5G Network
Venue: arXiv cs.NI 2022
Year: 2022

IAB is an innovative wireless backhaul solution to provide cost-efficient deployment of small cells for successful 5G adoption. Besides, IAB can utilize the same spectrum for access and backhaul purposes. The 3GPP standardized IAB in Release 16 and would incorporate a few enhancements in the upcoming releases. The 3GPP IAB architecture, however, suffers from some limitations, such as it does not support mobile relays or dual-connectivity. This article presents a novel IAB architecture that addresses these limitations and is transparent to legacy operations of the 5G system. The architecture also supports multi-RAT coexistence where access and backhaul may belong to different RATs. These factors (and many others) enable operators to capitalize on the architecture for deploying IAB anywhere in a plug-and-play manner. We also show the merits of the architecture by evaluating its capacity and mobility robustness compared to the 3GPP architecture. Simulation results corroborate our design approach. Owing its robust design, the architecture can contend for standardization in B5G system.
Securing Federated Sensitive Topic Classification against Poisoning Attacks
Venue: arXiv cs.CR 2022
Year: 2022

We present a Federated Learning (FL) based solution for building a distributed classifier capable of detecting URLs containing GDPR-sensitive content related to categories such as health, sexual preference, political beliefs, etc. Although such a classifier addresses the limitations of previous offline/centralised classifiers,it is still vulnerable to poisoning attacks from malicious users that may attempt to reduce the accuracy for benign users by disseminating faulty model updates. To guard against this, we develop a robust aggregation scheme based on subjective logic and residual-based attack detection. Employing a combination of theoretical analysis, trace-driven simulation, as well as experimental validation with a prototype and real users, we show that our classifier can detect sensitive content with high accuracy, learn new labels fast, and remain robust in view of poisoning attacks from malicious users, as well as imperfect input from non-malicious ones.
How Vulnerable is an Undirected Planar Graph with respect to Max Flow
Venue: arXiv cs.DS 2022
Year: 2022

We study the problem of computing the vitality of edges and vertices with respect to the $st$-max flow in undirected planar graphs, where the vitality of an edge/vertex is the $st$-max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the $st$-max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute $st$-max flow $O(n\log\log n)$. We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in $O(n)$ space.
Lessons from the AdKDD'21 Privacy-Preserving ML Challenge
Venue: arXiv cs.LG 2022
Year: 2022

Designing data sharing mechanisms providing performance and strong privacy guarantees is a hot topic for the Online Advertising industry. Namely, a prominent proposal discussed under the Improving Web Advertising Business Group at W3C only allows sharing advertising signals through aggregated, differentially private reports of past displays. To study this proposal extensively, an open Privacy-Preserving Machine Learning Challenge took place at AdKDD'21, a premier workshop on Advertising Science with data provided by advertising company Criteo. In this paper, we describe the challenge tasks, the structure of the available datasets, report the challenge results, and enable its full reproducibility. A key finding is that learning models on large, aggregated data in the presence of a small set of unaggregated data points can be surprisingly efficient and cheap. We also run additional experiments to observe the sensitivity of winning methods to different parameters such as privacy budget or quantity of available privileged side information. We conclude that the industry needs either alternate designs for private data sharing or a breakthrough in learning with aggregated data only to keep ad relevance at a reasonable level.
SPAGHETTI: Editing Implicit Shapes Through Part Aware Generation
Venue: arXiv cs.GR 2022
Year: 2022

Neural implicit fields are quickly emerging as an attractive representation for learning based techniques. However, adopting them for 3D shape modeling and editing is challenging. We introduce a method for $\mathbf{E}$diting $\mathbf{I}$mplicit $\mathbf{S}$hapes $\mathbf{T}$hrough $\mathbf{P}$art $\mathbf{A}$ware $\mathbf{G}$enera$\mathbf{T}$ion, permuted in short as SPAGHETTI. Our architecture allows for manipulation of implicit shapes by means of transforming, interpolating and combining shape segments together, without requiring explicit part supervision. SPAGHETTI disentangles shape part representation into extrinsic and intrinsic geometric information. This characteristic enables a generative framework with part-level control. The modeling capabilities of SPAGHETTI are demonstrated using an interactive graphical interface, where users can directly edit neural implicit shapes.
Resultant Tools for Parametric Polynomial Systems with Application to Population Models
Venue: arXiv cs.SC 2022
Year: 2022

We are concerned with the problem of decomposing the parameter space of a parametric system of polynomial equations, and possibly some polynomial inequality constraints, with respect to the number of real solutions that the system attains. Previous studies apply a two step approach to this problem, where first the discriminant variety of the system is computed via a Groebner Basis (GB), and then a Cylindrical Algebraic Decomposition (CAD) of this is produced to give the desired computation. However, even on some reasonably small applied examples this process is too expensive, with computation of the discriminant variety alone infeasible. In this paper we develop new approaches to build the discriminant variety using resultant methods (the Dixon resultant and a new method using iterated univariate resultants). This reduces the complexity compared to GB and allows for a previous infeasible example to be tackled. We demonstrate the benefit by giving a symbolic solution to a problem from population dynamics -- the analysis of the steady states of three connected populations which exhibit Allee effects - which previously could only be tackled numerically.
Differentiable Neural Radiosity
Venue: arXiv cs.GR 2022
Year: 2022

We introduce Differentiable Neural Radiosity, a novel method of representing the solution of the differential rendering equation using a neural network. Inspired by neural radiosity techniques, we minimize the norm of the residual of the differential rendering equation to directly optimize our network. The network is capable of outputting continuous, view-independent gradients of the radiance field with respect to scene parameters, taking into account differential global illumination effects while keeping memory and time complexity constant in path length. To solve inverse rendering problems, we use a pre-trained instance of our network that represents the differential radiance field with respect to a limited number of scene parameters. In our experiments, we leverage this to achieve faster and more accurate convergence compared to other techniques such as Automatic Differentiation, Radiative Backpropagation, and Path Replay Backpropagation.
Combining Local and Global Pose Estimation for Precise Tracking of Similar Objects
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we present a multi-object 6D detection and tracking pipeline for potentially similar and non-textured objects. The combination of a convolutional neural network for object classification and rough pose estimation with a local pose refinement and an automatic mismatch detection enables direct application in real-time AR scenarios. A new network architecture, trained solely with synthetic images, allows simultaneous pose estimation of multiple objects with reduced GPU memory consumption and enhanced performance. In addition, the pose estimates are further improved by a local edge-based refinement step that explicitly exploits known object geometry information. For continuous movements, the sole use of local refinement reduces pose mismatches due to geometric ambiguities or occlusions. We showcase the entire tracking pipeline and demonstrate the benefits of the combined approach. Experiments on a challenging set of non-textured similar objects demonstrate the enhanced quality compared to the baseline method. Finally, we illustrate how the system can be used in a real AR assistance application within the field of construction.
Top-K Ranking Deep Contextual Bandits for Information Selection Systems
Venue: arXiv cs.LG 2022
Year: 2022

In today's technology environment, information is abundant, dynamic, and heterogeneous in nature. Automated filtering and prioritization of information is based on the distinction between whether the information adds substantial value toward one's goal or not. Contextual multi-armed bandit has been widely used for learning to filter contents and prioritize according to user interest or relevance. Learn-to-Rank technique optimizes the relevance ranking on items, allowing the contents to be selected accordingly. We propose a novel approach to top-K rankings under the contextual multi-armed bandit framework. We model the stochastic reward function with a neural network to allow non-linear approximation to learn the relationship between rewards and contexts. We demonstrate the approach and evaluate the the performance of learning from the experiments using real world data sets in simulated scenarios. Empirical results show that this approach performs well under the complexity of a reward structure and high dimensional contextual features.
Fragmented ARES: Dynamic Storage for Large Objects
Venue: arXiv cs.DC 2022
Year: 2022

Data availability is one of the most important features in distributed storage systems, made possible by data replication. Nowadays data are generated rapidly and the goal to develop efficient, scalable and reliable storage systems has become one of the major challenges for high performance computing. In this work, we develop a dynamic, robust and strongly consistent distributed storage implementation suitable for handling large objects (such as files). We do so by integrating an Adaptive, Reconfigurable, Atomic Storage framework, called ARES, with a distributed file system, called COBFS, which relies on a block fragmentation technique to handle large objects. With the addition of ARES, we also enable the use of an erasure-coded algorithm to further split our data and to potentially improve storage efficiency at the replica servers and operation latency. To put the practicality of our outcomes at test, we conduct an in-depth experimental evaluation on the Emulab and AWS EC2 testbeds, illustrating the benefits of our approaches, as well as other interesting tradeoffs.
A Formal Model of Checked C
Venue: arXiv cs.PL 2022
Year: 2022

We present a formal model of Checked C, a dialect of C that aims to enforce spatial memory safety. Our model pays particular attention to the semantics of dynamically sized, potentially null-terminated arrays. We formalize this model in Coq, and prove that any spatial memory safety errors can be blamed on portions of the program labeled unchecked; this is a Checked C feature that supports incremental porting and backward compatibility. While our model's operational semantics uses annotated ("fat") pointers to enforce spatial safety, we show that such annotations can be safely erased: Using PLT Redex we formalize an executable version of our model and a compilation procedure from it to an untyped C-like language, and use randomized testing to validate that generated code faithfully simulates the original. Finally, we develop a custom random generator for well-typed and almost-well-typed terms in our Redex model, and use it to search for inconsistencies between our model and the Clang Checked C implementation. We find these steps to be a useful way to co-develop a language (Checked C is still in development) and a core model of it.