OpenRaiser/Intern-Atlas huggingface dataset:
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
Venue: arXiv cs.DS 2022
Year: 2022

Schelling's model considers $k$ types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers to neighbor agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and PO. Firstly, we focus on the fundamental case where $k=2$ and there are $r$ red agents and $b$ blue agents. We show that all solution-notions we consider are $\textsf{NP}$-hard to compute even when $b=1$ and that they are $\textsf{W}[1]$-hard when parameterized by $r$ and $b$. In addition, we show that WO and GWO are $\textsf{NP}$-hard even on cubic graphs. We complement these negative results by an $\textsf{FPT}$ algorithm parameterized by $r, b$ and the maximum degree of the graph. For the general case with $k$ types of agents, we prove that for any of the notions we consider the problem is $\textsf{W}[1]$-hard when parameterized by $k$ for a large family of graphs that includes trees. We accompany these negative results with an $\textsf{XP}$ algorithm parameterized by $k$ and the treewidth of the graph.
Scalable In Situ Compression of Transient Simulation Data Using Time-Dependent Bases
Venue: arXiv cs.CE 2022
Year: 2022

Large-scale simulations of time-dependent problems generate a massive amount of data and with the explosive increase in computational resources the size of the data generated by these simulations has increased significantly. This has imposed severe limitations on the amount of data that can be stored and has elevated the issue of input/output (I/O) into one of the major bottlenecks of high-performance computing. In this work, we present an in situ compression technique to reduce the size of the data storage by orders of magnitude. This methodology is based on time-dependent subspaces and it extracts low-rank structures from multidimensional streaming data by decomposing the data into a set of time-dependent bases and a core tensor. We derive closed-form evolution equations for the core tensor as well as the time-dependent bases. The presented methodology does not require the data history and the computational cost of its extractions scales linearly with the size of data -- making it suitable for large-scale streaming datasets. To control the compression error, we present an adaptive strategy to add/remove modes to maintain the reconstruction error below a given threshold. We present four demonstration cases: (i) analytical example, (ii) incompressible unsteady reactive flow, (iii) stochastic turbulent reactive flow, and (iv) three-dimensional turbulent channel flow.
Continual Coarse-to-Fine Domain Adaptation in Semantic Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks are typically trained in a single shot for a specific task and data distribution, but in real world settings both the task and the domain of application can change. The problem becomes even more challenging in dense predictive tasks, such as semantic segmentation, and furthermore most approaches tackle the two problems separately. In this paper we introduce the novel task of coarse-to-fine learning of semantic segmentation architectures in presence of domain shift. We consider subsequent learning stages progressively refining the task at the semantic level; i.e., the finer set of semantic labels at each learning step is hierarchically derived from the coarser set of the previous step. We propose a new approach (CCDA) to tackle this scenario. First, we employ the maximum squares loss to align source and target domains and, at the same time, to balance the gradients between well-classified and harder samples. Second, we introduce a novel coarse-to-fine knowledge distillation constraint to transfer network capabilities acquired on a coarser set of labels to a set of finer labels. Finally, we design a coarse-to-fine weight initialization rule to spread the importance from each coarse class to the respective finer classes. To evaluate our approach, we design two benchmarks where source knowledge is extracted from the GTA5 dataset and it is transferred to either the Cityscapes or the IDD datasets, and we show how it outperforms the main competitors.
Knock Detection in Combustion Engine Time Series Using a Theory-Guided 1D Convolutional Neural Network Approach
Venue: arXiv cs.LG 2022
Year: 2022

This paper introduces a method for the detection of knock occurrences in an internal combustion engine (ICE) using a 1D convolutional neural network trained on in-cylinder pressure data. The model architecture was based on considerations regarding the expected frequency characteristics of knocking combustion. To aid the feature extraction, all cycles were reduced to 60° CA long windows, with no further processing applied to the pressure traces. The neural networks were trained exclusively on in-cylinder pressure traces from multiple conditions and labels provided by human experts. The best-performing model architecture achieves an accuracy of above 92% on all test sets in a tenfold cross-validation when distinguishing between knocking and non-knocking cycles. In a multi-class problem where each cycle was labeled by the number of experts who rated it as knocking, 78% of cycles were labeled perfectly, while 90% of cycles were classified at most one class from ground truth. They thus considerably outperform the broadly applied MAPO (Maximum Amplitude of Pressure Oscillation) detection method, as well as other references reconstructed from previous works. Our analysis indicates that the neural network learned physically meaningful features connected to engine-characteristic resonance frequencies, thus verifying the intended theory-guided data science approach. Deeper performance investigation further shows remarkable generalization ability to unseen operating points. In addition, the model proved to classify knocking cycles in unseen engines with increased accuracy of 89% after adapting to their features via training on a small number of exclusively non-knocking cycles. The algorithm takes below 1 ms (on CPU) to classify individual cycles, effectively making it suitable for real-time engine control.
Supporting Domain Data Selection in Data-Enhanced Process Models
Venue: arXiv cs.DB 2022
Year: 2022

