OpenRaiser/Intern-Atlas huggingface dataset:
Greedy Algorithms for Decision Trees with Hypotheses
Venue: arXiv cs.CC 2022
Year: 2022

We investigate at decision trees that incorporate both traditional queries based on one attribute and queries based on hypotheses about the values of all attributes. Such decision trees are similar to ones studied in exact learning, where membership and equivalence queries are allowed. We present greedy algorithms based on diverse uncertainty measures for construction of above decision trees and discuss results of computer experiments on various data sets from the UCI ML Repository and randomly generated Boolean functions. We also study the length and coverage of decision rules derived from the decisiontrees constructed by greedy algorithms.
Planar Rosa : a family of quasiperiodic substitution discrete plane tilings with $2n$-fold rotational symmetry
Venue: arXiv cs.DM 2022
Year: 2022

We present Planar Rosa, a family of rhombus tilings with a $2n$-fold rotational symmetry that are generated by a primitive substitution and that are also discrete plane tilings, meaning that they are obtained as a projection of a higher dimensional discrete plane. The discrete plane condition is a relaxed version of the cut-and-project condition. We also prove that the Sub Rosa substitution tilings with $2n$-fold rotational symmetry defined by Kari and Rissanen do not satisfy even the weaker discrete plane condition. We prove these results for all even $n\geq 4$. This completes our previously published results for odd values of $n$.
Towards an HPC Complementary Computing Facility
Venue: arXiv cs.DC 2022
Year: 2022

This Letter considers the design for computing facilities that are complementary to the leadership class High Performance Computing (HPC) facilities. This design envisions a future where funding agencies are allocating greater resources for leadership class facilities and these facilities will provide a significant part of the total compute cycles for HEP Experiments. While a leadership class facility (LCF) may provide cycles and advanced architectures, the facility does not necessarily provide all of the services needed to help HEP users make the best use of the HPC facility, as well as the services needed to provide computing for workflows that are not a good fit for the HPC facilities. This Letter outlines some of the necessary components of a facility designed to provide those services and capabilities.
Encrypted Operator Computing: a novel scheme for computation on encrypted data
Venue: arXiv cs.CR 2022
Year: 2022

We introduce a new approach to computation on encrypted data -- Encrypted Operator Computing (EOC) -- as an alternative to Fully Homomorphic Encryption (FHE). Given a plaintext vector $|{x}\rangle$, $x\in \{0,1\}^n$, and a function $F(x)$ represented as an operator $\hat F$, $\hat F\;|{x}\rangle = |{F(x)}\rangle$, the EOC scheme is based on obfuscating the conjugated operator (circuit) $\hat{F}^E = \hat E\;\hat F\;\hat{E}^{-1}$ that implements computation on encrypted data, $\hat E |{x}\rangle$. The construction of EOC hinges on the existence of a two-stage NC$^1$ reversible-circuit-based IND-CCA2 cipher $\hat{E} = \hat{N} \hat{L}$, where $\hat{L}$ and $\hat{N}$ represent, respectively, linear and non-linear NC$^1$ tree-structured circuits of 3-bit reversible gates. We make and motivate security assumptions about such a NC$^1$ cipher. Furthermore, we establish the polynomial complexity of the obfuscated circuit, the evaluator $O(\hat{F}^E)$, by proving that: (a) conjugation of each gate of $F$ with $\hat{L}$ yields a polynomial number of gates; and (b) the subsequent conjugation with $\hat{N}$ yields a polynomial number of ``chips,'' $n$-input/$n$-output reversible functions, with outputs expressed as polynomial-sized ordered Binary Decision Diagrams (OBDDs). The security of individual chips is connected to the notion of Best Possible Obfuscators which relies on poly-size OBDDs and the fact that OBDDs are normal forms that expose the functionality but hide the gate implementation of the chip. We conjecture that the addition of random pairs of NOTs between layers of $\hat{N}$ during the construction of $F^E$, a device analogous to the AddRoundKey rounds of AES, ensures the security of the the evaluator. We also present a generalization to asymmetric encryption.
Multimodal Learning on Graphs for Disease Relation Extraction
Venue: arXiv cs.LG 2022
Year: 2022

