OpenRaiser/Intern-Atlas huggingface dataset:
Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints
Venue: arXiv cs.DS 2021
Year: 2021

We study flow scheduling under node capacity constraints. We are given capacitated nodes and an online sequence of jobs, each with a release time and a demand to be routed between two nodes. A schedule specifies which jobs are routed in each step, guaranteeing that the total demand on a node in any step is at most its capacity. A key metric in this scenario is response time: the time between a job's release and its completion. Prior work shows no un-augmented algorithm is competitive for average response time, and that a constant factor competitive ratio is achievable with augmentation exceeding 2 (Dinitz-Moseley Infocom 2020). For maximum response time, the best known result is a 2-competitive algorithm with a augmentation 4 (Jahanjou et al SPAA 2020). We improve these bounds under various response time objectives. We show that, without resource augmentation, the best competitive ratio for maximum response time is $Ω(n)$, where $n$ is the number of nodes. Our Proportional Allocation algorithm uses $(1+\varepsilon)$ resource augmentation to achieve a $(1/\varepsilon)$-competitive ratio in the setting with general demands and capacities, and splittable jobs. Our Batch Decomposition algorithm is $2$-competitive (resp., optimal) for maximum response time using resource augmentation 2 (resp., 4) in the setting with unit demands and capacities, and unsplittable jobs. We also derive bounds for the simultaneous approximation of average and maximum response time metrics.
An Underexplored Dilemma between Confidence and Calibration in Quantized Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Modern convolutional neural networks (CNNs) are known to be overconfident in terms of their calibration on unseen input data. That is to say, they are more confident than they are accurate. This is undesirable if the probabilities predicted are to be used for downstream decision making. When considering accuracy, CNNs are also surprisingly robust to compression techniques, such as quantization, which aim to reduce computational and memory costs. We show that this robustness can be partially explained by the calibration behavior of modern CNNs, and may be improved with overconfidence. This is due to an intuitive result: low confidence predictions are more likely to change post-quantization, whilst being less accurate. High confidence predictions will be more accurate, but more difficult to change. Thus, a minimal drop in post-quantization accuracy is incurred. This presents a potential conflict in neural network design: worse calibration from overconfidence may lead to better robustness to quantization. We perform experiments applying post-training quantization to a variety of CNNs, on the CIFAR-100 and ImageNet datasets.
Solving Linear Algebra by Program Synthesis
Venue: arXiv cs.LG 2021
Year: 2021

We solve MIT's Linear Algebra 18.06 course and Columbia University's Computational Linear Algebra COMS3251 courses with perfect accuracy by interactive program synthesis. This surprisingly strong result is achieved by turning the course questions into programming tasks and then running the programs to produce the correct answers. We use OpenAI Codex with zero-shot learning, without providing any examples in the prompts, to synthesize code from questions. We quantify the difference between the original question text and the transformed question text that yields a correct answer. Since all COMS3251 questions are not available online the model is not overfitting. We go beyond just generating code for questions with numerical answers by interactively generating code that also results visually pleasing plots as output. Finally, we automatically generate new questions given a few sample questions which may be used as new course content. This work is a significant step forward in solving quantitative math problems and opens the door for solving many university level STEM courses by machine.
An Exploratory Study on Perceptual Spaces of the Singing Voice
Venue: arXiv cs.SD 2021
Year: 2021

Sixty participants provided dissimilarity ratings between various singing techniques. Multidimensional scaling, class averaging and clustering techniques were used to analyse timbral spaces and how they change between different singers, genders and registers. Clustering analysis showed that ground-truth similarity and silhouette scores that were not significantly different between gender or register conditions, while similarity scores were positively correlated with participants' instrumental abilities and task comprehension. Participant feedback showed how a revised study design might mitigate noise in our data, leading to more detailed statistical results. Timbre maps and class distance analysis showed us which singing techniques remained similar to one another across gender and register conditions. This research provides insight into how the timbre space of singing changes under different conditions, highlights the subjectivity of perception between participants, and provides generalised timbre maps for regularisation in machine learning.
QA4PRF: A Question Answering based Framework for Pseudo Relevance Feedback
Venue: arXiv cs.IR 2021
Year: 2021

