OpenRaiser/Intern-Atlas huggingface dataset:
Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Venue: arXiv cs.LG 2022
Year: 2022

Rule sets are highly interpretable logical models in which the predicates for decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or, equivalently, the overall model comprises an unordered collection of if-then decision rules. In this paper, we consider a submodular optimization based approach for learning rule sets. The learning problem is framed as a subset selection task in which a subset of all possible rules needs to be selected to form an accurate and interpretable rule set. We employ an objective function that exhibits submodularity and thus is amenable to submodular optimization techniques. To overcome the difficulty arose from dealing with the exponential-sized ground set of rules, the subproblem of searching a rule is casted as another subset selection task that asks for a subset of features. We show it is possible to write the induced objective function for the subproblem as a difference of two submodular (DS) functions to make it approximately solvable by DS optimization algorithms. Overall, the proposed approach is simple, scalable, and likely to be benefited from further research on submodular optimization. Experiments on real datasets demonstrate the effectiveness of our method.
Probing for Passwords -- Privacy Implications of SSIDs in Probe Requests
Venue: arXiv cs.CR 2022
Year: 2022

Probe requests help mobile devices discover active Wi-Fi networks. They often contain a multitude of data that can be used to identify and track devices and thereby their users. The past years have been a cat-and-mouse game of improving fingerprinting and introducing countermeasures against fingerprinting. This paper analyses the content of probe requests sent by mobile devices and operating systems in a field experiment. In it, we discover that users (probably by accident) input a wealth of data into the SSID field and find passwords, e-mail addresses, names and holiday locations. With these findings we underline that probe requests should be considered sensitive data and be well protected. To preserve user privacy, we suggest and evaluate a privacy-friendly hash-based construction of probe requests and improved user controls.
Learning Digital Terrain Models from Point Clouds: ALS2DTM Dataset and Rasterization-based GAN
Venue: arXiv cs.CV 2022
Year: 2022

Despite the popularity of deep neural networks in various domains, the extraction of digital terrain models (DTMs) from airborne laser scanning (ALS) point clouds is still challenging. This might be due to the lack of dedicated large-scale annotated dataset and the data-structure discrepancy between point clouds and DTMs. To promote data-driven DTM extraction, this paper collects from open sources a large-scale dataset of ALS point clouds and corresponding DTMs with various urban, forested, and mountainous scenes. A baseline method is proposed as the first attempt to train a Deep neural network to extract digital Terrain models directly from ALS point clouds via Rasterization techniques, coined DeepTerRa. Extensive studies with well-established methods are performed to benchmark the dataset and analyze the challenges in learning to extract DTM from point clouds. The experimental results show the interest of the agnostic data-driven approach, with sub-metric error level compared to methods designed for DTM extraction. The data and source code is provided at https://lhoangan.github.io/deepterra/ for reproducibility and further similar research.
Efficient reversible data hiding via two layers of double-peak embedding
Venue: arXiv cs.CR 2022
Year: 2022

Reversible data hiding continues to attract significant attention in recent years. In particular, an increasing number of authors focus on the higher significant bit (HSB) plane of an image which can yield more redundant space. On the other hand, the lower significant bit planes are often ignored for embedding in existing schemes due to their harm to the embedding rate. This paper proposes an efficient reversible data hiding scheme via a double-peak two-layer embedding (DTLE) strategy with prediction error expansion. The higher six-bit planes of the image are assigned as the HSB plane, and double prediction error peaks are applied in either embedding layer. This makes fuller use of the redundancy space of images compared with the one error peak strategy. Moreover, we carry out the median-edge detector pre-processing for complex images to reduce the size of the auxiliary information. A series of experimental results show that our DTLE approach achieves up to 83% higher embedding rate on real-world datasets while guaranteeing better image quality.
FEL: High Capacity Learning for Recommendation and Ranking via Federated Ensemble Learning
Venue: arXiv cs.IR 2022
Year: 2022

Federated learning (FL) has emerged as an effective approach to address consumer privacy needs. FL has been successfully applied to certain machine learning tasks, such as training smart keyboard models and keyword spotting. Despite FL's initial success, many important deep learning use cases, such as ranking and recommendation tasks, have been limited from on-device learning. One of the key challenges faced by practical FL adoption for DL-based ranking and recommendation is the prohibitive resource requirements that cannot be satisfied by modern mobile systems. We propose Federated Ensemble Learning (FEL) as a solution to tackle the large memory requirement of deep learning ranking and recommendation tasks. FEL enables large-scale ranking and recommendation model training on-device by simultaneously training multiple model versions on disjoint clusters of client devices. FEL integrates the trained sub-models via an over-arch layer into an ensemble model that is hosted on the server. Our experiments demonstrate that FEL leads to 0.43-2.31% model quality improvement over traditional on-device federated learning - a significant improvement for ranking and recommendation system use cases.
An Analysis of Selection Bias Issue for Online Advertising
Venue: arXiv cs.IR 2022
Year: 2022

