OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Framework of Light Spanners II: Fine-Grained Optimality
Venue: arXiv cs.DS 2021
Year: 2021

Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (1) The techniques are ad hoc per graph class, and thus can't be applied broadly. (2) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (3) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. Our framework is developed in two papers. The current paper is the second of the two -- it builds on the basis of the unified framework laid in the first paper, and then strengthens it to achieve more refined optimality bounds for several graph classes. Among various applications and implications of our framework, we highlight here the following: For $K_r$-minor-free graphs, we provide a $(1+ε)$-spanner with lightness $\tilde{O}_{r,ε}( \frac{r}ε + \frac{1}{ε^2})$, improving the lightness bound $\tilde{O}_{r,ε}( \frac{r}{ε^3})$ of Borradaile, Le and Wulff-Nilsen. We complement our upper bound with a lower bound construction, for which any $(1+ε)$-spanner must have lightness $Ω(\frac{r}ε + \frac{1}{ε^2})$. We note that the quadratic dependency on $1/ε$ we proved here is surprising, as the prior work suggested that the dependency on $ε$ should be $1/ε$.
A Note on Sanitizing Streams with Differential Privacy
Venue: arXiv cs.DS 2021
Year: 2021

The literature on data sanitization aims to design algorithms that take an input dataset and produce a privacy-preserving version of it, that captures some of its statistical properties. In this note we study this question from a streaming perspective and our goal is to sanitize a data stream. Specifically, we consider low-memory algorithms that operate on a data stream and produce an alternative privacy-preserving stream that captures some statistical properties of the original input stream.
Common Sense Knowledge Learning for Open Vocabulary Neural Reasoning: A First View into Chronic Disease Literature
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we address reasoning tasks from open vocabulary Knowledge Bases (openKBs) using state-of-the-art Neural Language Models (NLMs) with applications in scientific literature. For this purpose, self-attention based NLMs are trained using a common sense KB as a source task. The NLMs are then tested on a target KB for open vocabulary reasoning tasks involving scientific knowledge related to the most prevalent chronic diseases (also known as non-communicable diseases, NCDs). Our results identified NLMs that performed consistently and with significance in knowledge inference for both source and target tasks. Furthermore, in our analysis by inspection we discussed the semantic regularities and reasoning capabilities learned by the models, while showing a first insight into the potential benefits of our approach to aid NCD research.
Automated Antenna Testing Using Encoder-Decoder-based Anomaly Detection
Venue: arXiv cs.LG 2021
Year: 2021

We propose a new method for testing antenna arrays that records the radiating electromagnetic (EM) field using an absorbing material and evaluating the resulting thermal image series through an AI using a conditional encoder-decoder model. Given the power and phase of the signals fed into each array element, we are able to reconstruct normal sequences through our trained model and compare it to the real sequences observed by a thermal camera. These thermograms only contain low-level patterns such as blobs of various shapes. A contour-based anomaly detector can then map the reconstruction error matrix to an anomaly score to identify faulty antenna arrays and increase the classification F-measure (F-M) by up to 46%. We show our approach on the time series thermograms collected by our antenna testing system. Conventionally, a variational autoencoder (VAE) learning observation noise may yield better results than a VAE with a constant noise assumption. However, we demonstrate that this is not the case for anomaly detection on such low-level patterns for two reasons. First, the baseline metric reconstruction probability, which incorporates the learned observation noise, fails to differentiate anomalous patterns. Second, the area under the receiver operating characteristic (ROC) curve of a VAE with a lower observation noise assumption achieves 11.83% higher than that of a VAE with learned noise.
Evading Malware Analysis Using Reverse Execution
Venue: arXiv cs.CR 2021
Year: 2021

Malware is a security threat, and various means are adapted to detect and block them. In this paper, we demonstrate a method where malware can evade malware analysis. The method is based on single-step reverse execution of code using the self-debugging feature. We discuss how self-debugging code works and use that to derive reverse execution for any payload. Further, we demonstrate the feasibility of a detection evading malware through a real implementation that targets Linux x86-64 architecture for a reference implementation. The reference implementation produces one result when run in one direction and a different result when run in the reverse direction.
Calibrated Feature Decomposition for Generalizable Person Re-Identification
Venue: arXiv cs.CV 2021
Year: 2021

