OpenRaiser/Intern-Atlas huggingface dataset:
Trustworthy Anomaly Detection: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

Anomaly detection has a wide range of real-world applications, such as bank fraud detection and cyber intrusion detection. In the past decade, a variety of anomaly detection models have been developed, which lead to big progress towards accurately detecting various anomalies. Despite the successes, anomaly detection models still face many limitations. The most significant one is whether we can trust the detection results from the models. In recent years, the research community has spent a great effort to design trustworthy machine learning models, such as developing trustworthy classification models. However, the attention to anomaly detection tasks is far from sufficient. Considering that many anomaly detection tasks are life-changing tasks involving human beings, labeling someone as anomalies or fraudsters should be extremely cautious. Hence, ensuring the anomaly detection models conducted in a trustworthy fashion is an essential requirement to deploy the models to conduct automatic decisions in the real world. In this brief survey, we summarize the existing efforts and discuss open problems towards trustworthy anomaly detection from the perspectives of interpretability, fairness, robustness, and privacy-preservation.
Code Generation for Unknown Libraries via Reading API Documentations
Venue: arXiv cs.CL 2022
Year: 2022

Open-domain code generation is a challenging problem because the set of functions and classes that we use are frequently changed and extended in programming communities. We consider the challenge of code generation for unknown libraries without additional training. In this paper, we explore a framework of code generation that can refer to relevant API documentations like human programmers to handle unknown libraries. As a first step of this direction, we implement a model that can extract relevant code signatures from API documentations based on a natural language intent and copy primitives from the extracted signatures. Moreover, to evaluate code generation for unknown libraries and our framework, we extend an existing dataset of open-domain code generation and resplit it so that the evaluation data consist of only examples using the libraries that do not appear in the training data. Experiments on our new split show that baseline encoder-decoder models cannot generate code using primitives of unknown libraries as expected. In contrast, our model outperforms the baseline on the new split and can properly generate unknown primitives when extracted code signatures are noiseless.
RNGDet: Road Network Graph Detection by Transformer in Aerial Images
Venue: arXiv cs.CV 2022
Year: 2022

Road network graphs provide critical information for autonomous-vehicle applications, such as drivable areas that can be used for motion planning algorithms. To find road network graphs, manually annotation is usually inefficient and labor-intensive. Automatically detecting road network graphs could alleviate this issue, but existing works still have some limitations. For example, segmentation-based approaches could not ensure satisfactory topology correctness, and graph-based approaches could not present precise enough detection results. To provide a solution to these problems, we propose a novel approach based on transformer and imitation learning in this paper. In view of that high-resolution aerial images could be easily accessed all over the world nowadays, we make use of aerial images in our approach. Taken as input an aerial image, our approach iteratively generates road network graphs vertex-by-vertex. Our approach can handle complicated intersection points with various numbers of incident road segments. We evaluate our approach on a publicly available dataset. The superiority of our approach is demonstrated through the comparative experiments. Our work is accompanied with a demonstration video which is available at \url{https://tonyxuqaq.github.io/projects/RNGDet/}.
CycleGAN for Undamaged-to-Damaged Domain Translation for Structural Health Monitoring and Damage Detection
Venue: arXiv cs.LG 2022
Year: 2022

The recent advances in the data science field in the last few decades have benefitted many other fields including Structural Health Monitoring (SHM). Particularly, Artificial Intelligence (AI) such as Machine Learning (ML) and Deep Learning (DL) methods for vibration-based damage diagnostics of civil structures has been utilized extensively due to the observed high performances in learning from data. Along with diagnostics, damage prognostics is also vitally important for estimating the remaining useful life of civil structures. Currently, AI-based data-driven methods used for damage diagnostics and prognostics centered on historical data of the structures and require a substantial amount of data for prediction models. Although some of these methods are generative-based models, they are used to perform ML or DL tasks such as classification, regression, clustering, etc. after learning the distribution of the data. In this study, a variant of Generative Adversarial Networks (GAN), Cycle-Consistent Wasserstein Deep Convolutional GAN with Gradient Penalty (CycleWDCGAN-GP) model is developed to investigate the "transition of structural dynamic signature from an undamaged-to-damaged state" and "if this transition can be employed for predictive damage detection". The outcomes of this study demonstrate that the proposed model can accurately generate damaged responses from undamaged responses or vice versa. In other words, it will be possible to understand the damaged condition while the structure is still in a healthy (undamaged) condition or vice versa with the proposed methodology. This will enable a more proactive approach in overseeing the life-cycle performance as well as in predicting the remaining useful life of structures.
DBT-Net: Dual-branch federative magnitude and phase estimation with attention-in-attention transformer for monaural speech enhancement
Venue: arXiv cs.SD 2022
Year: 2022

The decoupling-style concept begins to ignite in the speech enhancement area, which decouples the original complex spectrum estimation task into multiple easier sub-tasks i.e., magnitude-only recovery and the residual complex spectrum estimation)}, resulting in better performance and easier interpretability. In this paper, we propose a dual-branch federative magnitude and phase estimation framework, dubbed DBT-Net, for monaural speech enhancement, aiming at recovering the coarse- and fine-grained regions of the overall spectrum in parallel. From the complementary perspective, the magnitude estimation branch is designed to filter out dominant noise components in the magnitude domain, while the complex spectrum purification branch is elaborately designed to inpaint the missing spectral details and implicitly estimate the phase information in the complex-valued spectral domain. To facilitate the information flow between each branch, interaction modules are introduced to leverage features learned from one branch, so as to suppress the undesired parts and recover the missing components of the other branch. Instead of adopting the conventional RNNs and temporal convolutional networks for sequence modeling, we employ a novel attention-in-attention transformer-based network within each branch for better feature learning. More specially, it is composed of several adaptive spectro-temporal attention transformer-based modules and an adaptive hierarchical attention module, aiming to capture long-term time-frequency dependencies and further aggregate intermediate hierarchical contextual information. Comprehensive evaluations on the WSJ0-SI84 + DNS-Challenge and VoiceBank + DEMAND dataset demonstrate that the proposed approach consistently outperforms previous advanced systems and yields state-of-the-art performance in terms of speech quality and intelligibility.
On the Complexity of Scheduling Problems With a Fixed Number of Parallel Identical Machines
Venue: arXiv cs.DS 2022
Year: 2022