Process mining bridges the gap between process management and data science by discovering process models using event logs derived from real-world data. Besides mandatory event attributes, additional attributes can be part of an event representing domain data, such as human resources and costs. Data-enhanced process models provide a visualization of domain data associated to process activities directly in the process model, allowing to monitor the actual values of domain data in the form of event attribute aggregations. However, event logs can have so many attributes that it is difficult to decide, which one is of interest to observe throughout the process. This paper introduces three mechanisms to support domain data selection, allowing process analysts and domain experts to progressively reach their information of interest. We applied the proposed technique on the MIMIC-IV real-world data set on hospitalizations in the US.
Conflict-aware Inference of Python Compatible Runtime Environments with Domain Knowledge Graph
Venue: arXiv cs.SE 2022
Year: 2022

Code sharing and reuse is a widespread use practice in software engineering. Although a vast amount of open-source Python code is accessible on many online platforms, programmers often find it difficult to restore a successful runtime environment. Previous studies validated automatic inference of Python dependencies using pre-built knowledge bases. However, these studies do not cover sufficient knowledge to accurately match the Python code and also ignore the potential conflicts between their inferred dependencies, thus resulting in a low success rate of inference. In this paper, we propose PyCRE, a new approach to automatically inferring Python compatible runtime environments with domain knowledge graph (KG). Specifically, we design a domain-specific ontology for Python third-party packages and construct KGs for over 10,000 popular packages in Python 2 and Python 3. PyCRE discovers candidate libraries by measuring the matching degree between the known libraries and the third-party resources used in target code. For the NP-complete problem of dependency solving, we propose a heuristic graph traversal algorithm to efficiently guarantee the compatibility between packages. PyCRE achieves superior performance on a real-world dataset and efficiently resolves nearly half more import errors than previous methods.
Fully Connected Reconfigurable Intelligent Surface Aided Rate-Splitting Multiple Access for Multi-User Multi-Antenna Transmission
Venue: arXiv cs.IT 2022
Year: 2022

Rate-splitting multiple access (RSMA) has been recognized as a promising and powerful multiple access (MA) scheme, non-orthogonal transmission framework and interference management strategy for 6G. Inspired by the appealing spectral efficiency gain achieved by RSMA over conventional MA schemes in multi-user multi-antenna transmission, in this paper we introduce RSMA to reconfigurable intelligent surface (RIS)-aided multiple-input single-out (MISO) broadcast channel (BC). To further enhance the spectral efficiency, a more generalized RIS architecture called fully connected RIS is considered. By jointly optimizing the scattering matrix of the fully connected RIS and the transmit beamformers to maximize the sum-rate, we show that the proposed fully connected RIS aided RSMA transmission scheme significantly improves the spectral efficiency compared with the conventional single connected RIS schemes and the schemes without RIS. It acts as a new benchmark for linearly precoded multi-user multi-antenna networks.
System-Agnostic Meta-Learning for MDP-based Dynamic Scheduling via Descriptive Policy
Venue: arXiv cs.LG 2022
Year: 2022

Dynamic scheduling is an important problem in applications from queuing to wireless networks. It addresses how to choose an item among multiple scheduling items in each timestep to achieve a long-term goal. Conventional approaches for dynamic scheduling find the optimal policy for a given specific system so that the policy from these approaches is usable only for the corresponding system characteristics. Hence, it is hard to use such approaches for a practical system in which system characteristics dynamically change. This paper proposes a novel policy structure for MDP-based dynamic scheduling, a descriptive policy, which has a system-agnostic capability to adapt to unseen system characteristics for an identical task (dynamic scheduling). To this end, the descriptive policy learns a system-agnostic scheduling principle--in a nutshell, "which condition of items should have a higher priority in scheduling". The scheduling principle can be applied to any system so that the descriptive policy learned in one system can be used for another system. Experiments with simple explanatory and realistic application scenarios demonstrate that it enables system-agnostic meta-learning with very little performance degradation compared with the system-specific conventional policies.
Forecasting Loss of Signal in Optical Networks with Machine Learning
Venue: arXiv cs.NI 2022
Year: 2022