Objective: Disease knowledge graphs are a way to connect, organize, and access disparate information about diseases with numerous benefits for artificial intelligence (AI). To create knowledge graphs, it is necessary to extract knowledge from multimodal datasets in the form of relationships between disease concepts and normalize both concepts and relationship types. Methods: We introduce REMAP, a multimodal approach for disease relation extraction and classification. The REMAP machine learning approach jointly embeds a partial, incomplete knowledge graph and a medical language dataset into a compact latent vector space, followed by aligning the multimodal embeddings for optimal disease relation extraction. Results: We apply REMAP approach to a disease knowledge graph with 96,913 relations and a text dataset of 1.24 million sentences. On a dataset annotated by human experts, REMAP improves text-based disease relation extraction by 10.0% (accuracy) and 17.2% (F1-score) by fusing disease knowledge graphs with text information. Further, REMAP leverages text information to recommend new relationships in the knowledge graph, outperforming graph-based methods by 8.4% (accuracy) and 10.4% (F1-score). Conclusion: REMAP is a multimodal approach for extracting and classifying disease relationships by fusing structured knowledge and text information. REMAP provides a flexible neural architecture to easily find, access, and validate AI-driven relationships between disease concepts.
Sound Development of Safety Supervisors
Venue: arXiv cs.SE 2022
Year: 2022

Safety supervisors are controllers enforcing safety properties by keeping a system in (or returning it to) a safe state. The development of such high-integrity components can benefit from a rigorous workflow integrating formal design and verification. In this paper, we present a workflow for the sound development of safety supervisors combining the best of two worlds, verified synthesis and complete testing. Synthesis allows one to focus on problem specification and model validation. Testing compensates for the crossing of abstraction, formalism, and tool boundaries and is a key element to obtain certification credit before entry into service. We establish soundness of our workflow through a rigorous argument. Our approach is tool-supported, aims at modern autonomous systems, and is illustrated with a collaborative robotics example.
Understanding Privacy Switching Behaviour on Twitter
Venue: arXiv cs.HC 2022
Year: 2022

Changing a Twitter account's privacy setting between public and protected changes the visibility of past tweets. By inspecting the privacy setting of over 100K Twitter users over 3 months, we noticed that over 40% of those users change their privacy setting at least once with around 16% changing it over 5 times. This motivated us to explore the reasons why people switch their privacy setting. We studied these switching phenomena quantitatively by comparing the tweeting behaviour of users when public vs protected, and qualitatively using two follow-up surveys (n=100, n=324) to understand potential reasoning behind the observed behaviours. Our quantitative analysis shows that users who switch privacy settings mention others and share hashtags more when their setting is public. Our surveys highlighted that users turn protected to share personal content and regulate boundaries while they turn public to interact with others in ways prevented by being protected.
Backpropagation through Time and Space: Learning Numerical Methods with Multi-Agent Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

We introduce Backpropagation Through Time and Space (BPTTS), a method for training a recurrent spatio-temporal neural network, that is used in a homogeneous multi-agent reinforcement learning (MARL) setting to learn numerical methods for hyperbolic conservation laws. We treat the numerical schemes underlying partial differential equations (PDEs) as a Partially Observable Markov Game (POMG) in Reinforcement Learning (RL). Similar to numerical solvers, our agent acts at each discrete location of a computational space for efficient and generalizable learning. To learn higher-order spatial methods by acting on local states, the agent must discern how its actions at a given spatiotemporal location affect the future evolution of the state. The manifestation of this non-stationarity is addressed by BPTTS, which allows for the flow of gradients across both space and time. The learned numerical policies are comparable to the SOTA numerics in two settings, the Burgers' Equation and the Euler Equations, and generalize well to other simulation set-ups.
Robustness through Cognitive Dissociation Mitigation in Contrastive Adversarial Training
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we introduce a novel neural network training framework that increases model's adversarial robustness to adversarial attacks while maintaining high clean accuracy by combining contrastive learning (CL) with adversarial training (AT). We propose to improve model robustness to adversarial attacks by learning feature representations that are consistent under both data augmentations and adversarial perturbations. We leverage contrastive learning to improve adversarial robustness by considering an adversarial example as another positive example, and aim to maximize the similarity between random augmentations of data samples and their adversarial example, while constantly updating the classification head in order to avoid a cognitive dissociation between the classification head and the embedding space. This dissociation is caused by the fact that CL updates the network up to the embedding space, while freezing the classification head which is used to generate new positive adversarial examples. We validate our method, Contrastive Learning with Adversarial Features(CLAF), on the CIFAR-10 dataset on which it outperforms both robust accuracy and clean accuracy over alternative supervised and self-supervised adversarial learning methods.
Kan Extensions in Data Science and Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

A common problem in data science is "use this function defined over this small set to generate predictions over that larger set." Extrapolation, interpolation, statistical inference and forecasting all reduce to this problem. The Kan extension is a powerful tool in category theory that generalizes this notion. In this work we explore several applications of Kan extensions to data science. We begin by deriving a simple classification algorithm as a Kan extension and experimenting with this algorithm on real data. Next, we use the Kan extension to derive a procedure for learning clustering algorithms from labels and explore the performance of this procedure on real data. We then investigate how Kan extensions can be used to learn a general mapping from datasets of labeled examples to functions and to approximate a complex function with a simpler one.
Graph Augmentation Learning
Venue: arXiv cs.LG 2022
Year: 2022