Pseudo relevance feedback (PRF) automatically performs query expansion based on top-retrieved documents to better represent the user's information need so as to improve the search results. Previous PRF methods mainly select expansion terms with high occurrence frequency in top-retrieved documents or with high semantic similarity with the original query. However, existing PRF methods hardly try to understand the content of documents, which is very important in performing effective query expansion to reveal the user's information need. In this paper, we propose a QA-based framework for PRF called QA4PRF to utilize contextual information in documents. In such a framework, we formulate PRF as a QA task, where the query and each top-retrieved document play the roles of question and context in the corresponding QA system, while the objective is to find some proper terms to expand the original query by utilizing contextual information, which are similar answers in QA task. Besides, an attention-based pointer network is built on understanding the content of top-retrieved documents and selecting the terms to represent the original query better. We also show that incorporating the traditional supervised learning methods, such as LambdaRank, to integrate PRF information will further improve the performance of QA4PRF. Extensive experiments on three real-world datasets demonstrate that QA4PRF significantly outperforms the state-of-the-art methods.
Analysis of 5G academic Network based on graph representation learning method
Venue: arXiv cs.SI 2021
Year: 2021

With the rapid development of 5th Generation Mobile Communication Technology (5G), the diverse forms of collaboration and extensive data in academic social networks constructed by 5G papers make the management and analysis of academic social networks increasingly challenging. Despite the particular success achieved by representation learning in analyzing academic and social networks, most present presentation learning models focus on maintaining the first-order and second-order similarity of nodes. They rarely possess similar structural characteristics of spatial independence in the network. This paper proposes a Low-order Network representation Learning Model (LNLM) based on Non-negative Matrix Factorization (NMF) to solve these problems. The model uses the random walk method to extract low-order features of nodes and map multiple components to a low-dimensional space, effectively maintaining the internal correlation between members. This paper verifies the performance of this model, conducts comparative experiments on four test datasets and four real network datasets through downstream tasks such as multi-label classification, clustering, and link prediction. Comparing eight mainstream network representation learning models shows that the proposed model can significantly improve the detection efficiency and learning methods and effectively extract local and low-order features of the network.
Data Augmentation using Random Image Cropping for High-resolution Virtual Try-On (VITON-CROP)
Venue: arXiv cs.CV 2021
Year: 2021

Image-based virtual try-on provides the capacity to transfer a clothing item onto a photo of a given person, which is usually accomplished by warping the item to a given human pose and adjusting the warped item to the person. However, the results of real-world synthetic images (e.g., selfies) from the previous method is not realistic because of the limitations which result in the neck being misrepresented and significant changes to the style of the garment. To address these challenges, we propose a novel method to solve this unique issue, called VITON-CROP. VITON-CROP synthesizes images more robustly when integrated with random crop augmentation compared to the existing state-of-the-art virtual try-on models. In the experiments, we demonstrate that VITON-CROP is superior to VITON-HD both qualitatively and quantitatively.
Hierarchical Topometric Representation of 3D Robotic Maps
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we propose a method for generating a hierarchical, volumetric topological map from 3D point clouds. There are three basic hierarchical levels in our map: $storey - region - volume$. The advantages of our method are reflected in both input and output. In terms of input, we accept multi-storey point clouds and building structures with sloping roofs or ceilings. In terms of output, we can generate results with metric information of different dimensionality, that are suitable for different robotics applications. The algorithm generates the volumetric representation by generating $volumes$ from a 3D voxel occupancy map. We then add $passage$s (connections between $volumes$), combine small $volumes$ into a big $region$ and use a 2D segmentation method for better topological representation. We evaluate our method on several freely available datasets. The experiments highlight the advantages of our approach.
A Markov Chain Approach for Myopic Multi-hop Relaying: Outage and Diversity Analysis
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, a cooperative protocol is investigated for a multi-hop network consisting of relays with buffers of finite size, which may operate in different communication modes. The protocol is based on the myopic decode-and-forward strategy, where each node of the network cooperates with a limited number of neighboring nodes for the transmission of the signals. Each relay stores in its buffer the messages that were successfully decoded, in order to forward them through the appropriate channel links, based on its supported communication modes. A complete theoretical framework is investigated that models the evolution of the buffers and the transitions at the operations of each relay as a state Markov chain (MC). We analyze the performance of the proposed protocol in terms of outage probability and derive an expression for the achieved diversity-multiplexing tradeoff, by using the state transition matrix and the related steady state of the MC. Our results show that the proposed protocol outperforms the conventional multi-hop relaying scheme and the system's outage probability as well as the achieved diversity order depend on the degree of cooperation among neighboring nodes and the communication model that is considered for every relay of the network.
Reshaping Smart Energy Transition: An analysis of human-building interactions in Qatar Using Machine Learning Techniques
Venue: arXiv cs.LG 2021
Year: 2021

