OpenRaiser/Intern-Atlas huggingface dataset:
Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs
Venue: arXiv cs.DS 2021
Year: 2021

In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP is an IP of the form $\max \{ c^T x \mid \mathcal{A} x = b, \,l \leq x \leq u,\, x\text{ integral} \}$ where the constraint matrix $\mathcal{A}$ consists of small block matrices ordered on the diagonal line and for each stage there are larger blocks with few columns connecting the blocks in a tree like fashion. Over the last years there was enormous progress in the area of block structured IPs. For many of the known block IP classes - such as $n$-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained however was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of $t$ exponentials, where $t$ is the number of stages, while only a double exponential lower bound was known. In this paper we show that the tower of $t$ exponentials is actually not necessary. We can show an improved running time for the algorithm solving multistage stochastic IPs with a running time of $2^{(d\||A||_\infty)^{\mathcal{O}(d^{3t+1})}} \cdot poly(d,n)$, where $d$ is the sum of columns in the connecting blocks and $n$ is the number of blocks on the lowest stage. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant $t$. By this we come very close the known double exponential bound (based on the exponential time hypothesis) that holds already for two-stage stochastic IPs, i.e. multistage stochastic IPs with only two stages.
Multi-scale Iterative Residuals for Fast and Scalable Stereo Matching
Venue: arXiv cs.CV 2021
Year: 2021

Despite the remarkable progress of deep learning in stereo matching, there exists a gap in accuracy between real-time models and slower state-of-the-art models which are suitable for practical applications. This paper presents an iterative multi-scale coarse-to-fine refinement (iCFR) framework to bridge this gap by allowing it to adopt any stereo matching network to make it fast, more efficient and scalable while keeping comparable accuracy. To reduce the computational cost of matching, we use multi-scale warped features to estimate disparity residuals and push the disparity search range in the cost volume to a minimum limit. Finally, we apply a refinement network to recover the loss of precision which is inherent in multi-scale approaches. We test our iCFR framework by adopting the matching networks from state-of-the art GANet and AANet. The result is 49$\times$ faster inference time compared to GANetdeep and 4$\times$ less memory consumption, with comparable error. Our best performing network, which we call FRSNet is scalable even up to an input resolution of 6K on a GTX 1080Ti, with inference time still below one second and comparable accuracy to AANet+. It out-performs all real-time stereo methods and achieves competitive accuracy on the KITTI benchmark.
DP-XGBoost: Private Machine Learning at Scale
Venue: arXiv cs.LG 2021
Year: 2021

The big-data revolution announced ten years ago does not seem to have fully happened at the expected scale. One of the main obstacle to this, has been the lack of data circulation. And one of the many reasons people and organizations did not share as much as expected is the privacy risk associated with data sharing operations. There has been many works on practical systems to compute statistical queries with Differential Privacy (DP). There have also been practical implementations of systems to train Neural Networks with DP, but relatively little efforts have been dedicated to designing scalable classical Machine Learning (ML) models providing DP guarantees. In this work we describe and implement a DP fork of a battle tested ML model: XGBoost. Our approach beats by a large margin previous attempts at the task, in terms of accuracy achieved for a given privacy budget. It is also the only DP implementation of boosted trees that scales to big data and can run in distributed environments such as: Kubernetes, Dask or Apache Spark.
Battling Hateful Content in Indic Languages HASOC '21
Venue: arXiv cs.CL 2021
Year: 2021

The extensive rise in consumption of online social media (OSMs) by a large number of people poses a critical problem of curbing the spread of hateful content on these platforms. With the growing usage of OSMs in multiple languages, the task of detecting and characterizing hate becomes more complex. The subtle variations of code-mixed texts along with switching scripts only add to the complexity. This paper presents a solution for the HASOC 2021 Multilingual Twitter Hate-Speech Detection challenge by team PreCog IIIT Hyderabad. We adopt a multilingual transformer based approach and describe our architecture for all 6 subtasks as part of the challenge. Out of the 6 teams that participated in all the subtasks, our submissions rank 3rd overall.
Optimal Auction Design for the Gradual Procurement of Strategic Service Provider Agents
Venue: arXiv cs.GT 2021
Year: 2021