Graph Augmentation Learning (GAL) provides outstanding solutions for graph learning in handling incomplete data, noise data, etc. Numerous GAL methods have been proposed for graph-based applications such as social network analysis and traffic flow forecasting. However, the underlying reasons for the effectiveness of these GAL methods are still unclear. As a consequence, how to choose optimal graph augmentation strategy for a certain application scenario is still in black box. There is a lack of systematic, comprehensive, and experimentally validated guideline of GAL for scholars. Therefore, in this survey, we in-depth review GAL techniques from macro (graph), meso (subgraph), and micro (node/edge) levels. We further detailedly illustrate how GAL enhance the data quality and the model performance. The aggregation mechanism of augmentation strategies and graph learning models are also discussed by different application scenarios, i.e., data-specific, model-specific, and hybrid scenarios. To better show the outperformance of GAL, we experimentally validate the effectiveness and adaptability of different GAL strategies in different downstream tasks. Finally, we share our insights on several open issues of GAL, including heterogeneity, spatio-temporal dynamics, scalability, and generalization.
A Survey of Multi-Tenant Deep Learning Inference on GPU
Venue: arXiv cs.DC 2022
Year: 2022

Deep Learning (DL) models have achieved superior performance. Meanwhile, computing hardware like NVIDIA GPUs also demonstrated strong computing scaling trends with 2x throughput and memory bandwidth for each generation. With such strong computing scaling of GPUs, multi-tenant deep learning inference by co-locating multiple DL models onto the same GPU becomes widely deployed to improve resource utilization, enhance serving throughput, reduce energy cost, etc. However, achieving efficient multi-tenant DL inference is challenging which requires thorough full-stack system optimization. This survey aims to summarize and categorize the emerging challenges and optimization opportunities for multi-tenant DL inference on GPU. By overviewing the entire optimization stack, summarizing the multi-tenant computing innovations, and elaborating the recent technological advances, we hope that this survey could shed light on new optimization perspectives and motivate novel works in future large-scale DL system optimization.
Fine- and Coarse-Granularity Hybrid Self-Attention for Efficient BERT
Venue: arXiv cs.CL 2022
Year: 2022

Transformer-based pre-trained models, such as BERT, have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. However, deploying these models can be prohibitively costly, as the standard self-attention mechanism of the Transformer suffers from quadratic computational cost in the input sequence length. To confront this, we propose FCA, a fine- and coarse-granularity hybrid self-attention that reduces the computation cost through progressively shortening the computational sequence length in self-attention. Specifically, FCA conducts an attention-based scoring strategy to determine the informativeness of tokens at each layer. Then, the informative tokens serve as the fine-granularity computing units in self-attention and the uninformative tokens are replaced with one or several clusters as the coarse-granularity computing units in self-attention. Experiments on GLUE and RACE datasets show that BERT with FCA achieves 2x reduction in FLOPs over original BERT with <1% loss in accuracy. We show that FCA offers a significantly better trade-off between accuracy and FLOPs compared to prior methods.
Parameterized and Exact Algorithms for Class Domination Coloring
Venue: arXiv cs.DM 2022
Year: 2022

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighbourhood of some vertex. The minimum number of colors required for any cd-coloring of $G$, denoted by $χ_{cd}(G)$, is called the class domination chromatic number (cd-chromatic number) of $G$. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph $G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and integers $k$ and $q$, can we delete at most $k$ vertices such that the cd-chromatic number of the resulting graph is at most $q$? For the first problem, we give an exact algorithm with running time $\Oh(2^n n^4 \log n)$. Also, we show that the problem is \FPT\ with respect to the number $q$ of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with $\Oh(q^3)$ vertices. For the second (deletion) problem, we show \NP-hardness for each $q \geq 2$. Further, on split graphs, we show that the problem is \NP-hard if $q$ is a part of the input and \FPT\ with respect to $k$ and $q$ as combined parameters. As recognizing graphs with cd-chromatic number at most $q$ is \NP-hard in general for $q \geq 4$, the deletion problem is unlikely to be \FPT\ when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for $q \in \{2,3\}$ using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.
Time Dependency, Data Flow, and Competitive Advantage
Venue: arXiv cs.LG 2022
Year: 2022