In online advertising, a set of potential advertisements can be ranked by a certain auction system where usually the top-1 advertisement would be selected and displayed at an advertising space. In this paper, we show a selection bias issue that is present in an auction system. We analyze that the selection bias destroy truthfulness of the auction, which implies that the buyers (advertisers) on the auction can not maximize their profits. Although selection bias is well known in the field of statistics and there are lot of studies for it, our main contribution is to combine the theoretical analysis of the bias with the auction mechanism. In our experiment using online A/B testing, we evaluate the selection bias on an auction system whose ranking score is the function of predicted CTR (click through rate) of advertisement. The experiment showed that the selection bias is drastically reduced by using a multi-task learning which learns the data for all advertisements.
Reconfiguration of Non-crossing Spanning Trees
Venue: arXiv cs.CG 2022
Year: 2022

For a set $P$ of $n$ points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of $P$ to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of $P$. There is a known upper bound of $2n-4$ flips [Avis and Fukuda, 1996] and a lower bound of $1.5n - 5$ flips. We give a reconfiguration algorithm that uses at most $2n-3$ flips but reduces that to $1.5n-2$ flips when one tree is a path and either: the points are in convex position; or the path is monotone in some direction. For points in convex position, we prove an upper bound of $2d - Ω(\log d)$ where $d$ is half the size of the symmetric difference between the trees. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we find exact minimum flip distances for small point sets using exhaustive search.
On the Eigenstructure of Rotations and Poses: Commonalities and Peculiarities
Venue: arXiv cs.RO 2022
Year: 2022

Rotations and poses are ubiquitous throughout many fields of science and engineering such as robotics, aerospace, computer vision and graphics. In this paper, we provide a complete characterization of rotations and poses in terms of the eigenstructure of their matrix Lie group representations, SO(3), SE(3) and Ad(SE(3)). An eigendecomposition of the pose representations reveals that they can be cast into a form very similar to that of rotations although the structure of the former can vary depending on the relative nature of the translation and rotation involved. Understanding the eigenstructure of these important quantities has merit in and of itself but it is also essential to appreciating such practical results as the minimal polynomial for rotations and poses and the calculation of Jacobians; moreover, we can speak of a principal-axis pose in much the same manner that we can of a principal-axis rotation.
Channel Estimation with Hybrid Reconfigurable Intelligent Metasurfaces
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable Intelligent Surfaces (RISs) are envisioned to play a key role in future wireless communications, enabling programmable radio propagation environments. They are usually considered as almost passive planar structures that operate as adjustable reflectors, giving rise to a multitude of implementation challenges, including the inherent difficulty in estimating the underlying wireless channels. In this paper, we focus on the recently conceived concept of Hybrid Reconfigurable Intelligent Surfaces (HRISs), which do not solely reflect the impinging waveform in a controllable fashion, but are also capable of sensing and processing an adjustable portion of it. We first present implementation details for this metasurface architecture and propose a convenient mathematical model for characterizing its dual operation. As an indicative application of HRISs in wireless communications, we formulate the individual channel estimation problem for the uplink of a multi-user HRIS-empowered communication system. Considering first a noise-free setting, we theoretically quantify the advantage of HRISs in notably reducing the amount of pilots needed for channel estimation, as compared to the case of purely reflective RISs. We then present closed-form expressions for the MSE performance in estimating the individual channels at the HRISs and the base station for the noisy model. Based on these derivations, we propose an automatic differentiation-based first-order optimization approach to efficiently determine the HRIS phase and power splitting configurations for minimizing the weighted sum-MSE performance. Our numerical evaluations demonstrate that HRISs do not only enable the estimation of the individual channels in HRIS-empowered communication systems, but also improve the ability to recover the cascaded channel, as compared to existing methods using passive and reflective RISs.
"You Just Assume It Is In There, I Guess": UK Families' Application And Knowledge Of Smart Home Cyber Security
Venue: arXiv cs.CR 2022
Year: 2022