Policy Planning have the potential to contribute to the strategic development and economic diversification of developing countries even without considerable structural changes. In this study, we analyzed a set of human-oriented dimensions aimed at improving energy policies related to the building sector in Qatar. Considering the high percentage of expatriate and migrant communities with different financial and cultural backgrounds and behavioral patterns compared with local communities in the GCC Union, it is required to investigate human dimensions to propose adequate energy policies. This study explored the correlations of socioeconomic, behavioral, and demographic dimensions to determine the main factors behind discrepancies in energy use, responsibilities, motivations, habits, and overall well-being. The sample included 2,200 people in Qatar, and it was clustered into two consumer categories: high and low. In particular, the study focused on exploring human indoor comfort perception dependencies with building features. Financial drivers, such as demand programs and energy subsidies, were explored in relation to behavioral patterns. Subsequently, the data analysis resulted in implications for energy policies regarding interventions, social well-being, and awareness. Machine learning methods were used to perform a feature importance analysis to determine the main factors of human behavior. The findings of this study demonstrated how human factors impact comfort perception in residential and work environments, norms, habits, self-responsibility, consequence awareness, and consumption. The study has important implications for developing targeted strategies aimed at improving the efficacy of energy policies and sustainability performance indicators.
Self-Stabilization and Byzantine Tolerance for Maximal Independent Set
Venue: arXiv cs.DC 2021
Year: 2021

We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau \cite{turau2007linear} for computing such a vertex set. Our algorithm is self-stabilizing and also works under the more difficult context of arbitrary Byzantine faults. Byzantine nodes can prevent nodes close to them from taking part in the independent set for an arbitrarily long time. We give boundaries to their impact by focusing on the set of all nodes excluding nodes at distance 1 or less of Byzantine nodes, and excluding some of the nodes at distance 2. As far as we know, we present the first algorithm tolerating both transient and Byzantine faults under the fair distributed daemon. We prove that this algorithm converges in $ \mathcal O(Δn)$ rounds w.h.p., where $n$ and $Δ$ are the size and the maximum degree of the network, resp. Additionally, we present a modified version of this algorithm for anonymous systems under the adversarial distributed daemon that converges in $ \mathcal O(n^{2})$ expected number of steps.
A first approach to closeness distributions
Venue: arXiv cs.AI 2021
Year: 2021

Probabilistic graphical models allow us to encode a large probability distribution as a composition of smaller ones. It is oftentimes the case that we are interested in incorporating in the model the idea that some of these smaller distributions are likely to be similar to one another. In this paper we provide an information geometric approach on how to incorporate this information, and see that it allows us to reinterpret some already existing models.
2.5D Vehicle Odometry Estimation
Venue: arXiv cs.RO 2021
Year: 2021

It is well understood that in ADAS applications, a good estimate of the pose of the vehicle is required. This paper proposes a metaphorically named 2.5D odometry, whereby the planar odometry derived from the yaw rate sensor and four wheel speed sensors is augmented by a linear model of suspension. While the core of the planar odometry is a yaw rate model that is already understood in the literature, we augment this by fitting a quadratic to the incoming signals, enabling interpolation, extrapolation, and a finer integration of the vehicle position. We show, by experimental results with a DGPS/IMU reference, that this model provides highly accurate odometry estimates, compared with existing methods. Utilising sensors that return the change in height of vehicle reference points with changing suspension configurations, we define a planar model of the vehicle suspension, thus augmenting the odometry model. We present an experimental framework and evaluations criteria by which the goodness of the odometry is evaluated and compared with existing methods. This odometry model has been designed to support low-speed surround-view camera systems that are well-known. Thus, we present some application results that show a performance boost for viewing and computer vision applications using the proposed odometry
Weakly-supervised fire segmentation by visualizing intermediate CNN layers
Venue: arXiv cs.CV 2021
Year: 2021

Fire localization in images and videos is an important step for an autonomous system to combat fire incidents. State-of-art image segmentation methods based on deep neural networks require a large number of pixel-annotated samples to train Convolutional Neural Networks (CNNs) in a fully-supervised manner. In this paper, we consider weakly supervised segmentation of fire in images, in which only image labels are used to train the network. We show that in the case of fire segmentation, which is a binary segmentation problem, the mean value of features in a mid-layer of classification CNN can perform better than conventional Class Activation Mapping (CAM) method. We also propose to further improve the segmentation accuracy by adding a rotation equivariant regularization loss on the features of the last convolutional layer. Our results show noticeable improvements over baseline method for weakly-supervised fire segmentation.
Formal Quantum Software Engineering: Introducing the Formal Methods of Software Engineering to Quantum Computing
Venue: arXiv cs.SE 2021
Year: 2021