In parallel machine scheduling, we are given a set of jobs, together with a number of machines and our goal is to decide for each job, when and on which machine(s) it should be scheduled in order to minimize some objective function. Different machine models, job characteristics and objective functions result in a multitude of scheduling problems and many of them are NP-hard, even for a fixed number of identical machines. In this work, we give conditional running time lower bounds for a large number of scheduling problems, indicating the optimality of some classical algorithms. Most notably, we show that the algorithm by Lawler and Moore for $1||\sum w_jU_j$ and $Pm||C_{max}$, as well as the algorithm by Lee and Uzsoy for $P2||\sum w_jC_j$ are probably optimal. There is still small room for improvement for the $1|Rej\leq Q|\sum w_jU_j$ algorithm by Zhang et al., the algorithm for $1||\sum T_j$ by Lawler and the FPTAS for $1||\sum w_jU_j$ by Gens and Levner. We also give a lower bound for $P2|any|C_{max}$ and improve the dynamic program by Du and Leung from $\mathcal{O}(nP^2)$ to $\mathcal{O}(nP)$, matching this new lower bound. Here, $P$ is the sum of all processing times. The same idea also improves the algorithm for $P3|any|C_{max}$ by Du and Leung from $\mathcal{O}(nP^5)$ to $\mathcal{O}(nP^2)$. While our results suggest the optimality of some classical algorithms, they also motivate future research in cases where the best known algorithms do not quite match the lower bounds.
Guessing with Little Data
Venue: arXiv cs.SC 2022
Year: 2022

Reconstructing a hypothetical recurrence equation from the first terms of an infinite sequence is a classical and well-known technique in experimental mathematics. We propose a variation of this technique which can succeed with fewer input terms.
Out-Of-Distribution Generalization on Graphs: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

Graph machine learning has been extensively studied in both academia and industry. Although booming with a vast number of emerging methods and techniques, most of the literature is built on the in-distribution hypothesis, i.e., testing and training graph data are identically distributed. However, this in-distribution hypothesis can hardly be satisfied in many real-world graph scenarios where the model performance substantially degrades when there exist distribution shifts between testing and training graph data. To solve this critical problem, out-of-distribution (OOD) generalization on graphs, which goes beyond the in-distribution hypothesis, has made great progress and attracted ever-increasing attention from the research community. In this paper, we comprehensively survey OOD generalization on graphs and present a detailed review of recent advances in this area. First, we provide a formal problem definition of OOD generalization on graphs. Second, we categorize existing methods into three classes from conceptually different perspectives, i.e., data, model, and learning strategy, based on their positions in the graph machine learning pipeline, followed by detailed discussions for each category. We also review the theories related to OOD generalization on graphs and introduce the commonly used graph datasets for thorough evaluations. Finally, we share our insights on future research directions. This paper is the first systematic and comprehensive review of OOD generalization on graphs, to the best of our knowledge.
Branching Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we propose a novel Branching Reinforcement Learning (Branching RL) model, and investigate both Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. Unlike standard RL where the trajectory of each episode is a single $H$-step path, branching RL allows an agent to take multiple base actions in a state such that transitions branch out to multiple successor states correspondingly, and thus it generates a tree-structured trajectory. This model finds important applications in hierarchical recommendation systems and online advertising. For branching RL, we establish new Bellman equations and key lemmas, i.e., branching value difference lemma and branching law of total variance, and also bound the total variance by only $O(H^2)$ under an exponentially-large trajectory. For RM and RFE metrics, we propose computationally efficient algorithms BranchVI and BranchRFE, respectively, and derive nearly matching upper and lower bounds. Our results are only polynomial in problem parameters despite exponentially-large trajectories.
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget
Venue: arXiv cs.DM 2022
Year: 2022