The Internet of Things (IoT) is increasingly present in many family homes, yet it is unclear precisely how well families understand the cyber security threats and risks of using such devices, and how possible it is for them to educate themselves on these topics. Using a survey of 553 parents and interviews with 25 families in the UK, we find that families do not consider home IoT devices to be significantly different in terms of threats than more traditional home computers, and believe the major risks to be largely mitigated through consumer protection regulation. As a result, parents focus on teaching being careful with devices to prolong device life use, exposing their families to additional security risks and modeling incorrect security behaviors to their children. This is a risk for the present and also one for the future, as children are not taught about the IoT, and appropriate cyber security management of such devices, at school. We go on to suggest that steps must be taken by manufacturers and governments or appropriate trusted institutions to improve the cyber security knowledge and behaviors of both adults and children in relation to the use of home IoT devices.
Patch-based Object-centric Transformers for Efficient Video Generation
Venue: arXiv cs.CV 2022
Year: 2022

In this work, we present Patch-based Object-centric Video Transformer (POVT), a novel region-based video generation architecture that leverages object-centric information to efficiently model temporal dynamics in videos. We build upon prior work in video prediction via an autoregressive transformer over the discrete latent space of compressed videos, with an added modification to model object-centric information via bounding boxes. Due to better compressibility of object-centric representations, we can improve training efficiency by allowing the model to only access object information for longer horizon temporal information. When evaluated on various difficult object-centric datasets, our method achieves better or equal performance to other video generation models, while remaining computationally more efficient and scalable. In addition, we show that our method is able to perform object-centric controllability through bounding box manipulation, which may aid downstream tasks such as video editing, or visual planning. Samples are available at https://sites.google.com/view/povt-public
STable: Table Generation Framework for Encoder-Decoder Models
Venue: arXiv cs.CL 2022
Year: 2022

The output structure of database-like tables, consisting of values structured in horizontal rows and vertical columns identifiable by name, can cover a wide range of NLP tasks. Following this constatation, we propose a framework for text-to-table neural models applicable to problems such as extraction of line items, joint entity and relation extraction, or knowledge base population. The permutation-based decoder of our proposal is a generalized sequential method that comprehends information from all cells in the table. The training maximizes the expected log-likelihood for a table's content across all random permutations of the factorization order. During the content inference, we exploit the model's ability to generate cells in any order by searching over possible orderings to maximize the model's confidence and avoid substantial error accumulation, which other sequential models are prone to. Experiments demonstrate a high practical value of the framework, which establishes state-of-the-art results on several challenging datasets, outperforming previous solutions by up to 15%.
Balanced background and explanation data are needed in explaining deep learning models with SHAP: An empirical study on clinical decision making
Venue: arXiv cs.LG 2022
Year: 2022

Objective: Shapley additive explanations (SHAP) is a popular post-hoc technique for explaining black box models. While the impact of data imbalance on predictive models has been extensively studied, it remains largely unknown with respect to SHAP-based model explanations. This study sought to investigate the effects of data imbalance on SHAP explanations for deep learning models, and to propose a strategy to mitigate these effects. Materials and Methods: We propose to adjust class distributions in the background and explanation data in SHAP when explaining black box models. Our data balancing strategy is to compose background data and explanation data with an equal distribution of classes. To evaluate the effects of data adjustment on model explanation, we propose to use the beeswarm plot as a qualitative tool to identify "abnormal" explanation artifacts, and quantitatively test the consistency between variable importance and prediction power. We demonstrated our proposed approach in an empirical study that predicted inpatient mortality using the Medical Information Mart for Intensive Care (MIMIC-III) data and a multilayer perceptron. Results: Using the data balancing strategy would allow us to reduce the number of the artifacts in the beeswarm plot, thus mitigating the negative effects of data imbalance. Additionally, with the balancing strategy, the top-ranked variables from the corresponding importance ranking demonstrated improved discrimination power. Discussion and Conclusion: Our findings suggest that balanced background and explanation data could help reduce the noise in explanation results induced by skewed data distribution and improve the reliability of variable importance ranking. Furthermore, these balancing procedures improve the potential of SHAP in identifying patients with abnormal characteristics in clinical applications.
Hidden Markov Models with Momentum
Venue: arXiv cs.LG 2022
Year: 2022