Existing disentangled-based methods for generalizable person re-identification aim at directly disentangling person representations into domain-relevant interference and identity-relevant feature. However, they ignore that some crucial characteristics are stubbornly entwined in both the domain-relevant interference and identity-relevant feature, which are intractable to decompose in an unsupervised manner. In this paper, we propose a simple yet effective Calibrated Feature Decomposition (CFD) module that focuses on improving the generalization capacity for person re-identification through a more judicious feature decomposition and reinforcement strategy. Specifically, a calibrated-and-standardized Batch normalization (CSBN) is designed to learn calibrated person representation by jointly exploring intra-domain calibration and inter-domain standardization of multi-source domain features. CSBN restricts instance-level inconsistency of feature distribution for each domain and captures intrinsic domain-level specific statistics. The calibrated person representation is subtly decomposed into the identity-relevant feature, domain feature, and the remaining entangled one. For enhancing the generalization ability and ensuring high discrimination of the identity-relevant feature, a calibrated instance normalization (CIN) is introduced to enforce discriminative id-relevant information, and filter out id-irrelevant information, and meanwhile the rich complementary clues from the remaining entangled feature are further employed to strengthen it. Extensive experiments demonstrate the strong generalization capability of our framework. Our models empowered by CFD modules significantly outperform the state-of-the-art domain generalization approaches on multiple widely-used benchmarks. Code will be made public: https://github.com/zkcys001/CFD.
Safe Screening for Sparse Conditional Random Fields
Venue: arXiv cs.CV 2021
Year: 2021

Sparse Conditional Random Field (CRF) is a powerful technique in computer vision and natural language processing for structured prediction. However, solving sparse CRFs in large-scale applications remains challenging. In this paper, we propose a novel safe dynamic screening method that exploits an accurate dual optimum estimation to identify and remove the irrelevant features during the training process. Thus, the problem size can be reduced continuously, leading to great savings in the computational cost without sacrificing any accuracy on the finally learned model. To the best of our knowledge, this is the first screening method which introduces the dual optimum estimation technique -- by carefully exploring and exploiting the strong convexity and the complex structure of the dual problem -- in static screening methods to dynamic screening. In this way, we can absorb the advantages of both the static and dynamic screening methods and avoid their drawbacks. Our estimation would be much more accurate than those developed based on the duality gap, which contributes to a much stronger screening rule. Moreover, our method is also the first screening method in sparse CRFs and even structure prediction models. Experimental results on both synthetic and real-world datasets demonstrate that the speedup gained by our method is significant.
Projection-based Classification of Surfaces for 3D Human Mesh Sequence Retrieval
Venue: arXiv cs.CG 2021
Year: 2021

We analyze human poses and motion by introducing three sequences of easily calculated surface descriptors that are invariant under reparametrizations and Euclidean transformations. These descriptors are obtained by associating to each finitely-triangulated surface two functions on the unit sphere: for each unit vector u we compute the weighted area of the projection of the surface onto the plane orthogonal to u and the length of its projection onto the line spanned by u. The L2 norms and inner products of the projections of these functions onto the space of spherical harmonics of order k provide us with three sequences of Euclidean and reparametrization invariants of the surface. The use of these invariants reduces the comparison of 3D+time surface representations to the comparison of polygonal curves in R^n. The experimental results on the FAUST and CVSSP3D artificial datasets are promising. Moreover, a slight modification of our method yields good results on the noisy CVSSP3D real dataset.
Scheduling Appointments Online:\\ The Power of Deferred Decision-Making
Venue: arXiv cs.DS 2021
Year: 2021

The recently introduced online Minimum Peak Appointment Scheduling (MPAS) problem is a variant of the online bin-packing problem that allows for deferred decision making. Specifically, it allows for the problem to be split into an online phase where a stream of appointment requests arrive requiring a scheduled time, followed by an offline phase where those appointments are scheduled into rooms. Similar to the bin-packing problem, the aim is to use the minimum number of rooms in the final configuration. This model more accurately captures scheduling appointments than bin packing. For example, a dialysis patient needs to know what time to arrive for an appointment, but does not need to know the assigned station ahead of time. Previous work developed a randomized algorithm for this problem which achieved an asymptotic competitive ratio of at most 1.5, proving that online MPAS was fundamentally different from the online bin-packing problem. Our main contribution is to develop a new randomized algorithm for the problem that achieves an asymptotic competitive ratio under 1.455, indicating the potential for further progress. This improvement is attained by modifying the process for scheduling appointments to increase the density of the packing in the worst case, along with utilizing the dual of the bin-packing linear programming relaxation to perform the analysis. We also present the first known lower bound of 1.2 on the asymptotic competitive ratio of both deterministic and randomized online MPAS algorithm. These results demonstrate how deferred decision-making can be leveraged to yield improved worst-case performance, a phenomenon which should be investigated in a broader class of settings.
How Can Applications of Blockchain and Artificial Intelligence Improve Performance of Internet of Things? -- A Survey
Venue: arXiv cs.NI 2021
Year: 2021

