OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Approximations of the Fisher Matrix in Neural Networks using Kronecker Product Singular Value Decomposition
Venue: arXiv cs.NE 2022
Year: 2022

Several studies have shown the ability of natural gradient descent to minimize the objective function more efficiently than ordinary gradient descent based methods. However, the bottleneck of this approach for training deep neural networks lies in the prohibitive cost of solving a large dense linear system corresponding to the Fisher Information Matrix (FIM) at each iteration. This has motivated various approximations of either the exact FIM or the empirical one. The most sophisticated of these is KFAC, which involves a Kronecker-factored block diagonal approximation of the FIM. With only a slight additional cost, a few improvements of KFAC from the standpoint of accuracy are proposed. The common feature of the four novel methods is that they rely on a direct minimization problem, the solution of which can be computed via the Kronecker product singular value decomposition technique. Experimental results on the three standard deep auto-encoder benchmarks showed that they provide more accurate approximations to the FIM. Furthermore, they outperform KFAC and state-of-the-art first-order methods in terms of optimization speed.
A Special Case of Schematic Syntactic Unification
Venue: arXiv cs.LO 2022
Year: 2022

We present a unification problem based on first-order syntactic unification which ask whether every problem in a schematically-defined sequence of unification problems is unifiable, so called loop unification. Alternatively, our problem may be formulated as a recursive procedure calling first-order syntactic unification on certain bindings occurring in the solved form resulting from unification. Loop unification is closely related to Narrowing as the schematic constructions can be seen as a rewrite rule applied during unification, and primal grammars, as we deal with recursive term constructions. However, loop unification relaxes the restrictions put on variables as fresh as well as used extra variables may be introduced by rewriting. In this work we consider an important special case, so called semiloop unification. We provide a sufficient condition for unifiability of the entire sequence based on the structure of a sufficiently long initial segment. It remains an open question whether this condition is also necessary for semiloop unification and how it may be extended to loop unification.
Towards Objective Metrics for Procedurally Generated Video Game Levels
Venue: arXiv cs.AI 2022
Year: 2022

With increasing interest in procedural content generation by academia and game developers alike, it is vital that different approaches can be compared fairly. However, evaluating procedurally generated video game levels is often difficult, due to the lack of standardised, game-independent metrics. In this paper, we introduce two simulation-based evaluation metrics that involve analysing the behaviour of an A* agent to measure the diversity and difficulty of generated levels in a general, game-independent manner. Diversity is calculated by comparing action trajectories from different levels using the edit distance, and difficulty is measured as how much exploration and expansion of the A* search tree is necessary before the agent can solve the level. We demonstrate that our diversity metric is more robust to changes in level size and representation than current methods and additionally measures factors that directly affect playability, instead of focusing on visual information. The difficulty metric shows promise, as it correlates with existing estimates of difficulty in one of the tested domains, but it does face some challenges in the other domain. Finally, to promote reproducibility, we publicly release our evaluation framework.
Tracking and Planning with Spatial World Models
Venue: arXiv cs.LG 2022
Year: 2022

We introduce a method for real-time navigation and tracking with differentiably rendered world models. Learning models for control has led to impressive results in robotics and computer games, but this success has yet to be extended to vision-based navigation. To address this, we transfer advances in the emergent field of differentiable rendering to model-based control. We do this by planning in a learned 3D spatial world model, combined with a pose estimation algorithm previously used in the context of TSDF fusion, but now tailored to our setting and improved to incorporate agent dynamics. We evaluate over six simulated environments based on complex human-designed floor plans and provide quantitative results. We achieve up to 92% navigation success rate at a frequency of 15 Hz using only image and depth observations under stochastic, continuous dynamics.
AI-based Re-identification of Behavioral Clickstream Data
Venue: arXiv cs.CR 2022
Year: 2022

AI-based face recognition, i.e., the re-identification of individuals within images, is an already well established technology for video surveillance, for user authentication, for tagging photos of friends, etc. This paper demonstrates that similar techniques can be applied to successfully re-identify individuals purely based on their behavioral patterns. In contrast to de-anonymization attacks based on record linkage, these methods do not require any overlap in data points between a released dataset and an identified auxiliary dataset. The mere resemblance of behavioral patterns between records is sufficient to correctly attribute behavioral data to identified individuals. Further, we can demonstrate that data perturbation does not provide protection, unless a significant share of data utility is being destroyed. These findings call for sincere cautions when sharing actual behavioral data with third parties, as modern-day privacy regulations, like the GDPR, define their scope based on the ability to re-identify. This has also strong implications for the Marketing domain, when dealing with potentially re-identify-able data sources like shopping behavior, clickstream data or cockies. We also demonstrate how synthetic data can offer a viable alternative, that is shown to be resilient against our introduced AI-based re-identification attacks.
A Multi-modal Fusion Framework Based on Multi-task Correlation Learning for Cancer Prognosis Prediction
Venue: arXiv cs.LG 2022
Year: 2022