Data is fundamental to machine learning-based products and services and is considered strategic due to its externalities for businesses, governments, non-profits, and more generally for society. It is renowned that the value of organizations (businesses, government agencies and programs, and even industries) scales with the volume of available data. What is often less appreciated is that the data value in making useful organizational predictions will range widely and is prominently a function of data characteristics and underlying algorithms. In this research, our goal is to study how the value of data changes over time and how this change varies across contexts and business areas (e.g. next word prediction in the context of history, sports, politics). We focus on data from Reddit.com and compare the value's time-dependency across various Reddit topics (Subreddits). We make this comparison by measuring the rate at which user-generated text data loses its relevance to the algorithmic prediction of conversations. We show that different subreddits have different rates of relevance decline over time. Relating the text topics to various business areas of interest, we argue that competing in a business area in which data value decays rapidly alters strategies to acquire competitive advantage. When data value decays rapidly, access to a continuous flow of data will be more valuable than access to a fixed stock of data. In this kind of setting, improving user engagement and increasing user-base help creating and maintaining a competitive advantage.
Graph Representation Learning with Individualization and Refinement
Venue: arXiv cs.LG 2022
Year: 2022

Graph Neural Networks (GNNs) have emerged as prominent models for representation learning on graph structured data. GNNs follow an approach of message passing analogous to 1-dimensional Weisfeiler Lehman (1-WL) test for graph isomorphism and consequently are limited by the distinguishing power of 1-WL. More expressive higher-order GNNs which operate on k-tuples of nodes need increased computational resources in order to process higher-order tensors. Instead of the WL approach, in this work, we follow the classical approach of Individualization and Refinement (IR), a technique followed by most practical isomorphism solvers. Individualization refers to artificially distinguishing a node in the graph and refinement is the propagation of this information to other nodes through message passing. We learn to adaptively select nodes to individualize and to aggregate the resulting graphs after refinement to help handle the complexity. Our technique lets us learn richer node embeddings while keeping the computational complexity manageable. Theoretically, we show that our procedure is more expressive than the 1-WL test. Experiments show that our method outperforms prominent 1-WL GNN models as well as competitive higher-order baselines on several benchmark synthetic and real datasets. Furthermore, our method opens new doors for exploring the paradigm of learning on graph structures with individualization and refinement.
Unsigned Distance Field as an Accurate 3D Scene Representation for Neural Scene Completion
Venue: arXiv cs.CV 2022
Year: 2022

Scene Completion is the task of completing missing geometry from a partial scan of a scene. Most previous methods compute an implicit representation from range data using a Truncated Signed Distance Function (T-SDF) computed on a 3D grid as input to neural networks. The truncation decreases but does not remove the border errors introduced by the sign of SDF for open surfaces. As an alternative, we present an Unsigned Distance Function (UDF) as an input representation to scene completion neural networks. The proposed UDF is simple, and efficient as a geometry representation, and can be computed on any point cloud. In contrast to usual Signed Distance Functions, our UDF does not require normal computation. To obtain the explicit geometry, we present a method for extracting a point cloud from discretized UDF values on a sparse grid. We compare different SDFs and UDFs for the scene completion task on indoor and outdoor point clouds collected using RGB-D and LiDAR sensors and show improved completion using the proposed UDF function.
Speaker recognition using residual signal of linear and nonlinear prediction models
Venue: arXiv cs.SD 2022
Year: 2022

This Paper discusses the usefulness of the residual signal for speaker recognition. It is shown that the combination of both a measure defined over LPCC coefficients and a measure defined over the energy of the residual signal gives rise to an improvement over the classical method which considers only the LPCC coefficients. If the residual signal is obtained from a linear prediction analysis, the improvement is 2.63% (error rate drops from 6.31% to 3.68%) and if it is computed through a nonlinear predictive neural nets based model, the improvement is 3.68%.
Depth-aware Neural Style Transfer using Instance Normalization
Venue: arXiv cs.CV 2022
Year: 2022

Neural Style Transfer (NST) is concerned with the artistic stylization of visual media. It can be described as the process of transferring the style of an artistic image onto an ordinary photograph. Recently, a number of studies have considered the enhancement of the depth-preserving capabilities of the NST algorithms to address the undesired effects that occur when the input content images include numerous objects at various depths. Our approach uses a deep residual convolutional network with instance normalization layers that utilizes an advanced depth prediction network to integrate depth preservation as an additional loss function to content and style. We demonstrate results that are effective in retaining the depth and global structure of content images. Three different evaluation processes show that our system is capable of preserving the structure of the stylized results while exhibiting style-capture capabilities and aesthetic qualities comparable or superior to state-of-the-art methods. Project page: https://ioannoue.github.io/depth-aware-nst-using-in.html.