In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals is allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains $k$-colorable at all times, and the updates consist of insertions only, then we can achieve the amortized recourse budget of $O(k^7 \log n)$ while maintaining a proper coloring with $k$ colors. This is an exponential improvement over the result in [Bosek et al., Recoloring Interval Graphs with Limited Recourse Budget. SWAT 2020] in terms of both $k$ and $n$. We complement this result by showing the lower bound of $Ω(n)$ on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As a byproduct of independent interest we include a new result on coloring proper circular arc graphs. Let $L$ be the maximum number of arcs intersecting in one point for some set of unit circular arcs $\mathcal{A}$. We show that if there is a set $\mathcal{A}'$ of non-intersecting unit arcs of size $L^2-1$ such that $\mathcal{A} \cup \mathcal{A}'$ does not contain $L+1$ arcs intersecting in one point, then it is possible to color $\mathcal{A}$ with $L$ colors. This complements the work on unit circular arc coloring, which specifies sufficient conditions needed to color $\mathcal{A}$ with $L+1$ colors or more.
Simulation-based Verification of SystemC-based VPs at the ESL
Venue: arXiv cs.AR 2022
Year: 2022

SystemC-based Virtual Prototypes (VPs) at the Electronic System Level (ESL) are increasingly adopted by the semiconductor industry. The main reason is that VPs are much earlier available, and their simulation is orders of magnitude faster in comparison to the hardware models at lower levels of abstraction (e.g. RTL). This leads designers to use VPs as reference models for early design verification. Hence, the correctness of VPs is of utmost importance as undetected errors may propagate to less abstract levels in the design process, increasing the fixing cost and effort. In this paper, we introduce a comprehensive simulation-based verification approach to automatically validate the simulation behavior of a given SystemC-based VP against both the TLM-2.0 rules and its specifications, i.e. functional and timing behavior of communications in the VP.
Optimizing over Serial Dictatorships
Venue: arXiv cs.GT 2022
Year: 2022

Motivated by the success of the serial dictatorship mechanism in social choice settings, we explore its usefulness in tackling various combinatorial optimization problems. We do so by considering an abstract model, in which a set of agents are asked to act in a particular ordering, called the action sequence. Each agent acts in a way that gives her the maximum possible value, given the actions of the agents who preceded her in the action sequence. Our goal is to compute action sequences that yield approximately optimal total value to the agents (a.k.a., social welfare). We assume query access to the value $v_i(S)$ that the agent i gets when she acts after the agents in the ordered set $S$. We establish tight bounds on the social welfare that can be achieved using polynomially many queries. Even though these bounds show a marginally sublinear approximation of optimal social welfare in general, excellent approximations can be obtained when the valuations stem from an underlying combinatorial domain. Indicatively, when the valuations are defined using bipartite matchings, arborescences in directed graphs, and satisfiability of Boolean expressions, simple query-efficient algorithms yield $2$-approximations. We discuss issues related to truthfulness and show how some of our algorithms can be implemented truthfully using VCG-like payments. Finally, we introduce and study the price of serial dictatorship, a notion that provides an optimistic measure of the quality of combinatorial optimization solutions generated by action sequences.
Reversible data hiding with dual pixel-value-ordering and1minimum prediction error expansion
Venue: arXiv cs.CV 2022
Year: 2022