Morphological attributes from histopathological images and molecular profiles from genomic data are important information to drive diagnosis, prognosis, and therapy of cancers. By integrating these heterogeneous but complementary data, many multi-modal methods are proposed to study the complex mechanisms of cancers, and most of them achieve comparable or better results from previous single-modal methods. However, these multi-modal methods are restricted to a single task (e.g., survival analysis or grade classification), and thus neglect the correlation between different tasks. In this study, we present a multi-modal fusion framework based on multi-task correlation learning (MultiCoFusion) for survival analysis and cancer grade classification, which combines the power of multiple modalities and multiple tasks. Specifically, a pre-trained ResNet-152 and a sparse graph convolutional network (SGCN) are used to learn the representations of histopathological images and mRNA expression data respectively. Then these representations are fused by a fully connected neural network (FCNN), which is also a multi-task shared network. Finally, the results of survival analysis and cancer grade classification output simultaneously. The framework is trained by an alternate scheme. We systematically evaluate our framework using glioma datasets from The Cancer Genome Atlas (TCGA). Results demonstrate that MultiCoFusion learns better representations than traditional feature extraction methods. With the help of multi-task alternating learning, even simple multi-modal concatenation can achieve better performance than other deep learning and traditional methods. Multi-task learning can improve the performance of multiple tasks not just one of them, and it is effective in both single-modal and multi-modal data.
Public Information Representation for Adversarial Team Games
Venue: arXiv cs.GT 2022
Year: 2022

The peculiarity of adversarial team games resides in the asymmetric information available to the team members during the play, which makes the equilibrium computation problem hard even with zero-sum payoffs. The algorithms available in the literature work with implicit representations of the strategy space and mainly resort to Linear Programming and column generation techniques to enlarge incrementally the strategy space. Such representations prevent the adoption of standard tools such as abstraction generation, game solving, and subgame solving, which demonstrated to be crucial when solving huge, real-world two-player zero-sum games. Differently from these works, we answer the question of whether there is any suitable game representation enabling the adoption of those tools. In particular, our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. In this converted game, the team is transformed into a single coordinator player who only knows information common to the whole team and prescribes to the players an action for any possible private state. Interestingly, we show that our game is more expressive than the original extensive-form game as any state/action abstraction of the extensive-form game can be captured by our representation, while the reverse does not hold. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one. To limit this explosion, we provide three algorithms, each returning an information-lossless abstraction that dramatically reduces the size of the tree. These abstractions can be produced without generating the original game tree. Finally, we show the effectiveness of the proposed approach by presenting experimental results on Kuhn and Leduc Poker games, obtained by applying state-of-art algorithms for two-player zero-sum games on the converted games
On-Device Learning with Cloud-Coordinated Data Augmentation for Extreme Model Personalization in Recommender Systems
Venue: arXiv cs.LG 2022
Year: 2022

Data heterogeneity is an intrinsic property of recommender systems, making models trained over the global data on the cloud, which is the mainstream in industry, non-optimal to each individual user's local data distribution. To deal with data heterogeneity, model personalization with on-device learning is a potential solution. However, on-device training using a user's small size of local samples will incur severe overfitting and undermine the model's generalization ability. In this work, we propose a new device-cloud collaborative learning framework, called CoDA, to break the dilemmas of purely cloud-based learning and on-device learning. The key principle of CoDA is to retrieve similar samples from the cloud's global pool to augment each user's local dataset to train the recommendation model. Specifically, after a coarse-grained sample matching on the cloud, a personalized sample classifier is further trained on each device for a fine-grained sample filtering, which can learn the boundary between the local data distribution and the outside data distribution. We also build an end-to-end pipeline to support the flows of data, model, computation, and control between the cloud and each device. We have deployed CoDA in a recommendation scenario of Mobile Taobao. Online A/B testing results show the remarkable performance improvement of CoDA over both cloud-based learning without model personalization and on-device training without data augmentation. Overhead testing on a real device demonstrates the computation, storage, and communication efficiency of the on-device tasks in CoDA.
Energy-Efficient Computation Offloading in MobileEdge Computing Systems with Uncertainties
Venue: arXiv cs.DC 2022
Year: 2022