We consider an outsourcing problem where a software agent procures multiple services from providers with uncertain reliabilities to complete a computational task before a strict deadline. The service consumer requires a procurement strategy that achieves the optimal balance between success probability and invocation cost. However, the service providers are self-interested and may misrepresent their private cost information if it benefits them. For such settings, we design a novel procurement auction that provides the consumer with the highest possible revenue, while giving sufficient incentives to providers to tell the truth about their costs. This auction creates a contingent plan for gradual service procurement that suggests recruiting a new provider only when the success probability of the already hired providers drops below a time-dependent threshold. To make this auction incentive compatible, we propose a novel weighted threshold payment scheme which pays the minimum among all truthful mechanisms. Using the weighted payment scheme, we also design a low-complexity near-optimal auction that reduces the computational complexity of the optimal mechanism by 99% with only marginal performance loss (less than 1%). We demonstrate the effectiveness and strength of our proposed auctions through both game theoretical and numerical analysis. The experiment results confirm that the proposed auctions exhibit 59% improvement in performance over the current state-of-the-art, by increasing success probability up to 79% and reducing invocation cost by up to 11%.
Two-dimensional mesh generator in generalized coordinates implemented in Python
Venue: arXiv cs.MS 2021
Year: 2021

Through mathematical models, it is possible to turn a problem of the physical domain into the computational domain. In this context, the paper presents a two-dimensional mesh generator in generalized coordinates, which uses the Parametric Linear Spline method and partial differential equations. The generator is automated and able to treat real complex domains. The code was implemented in Python, applying the Numpy and Matplotlib libraries to matrix manipulations and graphical plots, respectively. Applications are made for monoblock meshes (two-dimensional shape of a bottle) and multi-block meshes (geometry of Igapó I lake, Londrina, Paraná, Brazil).
A First Polynomial Non-Clausal Class in Many-Valued Logic
Venue: arXiv cs.LO 2021
Year: 2021

The relevance of polynomial formula classes to deductive efficiency motivated their search, and currently, a great number of such classes is known. Nonetheless, they have been exclusively sought in the setting of clausal form and propositional logic, which is of course expressively limiting for real applications. As a consequence, a first polynomial propositional class in non-clausal (NC) form has recently been proposed. Along these lines and towards making NC tractability applicable beyond propositional logic, firstly, we define the Regular many-valued Horn Non-Clausal class, or RH, obtained by suitably amalgamating both regular classes: Horn and NC. Secondly, we demonstrate that the relationship between (1) RH and the regular Horn class is that syntactically RH subsumes the Horn class but that both classes are equivalent semantically; and between (2) RH and the regular non-clausal class is that RH contains all NC formulas whose clausal form is Horn. Thirdly, we define Regular Non-Clausal Unit-Resolution, or RUR-NC , and prove both that it is complete for RH and that checks its satisfiability in polynomial time. The latter fact shows that our intended goal is reached since RH is many-valued, non-clausal and tractable. As RH and RUR-NC are, both, basic in the DPLL scheme, the most efficient in propositional logic, and can be extended to some other non-classical logics, we argue that they pave the way for efficient non-clausal DPLL-based approximate reasoning.
Spoofing Detection on Hand Images Using Quality Assessment
Venue: arXiv cs.CV 2021
Year: 2021

Recent research on biometrics focuses on achieving a high success rate of authentication and addressing the concern of various spoofing attacks. Although hand geometry recognition provides adequate security over unauthorized access, it is susceptible to presentation attack. This paper presents an anti-spoofing method toward hand biometrics. A presentation attack detection approach is addressed by assessing the visual quality of genuine and fake hand images. A threshold-based gradient magnitude similarity quality metric is proposed to discriminate between the real and spoofed hand samples. The visual hand images of 255 subjects from the Bogazici University hand database are considered as original samples. Correspondingly, from each genuine sample, we acquire a forged image using a Canon EOS 700D camera. Such fake hand images with natural degradation are considered for electronic screen display based spoofing attack detection. Furthermore, we create another fake hand dataset with artificial degradation by introducing additional Gaussian blur, salt and pepper, and speckle noises to original images. Ten quality metrics are measured from each sample for classification between original and fake hand image. The classification experiments are performed using the k-nearest neighbors, random forest, and support vector machine classifiers, as well as deep convolutional neural networks. The proposed gradient similarity-based quality metric achieves 1.5% average classification er ror using the k-nearest neighbors and random forest classifiers. An average classification error of 2.5% is obtained using the baseline evaluation with the MobileNetV2 deep network for discriminating original and different types of fake hand samples.
Improving Software Engineering Research through Experimentation Workbenches
Venue: arXiv cs.SE 2021
Year: 2021

