Abstract
While single-agent policy optimization in a fixed environment has attracted a lot of research attention recently in the reinforcement learning community, much less is known theoretically when there are multiple agents playing in a potentially competitive environment. We take steps forward by proposing and analyzing new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We consider two classes of transition structures: factored independent transition and single-controller transition. For both scenarios, we prove tight $\widetilde{\mathcal{O}}(\sqrt{K})$ regret bounds after $K$ episodes in a two-agent competitive game scenario. The regret of each agent is measured against a potentially adversarial opponent who can choose a single best policy in hindsight after observing the full policy sequence. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization in a non-stationary environment. When both players adopt the proposed algorithms, their overall optimality gap is $\widetilde{\mathcal{O}}(\sqrt{K})$.
$p$-DkNN: Out-of-Distribution Detection Through Statistical Testing of Deep Representations
Authors: Adam Dziedzic, Stephan Rabanser, Mohammad Yaghini, Armin Ale, Murat A. Erdogdu, Nicolas Papernot
Abstract
The lack of well-calibrated confidence estimates makes neural networks inadequate in safety-critical domains such as autonomous driving or healthcare. In these settings, having the ability to abstain from making a prediction on out-of-distribution (OOD) data can be as important as correctly classifying in-distribution data. We introduce $p$-DkNN, a novel inference procedure that takes a trained deep neural network and analyzes the similarity structures of its intermediate hidden representations to compute $p$-values associated with the end-to-end model prediction. The intuition is that statistical tests performed on latent representations can serve not only as a classifier, but also offer a statistically well-founded estimation of uncertainty. $p$-DkNN is scalable and leverages the composition of representations learned by hidden layers, which makes deep representation learning successful. Our theoretical analysis builds on Neyman-Pearson classification and connects it to recent advances in selective classification (reject option). We demonstrate advantageous trade-offs between abstaining from predicting on OOD inputs and maintaining high accuracy on in-distribution inputs. We find that $p$-DkNN forces adaptive attackers crafting adversarial examples, a form of worst-case OOD inputs, to introduce semantically meaningful changes to the inputs.
Teaching Interaction using State Diagrams
Authors: Padma Pasupathi (McMaster University), Christopher W. Schankula (McMaster University), Nicole DiVincenzo (McMaster University), Sarah Coker (McMaster University), Christopher Kumar Anand (McMaster University)
Subjects: Software Engineering (cs.SE); Programming Languages (cs.PL)
Abstract
To make computational thinking appealing to young learners, initial programming instruction looks very different now than a decade ago, with increasing use of graphics and robots both real and virtual. After the first steps, children want to create interactive programs, and they need a model for this. State diagrams provide such a model. This paper documents the design and implementation of a Model-Driven Engineering tool, SD Draw, that allows even primary-aged children to draw and understand state diagrams, and create modifiable app templates in the Elm programming language using the model-view-update pattern standard in Elm programs. We have tested this with grade 4 and 5 students. In our initial test, we discovered that children quickly understand the motivation and use of state diagrams using this tool, and will independently discover abstract states even if they are only taught to model using concrete states. To determine whether this approach is appropriate for children of this age we wanted to know: do children understand state diagrams, do they understand the role of reachability, and are they engaged by them? We found that they are able to translate between different representations of state diagrams, strongly indicating that they do understand them. We found with confidence p<0.001 that they do understand reachability by refuting the null hypothesis that they are creating diagrams randomly. And we found that they were engaged by the concept, with many students continuing to develop their diagrams on their own time after school and on the weekend.
XInsight: eXplainable Data Analysis Through The Lens of Causality
Abstract
In light of the growing popularity of Exploratory Data Analysis (EDA), understanding the underlying causes of the knowledge acquired by EDA is crucial, but remains under-researched. This study promotes for the first time a transparent and explicable perspective on data analysis, called eXplainable Data Analysis (XDA). XDA provides data analysis with qualitative and quantitative explanations of causal and non-causal semantics. This way, XDA will significantly improve human understanding and confidence in the outcomes of data analysis, facilitating accurate data interpretation and decision-making in the real world. For this purpose, we present XInsight, a general framework for XDA. XInsight is a three-module, end-to-end pipeline designed to extract causal graphs, translate causal primitives into XDA semantics, and quantify the quantitative contribution of each explanation to a data fact. XInsight uses a set of design concepts and optimizations to address the inherent difficulties associated with integrating causality into XDA. Experiments on synthetic and real-world datasets as well as human evaluations demonstrate the highly promising capabilities of XInsight.
"I Used To Carry A Wallet, Now I Just Need To Carry My Phone": Understanding Current Banking Practices and Challenges Among Older Adults in China
Authors: Xiaofu Jin, Mingming Fan
Subjects: Human-Computer Interaction (cs.HC); Computers and Society (cs.CY)
Abstract
Managing finances is crucial for older adults who are retired and may rely on savings to ensure their life quality. As digital banking platforms (e.g., mobile apps, electronic payment) gradually replace physical ones, it is critical to understand how they adapt to digital banking and the potential frictions they experience. We conducted semi-structured interviews with 16 older adults in China, where the aging population is the largest and digital banking grows fast. We also interviewed bank employees to gain complementary perspectives of these help givers. Our findings show that older adults used both physical and digital platforms as an ecosystem based on perceived pros and cons. Perceived usefulness, self-confidence, and social influence were key motivators for learning digital banking. They experienced app-related (e.g., insufficient error-recovery support) and user-related challenges (e.g., trust, security and privacy concerns, low perceived self-efficacy) and developed coping strategies. We discuss design considerations to improve their banking experiences.
Keyword: scaling
Inter-Frame Compression for Dynamic Point Cloud Geometry Coding
Authors: Anique Akhtar, Zhu Li, Geert Van der Auwera
Subjects: Computer Vision and Pattern Recognition (cs.CV); Multimedia (cs.MM); Image and Video Processing (eess.IV)
Abstract
Efficient point cloud compression is essential for applications like virtual and mixed reality, autonomous driving, and cultural heritage. In this paper, we propose a deep learning-based inter-frame encoding scheme for dynamic point cloud geometry compression. We propose a lossy geometry compression scheme that predicts the latent representation of the current frame using the previous frame by employing a novel prediction network. Our proposed network utilizes sparse convolutions with hierarchical multiscale 3D feature learning to encode the current frame using the previous frame. We employ convolution on target coordinates to map the latent representation of the previous frame to the downsampled coordinates of the current frame to predict the current frame's feature embedding. Our framework transmits the residual of the predicted features and the actual features by compressing them using a learned probabilistic factorized entropy model. At the receiver, the decoder hierarchically reconstructs the current frame by progressively rescaling the feature embedding. We compared our model to the state-of-the-art Video-based Point Cloud Compression (V-PCC) and Geometry-based Point Cloud Compression (G-PCC) schemes standardized by the Moving Picture Experts Group (MPEG). Our method achieves more than 91% BD-Rate Bjontegaard Delta Rate) reduction against G-PCC, more than 62% BD-Rate reduction against V-PCC intra-frame encoding mode, and more than 52% BD-Rate savings against V-PCC P-frame-based inter-frame encoding mode using HEVC.
Quiver neural networks
Authors: Iordan Ganev, Robin Walters
Subjects: Machine Learning (cs.LG); Representation Theory (math.RT)
Abstract
We develop a uniform theoretical approach towards the analysis of various neural network connectivity architectures by introducing the notion of a quiver neural network. Inspired by quiver representation theory in mathematics, this approach gives a compact way to capture elaborate data flows in complex network architectures. As an application, we use parameter space symmetries to prove a lossless model compression algorithm for quiver neural networks with certain non-pointwise activations known as rescaling activations. In the case of radial rescaling activations, we prove that training the compressed model with gradient descent is equivalent to training the original model with projected gradient descent.
Reconciling Security and Communication Efficiency in Federated Learning
Authors: Karthik Prasad, Sayan Ghosh, Graham Cormode, Ilya Mironov, Ashkan Yousefpour, Pierre Stock
Abstract
Cross-device Federated Learning is an increasingly popular machine learning setting to train a model by leveraging a large population of client devices with high privacy and security guarantees. However, communication efficiency remains a major bottleneck when scaling federated learning to production environments, particularly due to bandwidth constraints during uplink communication. In this paper, we formalize and address the problem of compressing client-to-server model updates under the Secure Aggregation primitive, a core component of Federated Learning pipelines that allows the server to aggregate the client updates without accessing them individually. In particular, we adapt standard scalar quantization and pruning methods to Secure Aggregation and propose Secure Indexing, a variant of Secure Aggregation that supports quantization for extreme compression. We establish state-of-the-art results on LEAF benchmarks in a secure Federated Learning setup with up to 40$\times$ compression in uplink communication with no meaningful loss in utility compared to uncompressed baselines.
Offline Reinforcement Learning at Multiple Frequencies
Authors: Kaylee Burns, Tianhe Yu, Chelsea Finn, Karol Hausman
Abstract
Leveraging many sources of offline robot data requires grappling with the heterogeneity of such data. In this paper, we focus on one particular aspect of heterogeneity: learning from offline data collected at different control frequencies. Across labs, the discretization of controllers, sampling rates of sensors, and demands of a task of interest may differ, giving rise to a mixture of frequencies in an aggregated dataset. We study how well offline reinforcement learning (RL) algorithms can accommodate data with a mixture of frequencies during training. We observe that the $Q$-value propagates at different rates for different discretizations, leading to a number of learning challenges for off-the-shelf offline RL. We present a simple yet effective solution that enforces consistency in the rate of $Q$-value updates to stabilize learning. By scaling the value of $N$ in $N$-step returns with the discretization size, we effectively balance $Q$-value propagation, leading to more stable convergence. On three simulated robotic control problems, we empirically find that this simple approach outperforms na\"ive mixing by 50% on average.
Keyword: calibration
Lumen Shape Reconstruction using a Soft Robotic Balloon Catheter and Electrical Impedance Tomography
Authors: James Avery, Mark Runciman, Cristina Fiani, Elena Monfort Sanchez, Saina Akhond, Zhuang Liu, Kirill Aristovich, George Mylonas
Abstract
Incorrectly sized balloon catheters can lead to increased post-surgical complications, yet even with preoperative imaging, correct selection remains a challenge. With limited feedback during surgery, it is difficult to verify correct deployment. We propose the use of integrated impedance measurements and Electrical Impedance Tomography (EIT) imaging to assess the deformation of the balloon and determine the size and shape of the surrounding lumen. Previous work using single impedance measurements, or pressure data and analytical models, whilst demonstrating high sizing accuracy, have assumed a circular cross section. Here we extend these methods by adding a multitude of electrodes to detect elliptical and occluded lumen and obtain EIT images to localise deformations. Using a 14 Fr (5.3 mm) catheter as an example, numerical simulations were performed to find the optimal electrode configuration of two rings of 8 electrodes spaced 10 mm apart. The simulations predicted that the maximum detectable aspect ratio decreased from 0.9 for a 14mm balloon to 0.5 at 30mm. The sizing and ellipticity detection results were verified experimentally. A prototype robotic balloon catheter was constructed to automatically inflate a compliant balloon while simultaneously recording EIT and pressure data. Data were collected in experiments replicating stenotic vessels with an elliptical and asymmetrical profile, and the widening of a lumen during angioplasty. After calibration, the system was able to correctly localise the occlusion and detect aspect ratios of 0.75. EIT images further localised the occlusion and visualised the dilation of the lumen during balloon inflation.
Exploring the Design of Adaptation Protocols for Improved Generalization and Machine Learning Safety
Authors: Puja Trivedi, Danai Koutra, Jayaraman J. Thiagarajan
Abstract
While directly fine-tuning (FT) large-scale, pretrained models on task-specific data is well-known to induce strong in-distribution task performance, recent works have demonstrated that different adaptation protocols, such as linear probing (LP) prior to FT, can improve out-of-distribution generalization. However, the design space of such adaptation protocols remains under-explored and the evaluation of such protocols has primarily focused on distribution shifts. Therefore, in this work, we evaluate common adaptation protocols across distributions shifts and machine learning safety metrics (e.g., anomaly detection, calibration, robustness to corruptions). We find that protocols induce disparate trade-offs that were not apparent from prior evaluation. Further, we demonstrate that appropriate pairing of data augmentation and protocol can substantially mitigate this trade-off. Finally, we hypothesize and empirically see that using hardness-promoting augmentations during LP and then FT with augmentations may be particularly effective for trade-off mitigation.
A Reliable Online Method for Joint Estimation of Focal Length and Camera Rotation
Authors: Yiming Qian, James H. Elder
Subjects: Computer Vision and Pattern Recognition (cs.CV)
Abstract
Linear perspectivecues deriving from regularities of the built environment can be used to recalibrate both intrinsic and extrinsic camera parameters online, but these estimates can be unreliable due to irregularities in the scene, uncertainties in line segment estimation and background clutter. Here we address this challenge through four initiatives. First, we use the PanoContext panoramic image dataset [27] to curate a novel and realistic dataset of planar projections over a broad range of scenes, focal lengths and camera poses. Second, we use this novel dataset and the YorkUrbanDB [4] to systematically evaluate the linear perspective deviation measures frequently found in the literature and show that the choice of deviation measure and likelihood model has a huge impact on reliability. Third, we use these findings to create a novel system for online camera calibration we call fR, and show that it outperforms the prior state of the art, substantially reducing error in estimated camera rotation and focal length. Our fourth contribution is a novel and efficient approach to estimating uncertainty that can dramatically improve online reliability for performance-critical applications by strategically selecting which frames to use for recalibration.
Keyword: out of distribution detection
There is no result
Keyword: out-of-distribution detection
There is no result
Keyword: expected calibration error
There is no result
Keyword: overconfident
There is no result
Keyword: overconfidence
There is no result
Keyword: confidence
Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions
$p$-DkNN: Out-of-Distribution Detection Through Statistical Testing of Deep Representations
Teaching Interaction using State Diagrams
XInsight: eXplainable Data Analysis Through The Lens of Causality
"I Used To Carry A Wallet, Now I Just Need To Carry My Phone": Understanding Current Banking Practices and Challenges Among Older Adults in China
Keyword: scaling
Inter-Frame Compression for Dynamic Point Cloud Geometry Coding
Quiver neural networks
Reconciling Security and Communication Efficiency in Federated Learning
Offline Reinforcement Learning at Multiple Frequencies
Keyword: calibration
Lumen Shape Reconstruction using a Soft Robotic Balloon Catheter and Electrical Impedance Tomography
Exploring the Design of Adaptation Protocols for Improved Generalization and Machine Learning Safety
A Reliable Online Method for Joint Estimation of Focal Length and Camera Rotation