Quantum computing (QC) represents the future of computing systems, but the tools for reasoning about the quantum model of computation, in which the laws obeyed are those on the quantum mechanical scale, are still a mix of linear algebra and Dirac notation; two subjects more suitable for physicists, rather than computer scientists and software engineers. On this ground, we believe it is possible to provide a more intuitive approach to thinking and writing about quantum computing systems, in order to simplify the design of quantum algorithms and the development of quantum software. In this paper, we move the first step in such direction, introducing a specification language as the tool to represent the operations of a quantum computer via axiomatic definitions, by adopting the same symbolisms and reasoning principles used by formal methods in software engineering. We name this approach formal quantum software engineering (F-QSE). This work assumes familiarity with the basic principles of quantum mechanics (QM), with the use of Zed (Z) which is a formal language of software engineering (SE), and with the notation and techniques of first-order logic (FOL) and functional programming (FP).
An Overview of Backdoor Attacks Against Deep Neural Networks and Possible Defences
Venue: arXiv cs.CR 2021
Year: 2021

Together with impressive advances touching every aspect of our society, AI technology based on Deep Neural Networks (DNN) is bringing increasing security concerns. While attacks operating at test time have monopolised the initial attention of researchers, backdoor attacks, exploiting the possibility of corrupting DNN models by interfering with the training process, represents a further serious threat undermining the dependability of AI techniques. In a backdoor attack, the attacker corrupts the training data so to induce an erroneous behaviour at test time. Test time errors, however, are activated only in the presence of a triggering event corresponding to a properly crafted input sample. In this way, the corrupted network continues to work as expected for regular inputs, and the malicious behaviour occurs only when the attacker decides to activate the backdoor hidden within the network. In the last few years, backdoor attacks have been the subject of an intense research activity focusing on both the development of new classes of attacks, and the proposal of possible countermeasures. The goal of this overview paper is to review the works published until now, classifying the different types of attacks and defences proposed so far. The classification guiding the analysis is based on the amount of control that the attacker has on the training process, and the capability of the defender to verify the integrity of the data used for training, and to monitor the operations of the DNN at training and test time. As such, the proposed analysis is particularly suited to highlight the strengths and weaknesses of both attacks and defences with reference to the application scenarios they are operating in.
A Spatial-temporal Graph Deep Learning Model for Urban Flood Nowcasting Leveraging Heterogeneous Community Features
Venue: arXiv cs.LG 2021
Year: 2021

The objective of this study is to develop and test a novel structured deep-learning modeling framework for urban flood nowcasting by integrating physics-based and human-sensed features. We present a new computational modeling framework including an attention-based spatial-temporal graph convolution network (ASTGCN) model and different streams of data that are collected in real-time, preprocessed, and fed into the model to consider spatial and temporal information and dependencies that improve flood nowcasting. The novelty of the computational modeling framework is threefold; first, the model is capable of considering spatial and temporal dependencies in inundation propagation thanks to the spatial and temporal graph convolutional modules; second, it enables capturing the influence of heterogeneous temporal data streams that can signal flooding status, including physics-based features such as rainfall intensity and water elevation, and human-sensed data such as flood reports and fluctuations of human activity. Third, its attention mechanism enables the model to direct its focus on the most influential features that vary dynamically. We show the application of the modeling framework in the context of Harris County, Texas, as the case study and Hurricane Harvey as the flood event. Results indicate that the model provides superior performance for the nowcasting of urban flood inundation at the census tract level, with a precision of 0.808 and a recall of 0.891, which shows the model performs better compared with some other novel models. Moreover, ASTGCN model performance improves when heterogeneous dynamic features are added into the model that solely relies on physics-based features, which demonstrates the promise of using heterogenous human-sensed data for flood nowcasting,
Which is Making the Contribution: Modulating Unimodal and Cross-modal Dynamics for Multimodal Sentiment Analysis
Venue: arXiv cs.LG 2021
Year: 2021

Multimodal sentiment analysis (MSA) draws increasing attention with the availability of multimodal data. The boost in performance of MSA models is mainly hindered by two problems. On the one hand, recent MSA works mostly focus on learning cross-modal dynamics, but neglect to explore an optimal solution for unimodal networks, which determines the lower limit of MSA models. On the other hand, noisy information hidden in each modality interferes the learning of correct cross-modal dynamics. To address the above-mentioned problems, we propose a novel MSA framework \textbf{M}odulation \textbf{M}odel for \textbf{M}ultimodal \textbf{S}entiment \textbf{A}nalysis ({$ M^3SA $}) to identify the contribution of modalities and reduce the impact of noisy information, so as to better learn unimodal and cross-modal dynamics. Specifically, modulation loss is designed to modulate the loss contribution based on the confidence of individual modalities in each utterance, so as to explore an optimal update solution for each unimodal network. Besides, contrary to most existing works which fail to explicitly filter out noisy information, we devise a modality filter module to identify and filter out modality noise for the learning of correct cross-modal embedding. Extensive experiments on publicly datasets demonstrate that our approach achieves state-of-the-art performance.