OpenRaiser/Intern-Atlas huggingface dataset:
Explicit Lower Bounds Against $Ω(n)$-Rounds of Sum-of-Squares
Venue: arXiv cs.CC 2022
Year: 2022

We construct an explicit family of 3-XOR instances hard for $Ω(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness of random instances up to imperfect completeness (Grigoriev TCS 2001, Schoenebeck FOCS 2008). Our result is based on a new form of small-set high dimensional expansion (SS-HDX) inspired by recent breakthroughs in locally testable and quantum LDPC codes. Adapting the recent framework of Dinur, Filmus, Harsha, and Tulsiani (ITCS 2021) for SoS lower bounds from the Ramanujan complex to this setting, we show any (bounded-degree) SS-HDX can be transformed into a highly unsatisfiable 3-XOR instance that cannot be refuted by $Ω(n)$-levels of SoS. We then show Leverrier and Zémor's (Arxiv 2022) recent qLDPC construction gives the desired explicit family of bounded-degree SS-HDX. Incidentally, this gives the strongest known form of bi-directional high dimensional expansion to date.
End-to-End Audio Strikes Back: Boosting Augmentations Towards An Efficient Audio Classification Network
Venue: arXiv cs.SD 2022
Year: 2022

While efficient architectures and a plethora of augmentations for end-to-end image classification tasks have been suggested and heavily investigated, state-of-the-art techniques for audio classifications still rely on numerous representations of the audio signal together with large architectures, fine-tuned from large datasets. By utilizing the inherited lightweight nature of audio and novel audio augmentations, we were able to present an efficient end-to-end network with strong generalization ability. Experiments on a variety of sound classification sets demonstrate the effectiveness and robustness of our approach, by achieving state-of-the-art results in various settings. Public code is available at: \href{https://github.com/Alibaba-MIIL/AudioClassfication}{this http url}
Groupwise Query Performance Prediction with BERT
Venue: arXiv cs.IR 2022
Year: 2022

While large-scale pre-trained language models like BERT have advanced the state-of-the-art in IR, its application in query performance prediction (QPP) is so far based on pointwise modeling of individual queries. Meanwhile, recent studies suggest that the cross-attention modeling of a group of documents can effectively boost performances for both learning-to-rank algorithms and BERT-based re-ranking. To this end, a BERT-based groupwise QPP model is proposed, in which the ranking contexts of a list of queries are jointly modeled to predict the relative performance of individual queries. Extensive experiments on three standard TREC collections showcase effectiveness of our approach. Our code is available at https://github.com/VerdureChen/Group-QPP.
Multi-UE Multi-AP Beam Alignment in User-Centric Cell-Free Massive MIMO Systems Operating at mmWave
Venue: arXiv cs.IT 2022
Year: 2022

This paper considers the problem of beam alignment in a cell-free massive MIMO deployment with multiple access points (APs) and multiple user equipments (UEs) simultaneously operating in the same millimeter wave frequency band. Assuming the availability of a control channel at sub-6 GHz frequencies, a protocol is developed that permits estimating, for each UE, the strongest propagation path from each of the surrounding APs, and to perform user-centric association between the UEs and the APs. Estimation of the strongest paths from nearby APs is realized at the UE in a one-phase procedure, during which all the APs simultaneously transmit on pseudo-randomly selected channels with pseudo-random transmit beamformers. An algorithm for orthogonal channels assignment to the APs is also proposed, with the aim of minimizing the mutual interference between APs that transmit on the same channels. The performance of the proposed strategy is evaluated both in terms of probability of correct detection of the directions of arrival and of departure associated to the strongest beam from nearby APs, and in terms of downlink and uplink signal-to-interference-plus-noise ratio. Numerical results show that the proposed approach is effective and capable of efficiently realizing beam alignment in a multi-UE multi-AP wireless scenario.
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Venue: arXiv cs.GT 2022
Year: 2022

Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute $\varepsilon$-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis, with an approximation guarantee of $(0.3393+δ)$, remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a $(\frac{1}{3}+δ)$-Nash equilibrium, for any constant $δ>0$. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of Tsaknakis and Spirakis, and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.
MathPartner Computer Algebra
Venue: arXiv cs.SC 2022
Year: 2022

In this paper, we describe general characteristics of the MathPartner computer algebra system (CAS) and Mathpar programming language thereof. MathPartner can be used for scientific and engineering calculations, as well as in high schools and universities. It allows one to carry out both simple calculations (acting as a scientific calculator) and complex calculations with large-scale mathematical objects. Mathpar is a procedural language; it supports a large number of elementary and special functions, as well as matrix and polynomial operators. This service allows one to build function images and animate them. MathPartner also makes it possible to solve some symbolic computation problems on supercomputers with distributed memory. We highlight main differences of MathPartner from other CASs and describe the Mathpar language along with the user service provided.
Relevance Models Based on the Knowledge Gap
Venue: arXiv cs.IR 2022
Year: 2022

Search systems are increasingly used for gaining knowledge through accessing relevant resources from a vast volume of content. However, search systems provide only limited support to users in knowledge acquisition contexts. Specifically, they do not fully consider the knowledge gap which we define as the gap existing between what the user knows and what the user intends to learn. The effects of considering the knowledge gap for knowledge acquisition tasks remain largely unexplored in search systems. We propose to model and incorporate the knowledge gap into search algorithms. We plan to explore to what extent the incorporation of the knowledge gap leads to an improvement in the performance of search systems in knowledge acquisition tasks. Furthermore, we aim to investigate and design a metric for the evaluation of the search systems' performance in the context of knowledge acquisition tasks.
Scaling Cross-Domain Content-Based Image Retrieval for E-commerce Snap and Search Application
Venue: arXiv cs.IR 2022
Year: 2022

In this industry talk at ECIR 2022, we illustrate how we approach the main challenges from large scale cross-domain content-based image retrieval using a cascade method and a combination of our visual search and classification capabilities. Specifically, we present a system that is able to handle the scale of the data for e-commerce usage and the cross-domain nature of the query and gallery image pools. We showcase the approach applied in real-world e-commerce snap and search use case and its impact on ranking and latency performance.
A Simple Structure For Building A Robust Model
Venue: arXiv cs.CV 2022
Year: 2022

As deep learning applications, especially programs of computer vision, are increasingly deployed in our lives, we have to think more urgently about the security of these applications.One effective way to improve the security of deep learning models is to perform adversarial training, which allows the model to be compatible with samples that are deliberately created for use in attacking the model.Based on this, we propose a simple architecture to build a model with a certain degree of robustness, which improves the robustness of the trained network by adding an adversarial sample detection network for cooperative training. At the same time, we design a new data sampling strategy that incorporates multiple existing attacks, allowing the model to adapt to many different adversarial attacks with a single training.We conducted some experiments to test the effectiveness of this design based on Cifar10 dataset, and the results indicate that it has some degree of positive effect on the robustness of the model.Our code could be found at https://github.com/dowdyboy/simple_structure_for_robust_model .
Investigating Black-Box Function Recognition Using Hardware Performance Counters
Venue: arXiv cs.CR 2022
Year: 2022

This paper presents new methods and results for recognising black-box program functions using hardware performance counters (HPC), where an investigator can invoke and measure function calls. Important use cases include analysing compiled libraries, e.g. static and dynamic link libraries, and trusted execution environment (TEE) applications. We develop a generic approach to classify a comprehensive set of hardware events, e.g. branch mis-predictions and instruction retirements, to recognise standard benchmarking and cryptographic library functions. This includes various signing, verification and hash functions, and ciphers in numerous modes of operation. Three architectures are evaluated using off-the-shelf Intel/X86-64, ARM, and RISC-V CPUs. Next, we show that several known CVE-numbered OpenSSL vulnerabilities can be detected using HPC differences between patched and unpatched library versions. Further, we demonstrate that standardised cryptographic functions within ARM TrustZone TEE applications can be recognised using non-secure world HPC measurements, applying to platforms that insecurely perturb the performance monitoring unit (PMU) during TEE execution. High accuracy was achieved in all cases (86.22-99.83%) depending on the application, architectural, and compilation assumptions. Lastly, we discuss mitigations, outstanding challenges, and directions for future research.
Optimal security hardening over a probabilistic attack graph: a case study of an industrial control system using the CySecTool tool
Venue: arXiv cs.CR 2022
Year: 2022

CySecTool is a tool that finds a cost-optimal security controls portfolio in a given budget for a probabilistic attack graph. A portfolio is a set of counter-measures, or controls, against vulnerabilities adopted for a computer system, while an attack graph is a type of a threat scenario model. In an attack graph, nodes are privilege states of the attacker, edges are vulnerabilities escalating privileges, and controls reduce the probabilities of some vulnerabilities being exploited. The tool builds on an optimisation algorithm published by Khouzani et al. (2019), enabling a user to quickly create, edit, and incrementally improve models, analyse results for given portfolios and display the best solutions for all possible budgets in the form of a Pareto frontier. A case study was performed utilising a system graph and suspected attack paths prepared by industrial security engineers based on an industrial source with which they work. The goal of the case study is to model a supervisory control and data acquisition (SCADA) industrial system which, due to having the potential to harm people, necessitates strong protection while not allowing the use of typical penetration tools like vulnerability scanners. Results are analysed to show how a cyber-security analyst would use CySecTool to store cyber-security intelligence and draw further conclusions.
Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions
Venue: arXiv cs.GT 2022
Year: 2022

Combinatorial auctions (CAs) allow bidders to express complex preferences for bundles of goods being auctioned. However, the behavior of bidders under different payment rules is often unclear. In this paper, we aim to understand how core constraints interact with different core-selecting payment rules. In particular, we examine the natural and desirable non-decreasing property of payment rules, which states that bidders cannot decrease their payments by increasing their bids. Previous work showed that, in general, the widely used VCG-nearest payment rule violates the non-decreasing property in single-minded CAs. We prove that under a single effective core constraint, the VCG-nearest payment rule is non-decreasing. In order to determine in which auctions single effective core constraints occur, we introduce a conflict graph representation of single-minded CAs and find sufficient conditions for the single effective core constraint in CAs. Finally, we study the consequences on the behavior of the bidders and show that no over-bidding exists in any Nash equilibrium for non-decreasing core-selecting payment rules.
KnowAugNet: Multi-Source Medical Knowledge Augmented Medication Prediction Network with Multi-Level Graph Contrastive Learning
Venue: arXiv cs.AI 2022
Year: 2022

Predicting medications is a crucial task in many intelligent healthcare systems. It can assist doctors in making informed medication decisions for patients according to electronic medical records (EMRs). However, medication prediction is a challenging data mining task due to the complex relations between medical codes. Most existing studies focus on utilizing inherent relations between homogeneous codes of medical ontology graph to enhance their representations using supervised methods, and few studies pay attention to the valuable relations between heterogeneous or homogeneous medical codes from history EMRs, which further limits the prediction performance and application scenarios. Therefore, to address these limitations, this paper proposes KnowAugNet, a multi-sourced medical knowledge augmented medication prediction network which can fully capture the diverse relations between medical codes via multi-level graph contrastive learning framework. Specifically, KnowAugNet first leverages the graph contrastive learning using graph attention network as the encoder to capture the implicit relations between homogeneous medical codes from the medical ontology graph and obtains the knowledge augmented medical codes embedding vectors. Then, it utilizes the graph contrastive learning using a weighted graph convolutional network as the encoder to capture the correlative relations between homogeneous or heterogeneous medical codes from the constructed medical prior relation graph and obtains the relation augmented medical codes embedding vectors. Finally, the augmented medical codes embedding vectors and the supervised medical codes embedding vectors are retrieved and input to the sequential learning network to capture the temporal relations of medical codes and predict medications for patients.
Adversarial Attention for Human Motion Synthesis
Venue: arXiv cs.CV 2022
Year: 2022

Analysing human motions is a core topic of interest for many disciplines, from Human-Computer Interaction, to entertainment, Virtual Reality and healthcare. Deep learning has achieved impressive results in capturing human pose in real-time. On the other hand, due to high inter-subject variability, human motion analysis models often suffer from not being able to generalise to data from unseen subjects due to very limited specialised datasets available in fields such as healthcare. However, acquiring human motion datasets is highly time-consuming, challenging, and expensive. Hence, human motion synthesis is a crucial research problem within deep learning and computer vision. We present a novel method for controllable human motion synthesis by applying attention-based probabilistic deep adversarial models with end-to-end training. We show that we can generate synthetic human motion over both short- and long-time horizons through the use of adversarial attention. Furthermore, we show that we can improve the classification performance of deep learning models in cases where there is inadequate real data, by supplementing existing datasets with synthetic motions.
Human-AI Collaboration via Conditional Delegation: A Case Study of Content Moderation
Venue: arXiv cs.AI 2022
Year: 2022

Despite impressive performance in many benchmark datasets, AI models can still make mistakes, especially among out-of-distribution examples. It remains an open question how such imperfect models can be used effectively in collaboration with humans. Prior work has focused on AI assistance that helps people make individual high-stakes decisions, which is not scalable for a large amount of relatively low-stakes decisions, e.g., moderating social media comments. Instead, we propose conditional delegation as an alternative paradigm for human-AI collaboration where humans create rules to indicate trustworthy regions of a model. Using content moderation as a testbed, we develop novel interfaces to assist humans in creating conditional delegation rules and conduct a randomized experiment with two datasets to simulate in-distribution and out-of-distribution scenarios. Our study demonstrates the promise of conditional delegation in improving model performance and provides insights into design for this novel paradigm, including the effect of AI explanations.
Generalizable Neural Performer: Learning Robust Radiance Fields for Human Novel View Synthesis
Venue: arXiv cs.CV 2022
Year: 2022

This work targets at using a general deep learning framework to synthesize free-viewpoint images of arbitrary human performers, only requiring a sparse number of camera views as inputs and skirting per-case fine-tuning. The large variation of geometry and appearance, caused by articulated body poses, shapes and clothing types, are the key bottlenecks of this task. To overcome these challenges, we present a simple yet powerful framework, named Generalizable Neural Performer (GNR), that learns a generalizable and robust neural body representation over various geometry and appearance. Specifically, we compress the light fields for novel view human rendering as conditional implicit neural radiance fields from both geometry and appearance aspects. We first introduce an Implicit Geometric Body Embedding strategy to enhance the robustness based on both parametric 3D human body model and multi-view images hints. We further propose a Screen-Space Occlusion-Aware Appearance Blending technique to preserve the high-quality appearance, through interpolating source view appearance to the radiance fields with a relax but approximate geometric guidance. To evaluate our method, we present our ongoing effort of constructing a dataset with remarkable complexity and diversity. The dataset GeneBody-1.0, includes over 360M frames of 370 subjects under multi-view cameras capturing, performing a large variety of pose actions, along with diverse body shapes, clothing, accessories and hairdos. Experiments on GeneBody-1.0 and ZJU-Mocap show better robustness of our methods than recent state-of-the-art generalizable methods among all cross-dataset, unseen subjects and unseen poses settings. We also demonstrate the competitiveness of our model compared with cutting-edge case-specific ones. Dataset, code and model will be made publicly available.
AU-NN: ANFIS Unit Neural Network
Venue: arXiv cs.LG 2022
Year: 2022

In this paper is described the ANFIS Unit Neural Network, a deep neural network where each neuron is an independent ANFIS. Two use cases of this network are shown to test the capability of the network. (i) Classification of five imagined words. (ii) Incremental learning in the task of detecting Imagined Word Segments vs. Idle State Segments. In both cases, the proposed network outperforms the conventional methods. Additionally, is described a process of classification where instead of taking the whole instance as one example, each instance is decomposed into a set of smaller instances, and the classification is done by a majority vote over all the predictions of the set. The codes to build the AU-NN used in this paper, are available on the github repository https://github.com/tonahdztoro/AU_NN.
Dynamic Ensemble Bayesian Filter for Robust Control of a Human Brain-machine Interface
Venue: arXiv cs.LG 2022
Year: 2022

Objective: Brain-machine interfaces (BMIs) aim to provide direct brain control of devices such as prostheses and computer cursors, which have demonstrated great potential for mobility restoration. One major limitation of current BMIs lies in the unstable performance in online control due to the variability of neural signals, which seriously hinders the clinical availability of BMIs. Method: To deal with the neural variability in online BMI control, we propose a dynamic ensemble Bayesian filter (DyEnsemble). DyEnsemble extends Bayesian filters with a dynamic measurement model, which adjusts its parameters in time adaptively with neural changes. This is achieved by learning a pool of candidate functions and dynamically weighting and assembling them according to neural signals. In this way, DyEnsemble copes with variability in signals and improves the robustness of online control. Results: Online BMI experiments with a human participant demonstrate that, compared with the velocity Kalman filter, DyEnsemble significantly improves the control accuracy (increases the success rate by 13.9% and reduces the reach time by 13.5% in the random target pursuit task) and robustness (performs more stably over different experiment days). Conclusion: Our results demonstrate the superiority of DyEnsemble in online BMI control. Significance: DyEnsemble frames a novel and flexible framework for robust neural decoding, which is beneficial to different neural decoding applications.
From Monolith to Microservices: Static and Dynamic Analysis Comparison
Venue: arXiv cs.SE 2022
Year: 2022

One of the most challenging problems in the migration of a monolith to a microservices architecture is the identification of the microservices boundaries. Several approaches have been recently proposed for the automatic identification of microservices, which, even though following the same basic steps, diverge on how data of the monolith system is collected and analysed. In this paper, we compare the decompositions generated for two monolith systems into a set of candidate microservices, when static and dynamic analysis data collection techniques are used. The decompositions are generated using a combination of similarity measures and are evaluated according to a complexity metric to answer the following research question: which collection of monolith data, static or dynamic analysis, allows to generate better decompositions? As result of the analysis we conclude that neither of the analysis techniques, static nor dynamic, outperforms the other, but the dynamic collection of data requires more effort.