Experimentation with software prototypes plays a fundamental role in software engineering research. In contrast to many other scientific disciplines, however, explicit support for this key activity in software engineering is relatively small. While some approaches to improve this situation have been proposed by the software engineering community, experiments are still very difficult and sometimes impossible to replicate. In this paper, we propose the concept of an experimentation workbench as a means of explicit support for experimentation in software engineering research. In particular, we discuss core requirements that an experimentation workbench should satisfy in order to qualify as such and to offer a real benefit for researchers. Beyond their core benefits for experimentation, we stipulate that experimentation workbenches will also have benefits in regard to reproducibility and repeatability of software engineering research. Further, we illustrate this concept with a scenario and a case study, and describe relevant challenges as well as our experience with experimentation workbenches.
Ultra-Dense LEO Satellite-based Communication Systems: A Novel Modeling Technique
Venue: arXiv cs.IT 2021
Year: 2021

Low earth orbit (LEO) satellite plays an indispensable role in the earth network because of its low latency, large capacity, and seamless global coverage. For such an unprecedented extensive irregular system, stochastic geometry (SG) is a suitable research method. The SG model can not only cope with the increasing network scale but also accurately analyze and estimate the network's performance. Several standard satellite distribution models and satellite-ground channel models are investigated in this paper. System-level metrics such as coverage probability and their intermediates are introduced in the non-technical description. Then, the influence of some factors on latency and coverage probability is studied. Finally, this paper presents the possible challenges and corresponding solutions for the SG-based LEO satellite system analysis.
Optimal Model Averaging: Towards Personalized Collaborative Learning
Venue: arXiv cs.LG 2021
Year: 2021

In federated learning, differences in the data or objectives between the participating nodes motivate approaches to train a personalized machine learning model for each node. One such approach is weighted averaging between a locally trained model and the global model. In this theoretical work, we study weighted model averaging for arbitrary scalar mean estimation problems under minimal assumptions on the distributions. In a variant of the bias-variance trade-off, we find that there is always some positive amount of model averaging that reduces the expected squared error compared to the local model, provided only that the local model has a non-zero variance. Further, we quantify the (possibly negative) benefit of weighted model averaging as a function of the weight used and the optimal weight. Taken together, this work formalizes an approach to quantify the value of personalization in collaborative learning and provides a framework for future research to test the findings in multivariate parameter estimation and under a range of assumptions.
Anomaly-Based Intrusion Detection System for Cyber-Physical System Security
Venue: arXiv cs.CR 2021
Year: 2021

Over the past decade, industrial control systems have experienced a massive integration with information technologies. Industrial networks have undergone numerous technical transformations to protect operational and production processes, leading today to a new industrial revolution. Information Technology tools are not able to guarantee confidentiality, integrity and availability in the industrial domain, therefore it is of paramount importance to understand the interaction of the physical components with the networks. For this reason, usually, the industrial control systems are an example of Cyber-Physical Systems (CPS). This paper aims to provide a tool for the detection of cyber attacks in cyber-physical systems. This method is based on Machine Learning to increase the security of the system. Through the analysis of the values assumed by Machine Learning it is possible to evaluate the classification performance of the three models. The model obtained using the training set, allows to classify a sample of anomalous behavior and a sample that is related to normal behavior. The attack identification is implemented in water tank system, and the identification approach using Machine Learning aims to avoid dangerous states, such as the overflow of a tank. The results are promising, demonstrating its effectiveness.
RoBin: Facilitating the Reproduction of Configuration-Related Vulnerability
Venue: arXiv cs.CR 2021
Year: 2021

Vulnerability reproduction paves a way in debugging software failures, which need intensive manual efforts. However, some key factors (e.g., software configuration, trigger method) are often missing, so we can not directly reproduce the failure without extra attempts. Even worse, highly customized configuration options of programs create a barrier for reproducing the vulnerabilities that only appear under some specific combinations of configurations. In this paper, we address the problem mentioned above -- reproducing the configuration-related vulnerability. We try to solve it by proposing a binary similarity-based method to infer the specific building configurations via the binary from crash report. The main challenges are as follows: precise compilation option inference, program configuration inference, and source-code-to-binary matching. To achieve the goal, we implement RoBin, a binary similarity-based building configuration inference tool. To demonstrate the effectiveness, we test RoBin on 21 vulnerable cases upon 4 well-known open-source programs. It shows a strong ability in pinpointing the building configurations causing the vulnerability. The result can help developers reproduce and diagnose the vulnerability, and finally, patch the programs.
2nd Place Solution for SODA10M Challenge 2021 -- Continual Detection Track
Venue: arXiv cs.CV 2021
Year: 2021