In the era of the Internet of Things (IoT), massive computing devices surrounding us operate and interact with each other to provide several significant services in industries, medical as well as in daily life activities at home, office, education sectors, and so on. The participating devices in an IoT network usually have resource constraints and the devices are prone to different cyber attacks, leading to the loopholes in the security and authentication. As a revolutionized and innovated technology, blockchain, that is applied in cryptocurrency, market prediction, etc., uses a distributed ledger that records transactions securely and efficiently. To utilize the great potential of blockchain, both industries and academia have paid a significant attention to integrate it with the IoT, as reported by several existing literature. On the other hand, Artificial Intelligence (AI) is able to embed intelligence in a system, and thus the AI can be integrated with IoT devices in order to automatically cope with different environments according to the demands. Furthermore, both blockchain and AI can be integrated with the IoT to design an automated secure and robust IoT model, as mentioned by numerous existing works. In this survey, we present a discussion on the IoT, blockchain, and AI, along with the descriptions of several research works that apply blockchain and AI in the IoT. In this direction, we point out strengths and limitations of the related existing researches. We also discuss different open challenges to exploit the full capacities of blockchain and AI in designing an IoT-based model. Therefore, the highlighted challenging issues can open the door for the development of future IoT models which will be intelligent and secure based on the integration of blockchain and AI with the IoT.
Visualization and Attack Prevention for a Sensor-Based Agricultural Monitoring System
Venue: arXiv cs.CR 2021
Year: 2021

This project proposes a sensor-based visual agricultural monitoring system. Distinguished from traditional agricultural monitoring systems, this system further analyzes basic agricultural data and prevents and monitors common wireless network attacks such as Selective Forwarding, Black Hole Attacks, Sinkhole Attacks, Flooding Attacks and Misdirection Attacks. Experimental verification and evaluation of the attack prevention and monitoring are also conducted.
Natural Language and Spatial Rules
Venue: arXiv cs.CL 2021
Year: 2021

We develop a system that formally represents spatial semantics concepts within natural language descriptions of spatial arrangements. The system builds on a model of spatial semantics representation according to which words in a sentence are assigned spatial roles and the relations among these roles are represented with spatial relations. We combine our system with the shape grammar formalism that uses shape rules to generate languages (sets) of two-dimensional shapes. Our proposed system consists of pairs of shape rules and verbal rules where the verbal rules describe in English the action of the associated shape rule. We present various types of natural language descriptions of shapes that are successfully parsed by our system and we discuss open questions and challenges we see at the interface of language and perception.
Empirical Conditional Method: A New Approach to Predict Throughput in TCP Mobile Data Network
Venue: arXiv cs.NI 2021
Year: 2021

Experience of live video streaming can be improved if future available bandwidth can be predicted more accurately at the video uploader side. Thus follows a natural question which is how to make predictions both easily and precisely in an ever-changing network. Researchers have developed many prediction algorithms in the literature, from where a simple algorithm, Arithmetic Mean (AM), stands out. Based on that, we are purposing a new method called Empirical Conditional Method (ECM) based on a Markov model, hoping to utilize more information in the past data to get a more accurate prediction without loss of practicality. Through simulations, we found that our ECM algorithm performs better than the commonly used AM one, in the sense of reducing the loss by about 10% compared with AM. Besides, ECM also has a higher utilization rate of available bandwidth, which means ECM can send more data out while not having a higher loss rate or delay, especially under a low FPS setting. ECM can be more helpful for those who have relatively limited networks to reach a more considerable balance between frame loss rate and video quality hence improving the quality of experience.
Multicriteria interpretability driven Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

Deep Learning methods are renowned for their performances, yet their lack of interpretability prevents them from high-stakes contexts. Recent model agnostic methods address this problem by providing post-hoc interpretability methods by reverse-engineering the model's inner workings. However, in many regulated fields, interpretability should be kept in mind from the start, which means that post-hoc methods are valid only as a sanity check after model training. Interpretability from the start, in an abstract setting, means posing a set of soft constraints on the model's behavior by injecting knowledge and annihilating possible biases. We propose a Multicriteria technique that allows to control the feature effects on the model's outcome by injecting knowledge in the objective function. We then extend the technique by including a non-linear knowledge function to account for more complex effects and local lack of knowledge. The result is a Deep Learning model that embodies interpretability from the start and aligns with the recent regulations. A practical empirical example based on credit risk, suggests that our approach creates performant yet robust models capable of overcoming biases derived from data scarcity.
Imbalanced data preprocessing techniques utilizing local data characteristics
Venue: arXiv cs.LG 2021
Year: 2021