Pixel Value Ordering (PVO) holds an impressive property for high fidelity Reversible Data Hiding (RDH). In this paper, we introduce a dual-PVO (dPVO) for Prediction Error Expansion(PEE), and thereby develop a new RDH scheme to offer a better rate-distortion performance. Particularly, we propose to embed in two phases: forward and backward. In the forward phase, PVO with classic PEE is applied to every non-overlapping image block of size 1x3. In the backward phase,minimum-set and maximum-set of pixels are determined from the pixels predicted in the forward phase. The minimum set only contains the lowest predicted pixels and the maximum set contains the largest predicted pixels of each image block. Proposed dPVO withPEE is then applied to both sets, so that the pixel values of the minimum set are increased and that of the maximum set are decreased by a unit value. Thereby, the pixels predicted in the forward embedding can partially be restored to their original values resulting in both better-embedded image quality and a higher embedding rate. Experimental results have recorded a promising rate-distortion performance of our scheme with a significant improvement of embedded image quality at higher embedding rates compared to the popular and state-of-the-art PVO-based RDHschemes.
A note on hospital financing: local financing vs. central financing
Venue: arXiv cs.GT 2022
Year: 2022

This note tries to study how hospital behaviors, with reference to interhospital collaboration or competition, could be affected by hospital financing systems. For that this note simulates two scenarios which start with the following baseline scenario: a State, with a set of hospitals, each with all types of wards at a basic level. The evolution of this baseline scenario consists in the evolution of hospitals, that is, in the possibility of hospitals to make some of their wards excel. The State has a budget, for the evolution of this baseline scenario, which can be used by two financing systems: either by a "local financing", i.e., by splitting the budget among the hospitals so that each hospital is managing its own portion of the budget by pursuing the individual benefit, or by a "central financing", i.e., by not splitting the budget among the hospitals so that the State is the sole manager of the budget, by pursuing the benefit of the whole community. The conclusions seem to be that: in the local financing system hospitals tend to diversify their excellences, while in the central financing system the State tends to create poles of excellence.
FUN-SIS: a Fully UNsupervised approach for Surgical Instrument Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Automatic surgical instrument segmentation of endoscopic images is a crucial building block of many computer-assistance applications for minimally invasive surgery. So far, state-of-the-art approaches completely rely on the availability of a ground-truth supervision signal, obtained via manual annotation, thus expensive to collect at large scale. In this paper, we present FUN-SIS, a Fully-UNsupervised approach for binary Surgical Instrument Segmentation. FUN-SIS trains a per-frame segmentation model on completely unlabelled endoscopic videos, by solely relying on implicit motion information and instrument shape-priors. We define shape-priors as realistic segmentation masks of the instruments, not necessarily coming from the same dataset/domain as the videos. The shape-priors can be collected in various and convenient ways, such as recycling existing annotations from other datasets. We leverage them as part of a novel generative-adversarial approach, allowing to perform unsupervised instrument segmentation of optical-flow images during training. We then use the obtained instrument masks as pseudo-labels in order to train a per-frame segmentation model; to this aim, we develop a learning-from-noisy-labels architecture, designed to extract a clean supervision signal from these pseudo-labels, leveraging their peculiar noise properties. We validate the proposed contributions on three surgical datasets, including the MICCAI 2017 EndoVis Robotic Instrument Segmentation Challenge dataset. The obtained fully-unsupervised results for surgical instrument segmentation are almost on par with the ones of fully-supervised state-of-the-art approaches. This suggests the tremendous potential of the proposed method to leverage the great amount of unlabelled data produced in the context of minimally invasive surgery.
A novel public key cryptography based on generalized Lucas matrices
Venue: arXiv cs.CR 2022
Year: 2022

In this article, we have proposed a generalized Lucas matrix (recursive matrix of higher order) having relation with generalized Fibonacci sequences and established many special properties in addition to that usual matrix algebra. Further, we have proposed a modified public key cryptography using these matrices as keys in Affine cipher and key agreement for encryption-decryption with the combination of terms of generalized Lucas sequences under residue operations. In this scheme, instead of exchanging the whole key matrix, only a pair of numbers(parameters) need to be exchanged, which reduces the time complexity as well as space complexity of the key transmission and has a large key-space.
Evaluation and Analysis of Different Aggregation and Hyperparameter Selection Methods for Federated Brain Tumor Segmentation
Venue: arXiv cs.LG 2022
Year: 2022

Availability of large, diverse, and multi-national datasets is crucial for the development of effective and clinically applicable AI systems in the medical imaging domain. However, forming a global model by bringing these datasets together at a central location, comes along with various data privacy and ownership problems. To alleviate these problems, several recent studies focus on the federated learning paradigm, a distributed learning approach for decentralized data. Federated learning leverages all the available data without any need for sharing collaborators' data with each other or collecting them on a central server. Studies show that federated learning can provide competitive performance with conventional central training, while having a good generalization capability. In this work, we have investigated several federated learning approaches on the brain tumor segmentation problem. We explore different strategies for faster convergence and better performance which can also work on strong Non-IID cases.