Computation offloading is indispensable for mobile edge computing (MEC). It uses edge resources to enable intensive computations and save energy for resource-constrained devices. Existing works generally impose strong assumptions on radio channels and network queue sizes. However, practical MEC systems are subject to various uncertainties rendering these assumptions impractical. In this paper, we investigate the energy-efficient computation offloading problem by relaxing those common assumptions and considering intrinsic uncertainties in the network. Specifically, we minimize the worst-case expected energy consumption of a local device when executing a time-critical application modeled as a directed acyclic graph. We employ the extreme value theory to bound the occurrence probability of uncertain events. To solve the formulated problem, we develop an $ε$-bounded approximation algorithm based on column generation. The proposed algorithm can efficiently identify a feasible solution that is less than (1+$ε$) of the optimal one. We implement the proposed scheme on an Android smartphone and conduct extensive experiments using a real-world application. Experiment results corroborate that it will lead to lower energy consumption for the client device by considering the intrinsic uncertainties during computation offloading. The proposed computation offloading scheme also significantly outperforms other schemes in terms of energy saving.
Improving Proximity Classification for Contact Tracing using a Multi-channel Approach
Venue: arXiv cs.NI 2022
Year: 2022

Due to the COVID 19 pandemic, smartphone-based proximity tracing systems became of utmost interest. Many of these systems use BLE signals to estimate the distance between two persons. The quality of this method depends on many factors and, therefore, does not always deliver accurate results. In this paper, we present a multi-channel approach to improve proximity classification, and a novel, publicly available data set that contains matched IEEE 802.11 (2.4 GHz and 5 GHz) and BLE signal strength data, measured in four different environments. We have developed and evaluated a combined classification model based on BLE and IEEE 802.11 signals. Our approach significantly improves the distance classification and consequently also the contact tracing accuracy. We are able to achieve good results with our approach in everyday public transport scenarios. However, in our implementation based on IEEE 802.11 probe requests, we also encountered privacy problems and limitations due to the consistency and interval at which such probes are sent. We discuss these limitations and sketch how our approach could be improved to make it suitable for real-world deployment.
An Algorithmic Framework for Bias Bounties
Venue: arXiv cs.LG 2022
Year: 2022

We propose and analyze an algorithmic framework for "bias bounties": events in which external participants are invited to propose improvements to a trained model, akin to bug bounty events in software and security. Our framework allows participants to submit arbitrary subgroup improvements, which are then algorithmically incorporated into an updated model. Our algorithm has the property that there is no tension between overall and subgroup accuracies, nor between different subgroup accuracies, and it enjoys provable convergence to either the Bayes optimal model or a state in which no further improvements can be found by the participants. We provide formal analyses of our framework, experimental evaluation, and findings from a preliminary bias bounty event.
Conditional entropy minimization principle for learning domain invariant representation features
Venue: arXiv cs.LG 2022
Year: 2022

Invariance-principle-based methods such as Invariant Risk Minimization (IRM), have recently emerged as promising approaches for Domain Generalization (DG). Despite promising theory, such approaches fail in common classification tasks due to the mixing of true invariant features and spurious invariant features. To address this, we propose a framework based on the conditional entropy minimization (CEM) principle to filter-out the spurious invariant features leading to a new algorithm with a better generalization capability. We show that our proposed approach is closely related to the well-known Information Bottleneck (IB) framework and prove that under certain assumptions, entropy minimization can exactly recover the true invariant features. Our approach provides competitive classification accuracy compared to recent theoretically-principled state-of-the-art alternatives across several DG datasets.
Distantly supervised end-to-end medical entity extraction from electronic health records with human-level quality
Venue: arXiv cs.CL 2022
Year: 2022

Medical entity extraction (EE) is a standard procedure used as a first stage in medical texts processing. Usually Medical EE is a two-step process: named entity recognition (NER) and named entity normalization (NEN). We propose a novel method of doing medical EE from electronic health records (EHR) as a single-step multi-label classification task by fine-tuning a transformer model pretrained on a large EHR dataset. Our model is trained end-to-end in an distantly supervised manner using targets automatically extracted from medical knowledge base. We show that our model learns to generalize for entities that are present frequently enough, achieving human-level classification quality for most frequent entities. Our work demonstrates that medical entity extraction can be done end-to-end without human supervision and with human quality given the availability of a large enough amount of unlabeled EHR and a medical knowledge base.
Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos
Venue: arXiv cs.LG 2022
Year: 2022