Momentum is a popular technique for improving convergence rates during gradient descent. In this research, we experiment with adding momentum to the Baum-Welch expectation-maximization algorithm for training Hidden Markov Models. We compare discrete Hidden Markov Models trained with and without momentum on English text and malware opcode data. The effectiveness of momentum is determined by measuring the changes in model score and classification accuracy due to momentum. Our extensive experiments indicate that adding momentum to Baum-Welch can reduce the number of iterations required for initial convergence during HMM training, particularly in cases where the model is slow to converge. However, momentum does not seem to improve the final model performance at a high number of iterations.
ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret
Venue: arXiv cs.GT 2022
Year: 2022

Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies). One promising line of research uses neural networks to approximate counterfactual regret minimization (CFR) or its modern variants. DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to an importance sampling term inherited from Monte Carlo CFR (MCCFR). In this paper we propose an unbiased model-free method that does not require any importance sampling. Our method, ESCHER, is principled and is guaranteed to converge to an approximate Nash equilibrium with high probability. We show that the variance of the estimated regret of ESCHER is orders of magnitude lower than DREAM and other baselines. We then show that ESCHER outperforms the prior state of the art -- DREAM and neural fictitious self play (NFSP) -- on a number of games and the difference becomes dramatic as game size increases. In the very large game of dark chess, ESCHER is able to beat DREAM and NFSP in a head-to-head competition over $90\%$ of the time.
Towards Self-supervised and Weight-preserving Neural Architecture Search
Venue: arXiv cs.CV 2022
Year: 2022

Neural architecture search (NAS) algorithms save tremendous labor from human experts. Recent advancements further reduce the computational overhead to an affordable level. However, it is still cumbersome to deploy the NAS techniques in real-world applications due to the fussy procedures and the supervised learning paradigm. In this work, we propose the self-supervised and weight-preserving neural architecture search (SSWP-NAS) as an extension of the current NAS framework by allowing the self-supervision and retaining the concomitant weights discovered during the search stage. As such, we simplify the workflow of NAS to a one-stage and proxy-free procedure. Experiments show that the architectures searched by the proposed framework achieve state-of-the-art accuracy on CIFAR-10, CIFAR-100, and ImageNet datasets without using manual labels. Moreover, we show that employing the concomitant weights as initialization consistently outperforms the random initialization and the two-stage weight pre-training method by a clear margin under semi-supervised learning scenarios. Codes are publicly available at https://github.com/LzVv123456/SSWP-NAS.
Role of Blockchain in Revolutionizing Online Transactional Security
Venue: arXiv cs.CR 2022
Year: 2022

This paper highlights the necessity to use modern blockchain technology in traditional banking sector to reduce frauds and enable high-security transactions on a permanent blockchain ledger. Reviewing different channels through which the traditional banking servers could integrate blockchain use, it is signified how a huge anti-fraud stand can be taken against bank servers allowing fraudulent transactions daily. Usage of a blockchain-based ledger is highly impactful in terms of security of a banking organization. Blockchain-based currency tokens, also referred to as Cryptocurrencies are not regulated by the government, highly volatile, and anonymous to use. Furthermore, there is no security for any funds invested in a cryptocurrency market. However, the integration of a blockchain ledger in a traditional banking organization would strengthen the security to provide more stability and confidence to its customers and at the same time, make blockchain a more reliable method to consider due to being trusted by large financial organizations.
CASS: Cross Architectural Self-Supervision for Medical Image Analysis
Venue: arXiv cs.CV 2022
Year: 2022

Recent advances in deep learning and computer vision have reduced many barriers to automated medical image analysis, allowing algorithms to process label-free images and improve performance. However, existing techniques have extreme computational requirements and drop a lot of performance with a reduction in batch size or training epochs. This paper presents Cross Architectural - Self Supervision (CASS), a novel self-supervised learning approach that leverages Transformer and CNN simultaneously. Compared to the existing state of the art self-supervised learning approaches, we empirically show that CASS-trained CNNs and Transformers across four diverse datasets gained an average of 3.8% with 1% labeled data, 5.9% with 10% labeled data, and 10.13% with 100% labeled data while taking 69% less time. We also show that CASS is much more robust to changes in batch size and training epochs. Notably, one of the test datasets comprised histopathology slides of an autoimmune disease, a condition with minimal data that has been underrepresented in medical imaging. The code is open source and is available on GitHub.
Few-shot Question Generation for Personalized Feedback in Intelligent Tutoring Systems
Venue: arXiv cs.CL 2022
Year: 2022

Existing work on generating hints in Intelligent Tutoring Systems (ITS) focuses mostly on manual and non-personalized feedback. In this work, we explore automatically generated questions as personalized feedback in an ITS. Our personalized feedback can pinpoint correct and incorrect or missing phrases in student answers as well as guide them towards correct answer by asking a question in natural language. Our approach combines cause-effect analysis to break down student answers using text similarity-based NLP Transformer models to identify correct and incorrect or missing parts. We train a few-shot Neural Question Generation and Question Re-ranking models to show questions addressing components missing in the student answers which steers students towards the correct answer. Our model vastly outperforms both simple and strong baselines in terms of student learning gains by 45% and 23% respectively when tested in a real dialogue-based ITS. Finally, we show that our personalized corrective feedback system has the potential to improve Generative Question Answering systems.