In this technical report, we present our approaches for the continual object detection track of the SODA10M challenge. We adapt ResNet50-FPN as the baseline and try several improvements for the final submission model. We find that task-specific replay scheme, learning rate scheduling, model calibration, and using original image scale helps to improve performance for both large and small objects in images. Our team `hypertune28' secured the second position among 52 participants in the challenge. This work will be presented at the ICCV 2021 Workshop on Self-supervised Learning for Next-Generation Industry-level Autonomous Driving (SSLAD).
Unsupervised Source Separation By Steering Pretrained Music Models
Venue: arXiv cs.SD 2021
Year: 2021

We showcase an unsupervised method that repurposes deep models trained for music generation and music tagging for audio source separation, without any retraining. An audio generation model is conditioned on an input mixture, producing a latent encoding of the audio used to generate audio. This generated audio is fed to a pretrained music tagger that creates source labels. The cross-entropy loss between the tag distribution for the generated audio and a predefined distribution for an isolated source is used to guide gradient ascent in the (unchanging) latent space of the generative model. This system does not update the weights of the generative model or the tagger, and only relies on moving through the generative model's latent space to produce separated sources. We use OpenAI's Jukebox as the pretrained generative model, and we couple it with four kinds of pretrained music taggers (two architectures and two tagging datasets). Experimental results on two source separation datasets, show this approach can produce separation estimates for a wider variety of sources than any tested supervised or unsupervised system. This work points to the vast and heretofore untapped potential of large pretrained music models for audio-to-audio tasks like source separation.
Gophormer: Ego-Graph Transformer for Node Classification
Venue: arXiv cs.LG 2021
Year: 2021

Transformers have achieved remarkable performance in a myriad of fields including natural language processing and computer vision. However, when it comes to the graph mining area, where graph neural network (GNN) has been the dominant paradigm, transformers haven't achieved competitive performance, especially on the node classification task. Existing graph transformer models typically adopt fully-connected attention mechanism on the whole input graph and thus suffer from severe scalability issues and are intractable to train in data insufficient cases. To alleviate these issues, we propose a novel Gophormer model which applies transformers on ego-graphs instead of full-graphs. Specifically, Node2Seq module is proposed to sample ego-graphs as the input of transformers, which alleviates the challenge of scalability and serves as an effective data augmentation technique to boost model performance. Moreover, different from the feature-based attention strategy in vanilla transformers, we propose a proximity-enhanced attention mechanism to capture the fine-grained structural bias. In order to handle the uncertainty introduced by the ego-graph sampling, we further propose a consistency regularization and a multi-sample inference strategy for stabilized training and testing, respectively. Extensive experiments on six benchmark datasets are conducted to demonstrate the superiority of Gophormer over existing graph transformers and popular GNNs, revealing the promising future of graph transformers.
Memory visualization tool for training neural network
Venue: arXiv cs.SE 2021
Year: 2021

Software developed helps world a better place ranging from system software, open source, application software and so on. Software engineering does have neural network models applied to code suggestion, bug report summarizing and so on to demonstrate their effectiveness at a real SE task. Software and machine learning algorithms combine to make software give better solutions and understanding of environment. In software, there are both generalized applications which helps solve problems for entire world and also some specific applications which helps one particular community. To address the computational challenge in deep learning, many tools exploit hardware features such as multi-core CPUs and many-core GPUs to shorten the training time. Machine learning algorithms have a greater impact in the world but there is a considerable amount of memory utilization during the process. We propose a new tool for analysis of memory utilized for developing and training deep learning models. Our tool results in visual utilization of memory concurrently. Various parameters affecting the memory utilization are analysed while training. This tool helps in knowing better idea of processes or models which consumes more memory.
Self-aware Social Learning over Graphs
Venue: arXiv cs.MA 2021
Year: 2021

In this paper we study the problem of social learning under multiple true hypotheses and self-interested agents which exchange information over a graph. In this setup, each agent receives data that might be generated from a different hypothesis (or state) than the data other agents receive. In contrast to the related literature in social learning, which focuses on showing that the network achieves consensus, here we study the case where every agent is self-interested and wants to find the hypothesis that generates its own observations. However, agents do not know which ones of their peers wants to find the same state with them and as a result they do not know which agents they should cooperate with. To this end, we propose a scheme with adaptive combination weights and study the consistency of the agents' learning process. The scheme allows each agent to identify and collaborate with neighbors that observe the same hypothesis, while excluding others, thus resulting in improved performance compared to both non-cooperative learning and cooperative social learning solutions. We analyze the asymptotic behavior of agents' beliefs under the proposed social learning algorithm and provide sufficient conditions that enable all agents to correctly identify their true hypotheses. The theoretical analysis is corroborated by numerical simulations.