The recent framework of performative prediction is aimed at capturing settings where predictions influence the target/outcome they want to predict. In this paper, we introduce a natural multi-agent version of this framework, where multiple decision makers try to predict the same outcome. We showcase that such competition can result in interesting phenomena by proving the possibility of phase transitions from stability to instability and eventually chaos. Specifically, we present settings of multi-agent performative prediction where under sufficient conditions their dynamics lead to global stability and optimality. In the opposite direction, when the agents are not sufficiently cautious in their learning/updates rates, we show that instability and in fact formal chaos is possible. We complement our theoretical predictions with simulations showcasing the predictive power of our results.
Impacts of Hardware Impairments on Mutualistic Cooperative Ambient Backscatter Communications
Venue: arXiv cs.IT 2022
Year: 2022

In mutualistic cooperative ambient backscatter communications (AmBC), Internet-of-Things (IoT) device sends its information to a desired receiver by modulating and backscattering the primary signal, while providing beneficial multipath diversity to the primary receiver in return, thus forming a mutualism relationship between the AmBC and primary links. We note that the hardware impairments (HIs), which are unavoidable in practical systems and may significantly affect the transmission rates of the primary and AmBC links and their mutualism relationships, have been largely ignored in the study of mutualistic cooperative AmBC networks. In this paper, we consider a mutualistic cooperative AmBC network under HIs, and study the impacts of HIs on the achievable rates of the primary link and the AmBC link. In particular, we theoretically prove that although HIs degrades the rate of each link, the mutualism relationship between the AmBC and primary links is maintained, i.e., the rate of the primary link in the mutualistic cooperative AmBC network is still higher than that without the AmBC link. The closed-form rate expressions of both the AmBC and primary links are derived. Computer simulations are provided to validate our theoretical analysis.
Network-Side Digital Contact Tracing on a Large University Campus
Venue: arXiv cs.NI 2022
Year: 2022

We describe a study conducted at a large public university campus in the United States which shows the efficacy of network log information for digital contact tracing and prediction of COVID-19 cases. Over the period of January 18, 2021 to May 7, 2021, more than 216 million client-access-point associations were logged across more than 11,000 wireless access points (APs). The association information was used to find potential contacts for approximately 30,000 individuals. Contacts are determined using an AP colocation algorithm, which supposes contact when two individuals connect to the same WiFi AP at approximately the same time. The approach was validated with a truth set of 350 positive COVID-19 cases inferred from the network log data by observing associations with APs in isolation residence halls reserved for individuals with a confirmed (clinical) positive COVID-19 test result. The network log data and AP-colocation have a predictive value of greater than 10%; more precisely, the contacts of an individual with a confirmed positive COVID-19 test have greater than a 10\% chance of testing positive in the following 7 days (compared with a 0.79% chance when chosen at random, a relative risk ratio of 12.6). Moreover, a cumulative exposure score is computed to account for exposure to multiple individuals that test positive. Over the duration of the study, the cumulative exposure score predicts positive cases with a true positive rate of 16.5% and missed detection rate of 79% at a specified operating point.
From an Authentication Question to a Public Social Event: Characterizing Birthday Sharing on Twitter
Venue: arXiv cs.SI 2022
Year: 2022

Date of birth (DOB) has historically been considered as private information and safe to use for authentication, but recent years have seen a shift towards wide public sharing. In this work we characterize how modern social media users are approaching the sharing of birthday wishes publicly online. Over 45 days, we collected over 2.8M tweets wishing happy birthday to 724K Twitter accounts. For 50K accounts, their age was likely mentioned revealing their DOB, and 10% were protected accounts. Our findings show that the majority of both public and protected accounts seem to be accepting of their birthdays and DOB being revealed online by their friends even when they do not have it listed on their profiles. We further complemented our findings through a survey to measure awareness of DOB disclosure issues and how people think about sharing different types of birthday-related information. Our analysis shows that giving birthday wishes to others online is considered a celebration and many users are quite comfortable with it. This view matches the trend also seen in security where the use of DOB in authentication process is no longer considered best practice.