Loss of Signal (LOS) represents a significant cost for operators of optical networks. By studying large sets of real-world Performance Monitoring (PM) data collected from six international optical networks, we find that it is possible to forecast LOS events with good precision 1-7 days before they occur, albeit at relatively low recall, with supervised machine learning (ML). Our study covers twelve facility types, including 100G lines and ETH10G clients. We show that the precision for a given network improves when training on multiple networks simultaneously relative to training on an individual network. Furthermore, we show that it is possible to forecast LOS from all facility types and all networks with a single model, whereas fine-tuning for a particular facility or network only brings modest improvements. Hence our ML models remain effective for optical networks previously unknown to the model, which makes them usable for commercial applications.
Three Weight Ternary Linear Codes from Non-Weakly Regular Bent Functions
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, several classes of three-weight ternary linear codes from non-weakly regular dual-bent functions are constructed based on a generic construction method. Instead of the whole space, we use the subspaces $B_+(f)$ or $B_-(f)$ associated with a ternary non-weakly regular dual-bent function $f$. Unusually, we use the pre-image sets of the dual function $f^*$ in $B_+(f)$ or $B_-(f)$ as the defining sets of the corresponding codes. Since the size of the defining sets of the constructed codes is flexible, it enables us to construct several codes with different parameters for a fixed dimension. We represent the weight distribution of the constructed codes. We also give several examples.
Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we propose a computationally efficient algorithm for the problem of global optimization in univariate loss functions. For the performance evaluation, we study the cumulative regret of the algorithm instead of the simple regret between our best query and the optimal value of the objective function. Although our approach has similar regret results with the traditional lower-bounding algorithms such as the Piyavskii-Shubert method for the Lipschitz continuous or Lipschitz smooth functions, it has a major computational cost advantage. In Piyavskii-Shubert method, for certain types of functions, the query points may be hard to determine (as they are solutions to additional optimization problems). However, this issue is circumvented in our binary sampling approach, where the sampling set is predetermined irrespective of the function characteristics. For a search space of $[0,1]$, our approach has at most $L\log (3T)$ and $2.25H$ regret for $L$-Lipschitz continuous and $H$-Lipschitz smooth functions respectively. We also analytically extend our results for a broader class of functions that covers more complex regularity conditions.
Dynamic maps for automated driving and UAVs geofencing
Venue: arXiv cs.NI 2022
Year: 2022

The past few years have witnessed a remarkable rise in interest in driver-less cars; and naturally, in parallel, the demand for an accurate and reliable object localization and mapping system is higher than ever. Such a system would have to provide its subscribers with precise information within close range. There have been many previous research works that have explored the different possible approaches to implement such a highly dynamic mapping system in an intelligent transportation system setting, but few have discussed its applicability toward enabling other 5G verticals and services. In this article we start by describing the concept of dynamic maps. We then introduce the approach we took when creating a spatio-temporal dynamic maps system by presenting its architecture and different components. After that, we propose different scenarios where this fairly new and modern technology can be adapted to serve other 5G services, in particular, that of UAV geofencing, and finally, we test the object detection module and discuss the results.
Using Particle Swarm Optimization as Pathfinding Strategy in a Space with Obstacles
Venue: arXiv cs.NE 2022
Year: 2022

Particle swarm optimization (PSO) is a search algorithm based on stochastic and population-based adaptive optimization. In this paper, a pathfinding strategy is proposed to improve the efficiency of path planning for a broad range of applications. This study aims to investigate the effect of PSO parameters (numbers of particle, weight constant, particle constant, and global constant) on algorithm performance to give solution paths. Increasing the PSO parameters makes the swarm move faster to the target point but takes a long time to converge because of too many random movements, and vice versa. From a variety of simulations with different parameters, the PSO algorithm is proven to be able to provide a solution path in a space with obstacles.
Stepwise Migration of a Monolith to a Microservices Architecture: Performance and Migration Effort Evaluation
Venue: arXiv cs.SE 2022
Year: 2022

The agility inherent to today's business promotes the definition of software architectures where the business entities are decoupled into modules and/or services. However, there are advantages in having a rich domain model, where domain entities are tightly connected, because it fosters an initial quick development. On the other hand, the split of the business logic into modules and/or services, its encapsulation through well-defined interfaces and the introduction of inter-service communication introduces a cost in terms of performance. In this paper we analyze the stepwise migrating of a monolith, using a rich domain object, into a microservice architecture, where a modular monolith architecture is used as an intermediate step. The impact on the migration effort and on performance is measured for both steps. Current state of the art analyses the migration of monolith systems to a microservices architecture, but we observed that migration effort and performance issues are already significant in the migration to a modular monolith. Therefore, a clear distinction is established for each one of the steps, which may inform software architects on the planning of the migration of monolith systems. In particular, the trade-offs of doing all the migration process or just migrating to a modular monolith.
Online Generation of Proofs Without Words
Venue: arXiv cs.LO 2022
Year: 2022