Data imbalance, that is the disproportion between the number of training observations coming from different classes, remains one of the most significant challenges affecting contemporary machine learning. The negative impact of data imbalance on traditional classification algorithms can be reduced by the data preprocessing techniques, methods that manipulate the training data to artificially reduce the degree of imbalance. However, the existing data preprocessing techniques, in particular SMOTE and its derivatives, which constitute the most prevalent paradigm of imbalanced data preprocessing, tend to be susceptible to various data difficulty factors. This is in part due to the fact that the original SMOTE algorithm does not utilize the information about majority class observations. The focus of this thesis is development of novel data resampling strategies natively utilizing the information about the distribution of both minority and majority class. The thesis summarizes the content of 12 research papers focused on the proposed binary data resampling strategies, their translation to the multi-class setting, and the practical application to the problem of histopathological data classification.
Cross-Task Consistency Learning Framework for Multi-Task Learning
Venue: arXiv cs.CV 2021
Year: 2021

Multi-task learning (MTL) is an active field in deep learning in which we train a model to jointly learn multiple tasks by exploiting relationships between the tasks. It has been shown that MTL helps the model share the learned features between tasks and enhance predictions compared to when learning each task independently. We propose a new learning framework for 2-task MTL problem that uses the predictions of one task as inputs to another network to predict the other task. We define two new loss terms inspired by cycle-consistency loss and contrastive learning, alignment loss and cross-task consistency loss. Both losses are designed to enforce the model to align the predictions of multiple tasks so that the model predicts consistently. We theoretically prove that both losses help the model learn more efficiently and that cross-task consistency loss is better in terms of alignment with the straight-forward predictions. Experimental results also show that our proposed model achieves significant performance on the benchmark Cityscapes and NYU dataset.
Throughput Maximization for IRS-Aided MIMO FD-WPCN with Non-Linear EH Model
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies an intelligent reflecting surface (IRS)-aided multiple-input-multiple-output (MIMO) full-duplex (FD) wireless-powered communication network (WPCN), where a hybrid access point (HAP) operating in FD broadcasts energy signals to multiple devices for their energy harvesting (EH) in the downlink (DL) and meanwhile receives information signals from devices in the uplink (UL) with the help of an IRS. Taking into account the practical finite self-interference (SI) and the non-linear EH model, we formulate the weighted sum throughput maximization optimization problem by jointly optimizing DL/UL time allocation, precoding matrices at devices, transmit covariance matrices at the HAP, and phase shifts at the IRS. Since the resulting optimization problem is non-convex, there are no standard methods to solve it optimally in general. To tackle this challenge, we first propose an element-wise (EW) based algorithm, where each IRS phase shift is alternately optimized in an iterative manner. To reduce the computational complexity, a minimum mean-square error (MMSE) based algorithm is proposed, where we transform the original problem into an equivalent form based on the MMSE method, which facilities the design of an efficient iterative algorithm. In particular, the IRS phase shift optimization problem is recast as an second-order cone program (SOCP), where all the IRS phase shifts are simultaneously optimized. For comparison, we also study two suboptimal IRS beamforming configurations in simulations, namely partially dynamic IRS beamforming (PDBF) and static IRS beamforming (SBF), which strike a balance between the system performance and practical complexity.
Implicit Equivariance in Convolutional Networks
Venue: arXiv cs.CV 2021
Year: 2021

Convolutional Neural Networks(CNN) are inherently equivariant under translations, however, they do not have an equivalent embedded mechanism to handle other transformations such as rotations and change in scale. Several approaches exist that make CNNs equivariant under other transformation groups by design. Among these, steerable CNNs have been especially effective. However, these approaches require redesigning standard networks with filters mapped from combinations of predefined basis involving complex analytical functions. We experimentally demonstrate that these restrictions in the choice of basis can lead to model weights that are sub-optimal for the primary deep learning task (e.g. classification). Moreover, such hard-baked explicit formulations make it difficult to design composite networks comprising heterogeneous feature groups. To circumvent such issues, we propose Implicitly Equivariant Networks (IEN) which induce equivariance in the different layers of a standard CNN model by optimizing a multi-objective loss function that combines the primary loss with an equivariance loss term. Through experiments with VGG and ResNet models on Rot-MNIST , Rot-TinyImageNet, Scale-MNIST and STL-10 datasets, we show that IEN, even with its simple formulation, performs better than steerable networks. Also, IEN facilitates construction of heterogeneous filter groups allowing reduction in number of channels in CNNs by a factor of over 30% while maintaining performance on par with baselines. The efficacy of IEN is further validated on the hard problem of visual object tracking. We show that IEN outperforms the state-of-the-art rotation equivariant tracking method while providing faster inference speed.