Understanding geometric relationships with little mathematical knowledge can be challenging for today's students and teachers. A new toolset is introduced that is able to create a proof without words by combining the benefits of the Geometric Deduction Database method (to obtain a readable proof of a geometric statement) and the GeoGebra framework (that makes it possible to export these data as an online applet in a simple way).
Towards Federated Clustering: A Federated Fuzzy $c$-Means Algorithm (FFCM)
Venue: arXiv cs.LG 2022
Year: 2022

Federated Learning (FL) is a setting where multiple parties with distributed data collaborate in training a joint Machine Learning (ML) model while keeping all data local at the parties. Federated clustering is an area of research within FL that is concerned with grouping together data that is globally similar while keeping all data local. We describe how this area of research can be of interest in itself, or how it helps addressing issues like non-independently-identically-distributed (i.i.d.) data in supervised FL frameworks. The focus of this work, however, is an extension of the federated fuzzy $c$-means algorithm to the FL setting (FFCM) as a contribution towards federated clustering. We propose two methods to calculate global cluster centers and evaluate their behaviour through challenging numerical experiments. We observe that one of the methods is able to identify good global clusters even in challenging scenarios, but also acknowledge that many challenges remain open.
Learning grammar with a divide-and-concur neural network
Venue: arXiv cs.CL 2022
Year: 2022

We implement a divide-and-concur iterative projection approach to context-free grammar inference. Unlike most state-of-the-art models of natural language processing, our method requires a relatively small number of discrete parameters, making the inferred grammar directly interpretable -- one can read off from a solution how to construct grammatically valid sentences. Another advantage of our approach is the ability to infer meaningful grammatical rules from just a few sentences, compared to the hundreds of gigabytes of training data many other models employ. We demonstrate several ways of applying our approach: classifying words and inferring a grammar from scratch, taking an existing grammar and refining its categories and rules, and taking an existing grammar and expanding its lexicon as it encounters new words in new data.
Sandbox Sample Classification Using Behavioral Indicators of Compromise
Venue: arXiv cs.CR 2022
Year: 2022

Behavioral Indicators of Compromise are associated with various automated methods used to extract the sample behavior by observing the system function calls performed in a virtual execution environment. Thus, every sample is described by a set of BICs triggered by the sample behavior in the sandbox environment. Here we discuss a Machine Learning approach to the classification of the sandbox samples as MALICIOUS or BENIGN, based on the list of triggered BICs. Besides the more traditional methods like Logistic Regression and Naive Bayes Classification we also discuss a different approach inspired by the statistical Monte Carlo methods. The numerical results are illustrated using ThreatGRID and ReversingLabs data.
An Optimization Framework for General Rate Splitting for General Multicast
Venue: arXiv cs.IT 2022
Year: 2022

Immersive video, such as virtual reality (VR) and multi-view videos, is growing in popularity. Its wireless streaming is an instance of general multicast, extending conventional unicast and multicast, whose effective design is still open. This paper investigates general rate splitting for general multicast. Specifically, we consider a multi-carrier single-cell wireless network where a multi-antenna base station (BS) communicates to multiple single-antenna users via general multicast. We consider linear beamforming at the BS and joint decoding at each user in the slow fading and fast fading scenarios. In the slow fading scenario, we consider the maximization of the weighted sum average rate, which is a challenging nonconvex stochastic problem with numerous variables. To reduce computational complexity, we decouple the original nonconvex stochastic problem into multiple nonconvex deterministic problems, one for each system channel state. Then, we propose an iterative algorithm for each deterministic problem to obtain a Karush-Kuhn-Tucker (KKT) point using the concave-convex procedure (CCCP). In the fast fading scenario, we consider the maximization of the weighted sum ergodic rate. This problem is more challenging than the one for the slow fading scenario, as it is not separable. First, we propose a stochastic iterative algorithm to obtain a KKT point using stochastic successive convex approximation (SSCA) and the exact penalty method. Then, we propose two low-complexity iterative algorithms to obtain feasible points with promising performance for two cases of channel distributions using approximation and CCCP. The proposed optimization framework generalizes the existing ones for rate splitting for various types of services. Finally, we numerically show substantial gains of the proposed solutions over existing schemes in both scenarios.