summaries: The paper's motivation is based on protecting private data and preventing its being scraped and used to train models. Even though motivation is clear and very important, the problem is the same as the works in crafting adversarial samples (i.e., the ones under data poisoning and adversarial attacks parts of the related work). The key difference is to apply Projected Gradient Descent (Mandry et al. 2018) in the reverse direction iteratively to *minimize* the loss function.  Furthermore, the performance evaluation will be the margin between models trained on completely clean data and sample-wise/class-wise adversarially corrupted data (in contrast to fooling a pretrained network in adversarial attack benchmarks).

summaries: The authors proposed the idea of using invisible noise to make personal data unusable to authorized deep learning models. To achieve this goal, the authors proposed the idea of error-minimizing noise crafted by a min-min optimization method. The error-minimizing noise is then added to training examples to make them unlearnable to deep learning models. The idea is very well motivated and explained. The experiments not only confirm the exceptional effectiveness of the proposed method but also show its flexibility.

summaries: The authors studied the problem of data protection from a new perspective. They proposed one kind of error-minimizing noise to make the data (added noise) unlearnable. The noise is imperceptible to human eyes, and thus does not affect normal data utility. The idea is very interesting and inspiring. The authors conducted a series of solid experiments to validate the effectiveness of the proposed noise, and tested it on a real world task of face recognition.

abstractText: The volume of “free” data on the internet has been key to the current success of deep learning. However, it also raises privacy concerns about the unauthorized exploitation of personal data for training commercial models. It is thus crucial to develop methods to prevent unauthorized data exploitation. This paper raises the question: can data be made unlearnable for deep learning models? We present a type of error-minimizing noise that can indeed make training examples unlearnable. Error-minimizing noise is intentionally generated to reduce the error of one or more of the training example(s) close to zero, which can trick the model into believing there is “nothing” to learn from these example(s). The noise is restricted to be imperceptible to human eyes, and thus does not affect normal data utility. We empirically verify the effectiveness of error-minimizing noise in both sample-wise and class-wise forms. We also demonstrate its flexibility under extensive experimental settings and practicability in a case study of face recognition. Our work establishes an important first step towards making personal data unexploitable to deep learning models. Code is available at https://github.com/HanxunH/Unlearnable-Examples.

authors:
Martin Abadi
Andy Chu
Ian Goodfellow
H Brendan McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep learning with differential privacy

venue: SIGSAC,

authors:
Yang Bai
Yuyuan Zeng
Yong Jiang
Yisen Wang
Shu-Tao Xia
Weiwei Guo

title: Improving query efficiency of black-box adversarial attack

venue: In ECCV,

authors:
Mauro Barni
Kassem Kallas
Benedetta Tondi

title: A new backdoor attack in cnns by training set corruption without label poisoning

venue: In ICIP

authors:
Battista Biggio
Blaine Nelson
Pavel Laskov

title: Poisoning attacks against support vector machines

venue: arXiv preprint arXiv:1206.6389,

authors:
Nicholas Carlini
David Wagner

title: Towards evaluating the robustness of neural networks

venue: In SP,

authors:
Xinyun Chen
Chang Liu
Bo Li
Kimberly Lu
Dawn Song

title: Targeted backdoor attacks on deep learning systems using data poisoning

venue: arXiv preprint arXiv:1712.05526,

authors:
Francesco Croce
Matthias Hein

title: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks

venue: In ICML,

authors:
Jiankang Deng
Jia Guo
Niannan Xue
Stefanos Zafeiriou

title: Arcface: Additive angular margin loss for deep face recognition

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Terrance DeVries
Graham W Taylor

title: Improved regularization of convolutional neural networks with cutout

venue: arXiv preprint arXiv:1708.04552,

authors:
Ranjie Duan
Xingjun Ma
Yisen Wang
James Bailey
A Kai Qin
Yun Yang

title: Adversarial camouflage: Hiding physical-world attacks with natural styles

authors:
Alhussein Fawzi
Seyed-Mohsen Moosavi-Dezfooli
Pascal Frossard

title: Robustness of classifiers: from adversarial to random noise

venue: In NeurIPS,

authors:
Ian J Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

title: The secretive company that might end privacy as we know it, 2020

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Gary B Huang
Marwan Mattar
Tamara Berg
Eric Learned-Miller

title: Labeled faces in the wild: A database forstudying face recognition in unconstrained environments

authors:
Andrew Ilyas
Shibani Santurkar
Dimitris Tsipras
Logan Engstrom
Brandon Tran
Aleksander Madry

title: Adversarial examples are not bugs, they are features

venue: NeurIPS,

authors:
Linxi Jiang
Xingjun Ma
Shaoxiang Chen
James Bailey
Yu-Gang Jiang

title: Black-box adversarial attacks on video recognition models

venue: In ACMMM,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In ICLR,

authors:
Pang Wei Koh
Percy Liang

title: Understanding black-box predictions via influence functions

title: Learning multiple layers of features from tiny images

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial examples in the physical world

venue: arXiv preprint arXiv:1607.02533,

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Yunfei Liu
Xingjun Ma
James Bailey
Feng Lu

title: Reflection backdoor: A natural backdoor attack on deep neural networks

authors:
Ziwei Liu
Ping Luo
Xiaogang Wang
Xiaoou Tang

venue: In ICCV,

authors:
Ilya Loshchilov
Frank Hutter

title: SGDR: stochastic gradient descent with warm restarts

authors:
Xingjun Ma
Bo Li
Yisen Wang
Sarah M Erfani
Sudanthi Wijewickrema
Grant Schoenebeck
Dawn Song
Michael E Houle
James Bailey

title: Characterizing adversarial subspaces using local intrinsic dimensionality

authors:
Xingjun Ma
Yuhao Niu
Lin Gu
Yisen Wang
Yitian Zhao
James Bailey
Feng Lu

title: Understanding adversarial attacks on deep learning based medical image analysis systems

venue: Pattern Recognition,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Omar Fawzi
Pascal Frossard

title: Universal adversarial perturbations

venue: In CVPR,

authors:
Luis Muñoz-González
Battista Biggio
Ambra Demontis
Andrea Paudice
Vasin Wongrassamee
Emil C Lupu
Fabio Roli

title: Towards poisoning of deep learning algorithms with back-gradient optimization

venue: AISec,

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

authors:
NhatHai Phan
Yue Wang
Xintao Wu
Dejing Dou

title: Differential privacy preservation for deep auto-encoders: an application of human behavior prediction

venue: In AAAI,

authors:
NhatHai Phan
Xintao Wu
Han Hu
Dejing Dou

title: Adaptive laplace mechanism: Differential privacy preservation in deep learning

venue: In ICDM,

authors:
Vinay Uday Prabhu
Abeba Birhane

title: Large image datasets: A pyrrhic win for computer vision

venue: arXiv preprint arXiv:2006.16923,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein
Alexander C. Berg
Li Fei-Fei

title: ImageNet Large Scale Visual Recognition Challenge

venue: International Journal of Computer Vision,

authors:
Ali Shafahi
W Ronny Huang
Mahyar Najibi
Octavian Suciu
Christoph Studer
Tudor Dumitras
Tom Goldstein

title: Poison frogs! targeted clean-label poisoning attacks on neural networks

authors:
Shawn Shan
Emily Wenger
Jiayun Zhang
Huiying Li
Haitao Zheng
Ben Y Zhao

title: Fawkes: Protecting personal privacy against unauthorized deep learning models

venue: USENIX-Security,

authors:
Reza Shokri
Vitaly Shmatikov

title: Privacy-preserving deep learning

venue: In SIGSAC,

authors:
Reza Shokri
Marco Stronati
Congzheng Song
Vitaly Shmatikov

title: Membership inference attacks against machine learning models

authors:
Karen Simonyan
Andrew Zisserman

venue: arXiv preprint arXiv:1409.1556,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199,

authors:
Christian Szegedy
Sergey Ioffe
Vincent Vanhoucke
Alex Alemi

title: Inception-v4, inception-resnet and the impact of residual connections on learning

venue: arXiv preprint arXiv:1602.07261,

authors:
Yaniv Taigman
Ming Yang
Marc’Aurelio Ranzato
Lior Wolf

title: Deepface: Closing the gap to human-level performance in face verification

authors:
Haohan Wang
Xindi Wu
Zeyi Huang
Eric P Xing

title: High-frequency component helps explain the generalization of convolutional neural networks

authors:
Xin Wang
Jie Ren
Shuyun Lin
Xiangming Zhu
Yisen Wang
Quanshi Zhang

title: A unified approach to interpreting and boosting adversarial transferability

venue: arXiv preprint arXiv:2010.04055,

authors:
Yisen Wang
Xingjun Ma
James Bailey
Jinfeng Yi
Bowen Zhou
Quanquan Gu

title: On the convergence and robustness of adversarial training

authors:
Yisen Wang
Difan Zou
Jinfeng Yi
James Bailey
Xingjun Ma
Quanquan Gu

title: Improving adversarial robustness requires revisiting misclassified examples

authors:
Dongxian Wu
Yisen Wang
Shu-Tao Xia
James Bailey
Xingjun Ma

title: Skip connections matter: On the transferability of adversarial examples generated with resnets

authors:
Dongxian Wu
Shu-Tao Xia
Yisen Wang

title: Adversarial weight perturbation helps robust generalization

authors:
Chaofei Yang
Qing Wu
Hai Li
Yiran Chen

title: Generative poisoning attack method against neural networks

venue: arXiv preprint arXiv:1703.01340,

authors:
Dong Yi
Zhen Lei
Shengcai Liao
Stan Z Li

title: Learning face representation from scratch

venue: arXiv preprint arXiv:1411.7923,

authors:
Sangdoo Yun
Dongyoon Han
Seong Joon Oh
Sanghyuk Chun
Junsuk Choe
Youngjoon Yoo

title: Cutmix: Regularization strategy to train strong classifiers with localizable features

authors:
Hongyang Zhang
Yaodong Yu
Jiantao Jiao
Eric Xing
Laurent El Ghaoui
Michael Jordan

title: Theoretically principled trade-off between robustness and accuracy

authors:
Hongyi Zhang
Moustapha Cisse
Yann N Dauphin
David Lopez-Paz

title: mixup: Beyond empirical risk minimization

authors:
Sheng Zhang
Xiaodong Liu
Jingjing Liu
Jianfeng Gao
Kevin Duh
Benjamin Van Durme

title: Record: Bridging the gap between human and machine commonsense reading comprehension

venue: arXiv preprint arXiv:1810.12885,

authors:
Shihao Zhao
Xingjun Ma
Xiang Zheng
James Bailey
Jingjing Chen
Yu-Gang Jiang

title: Cleanlabel backdoor attacks on video recognition models

title: 2020). I DIFFERENT GENERALIZATION METHODS FOR ERROR-MINIMIZATION NOISE The proposed error-minimizing noise is generated using PGD. Specifically, PGD is applied to solve the inner minimization problem in Equation 2. Since it is a typical constrained optimization problem, it can also be solved by other optimization (attack) methods such as FGSM

venue: (Goodfellow et al.,

authors:
L-BFGS (Szegedy et al
W (Carlini
Wagner

venue: In (Szegedy et al.,

authors:
Adam (Kingma
Ba

heading: 1 INTRODUCTION

text:
In recent years, deep learning has had groundbreaking successes in several fields, such as computer vision (He et al., 2016) and natural language processing (Devlin et al., 2018). This is partly attributed to the availability of large-scale datasets crawled freely from the Internet such as ImageNet (Russakovsky et al., 2015) and ReCoRD (Zhang et al., 2018b). Whilst these datasets provide a playground for developing deep learning models, a concerning fact is that some datasets were collected without mutual consent (Prabhu & Birhane, 2020). Personal data has also been unconsciously collected from the Internet and used for training commercial models (Hill, 2020). This has raised public concerns about the “free” exploration of personal data for unauthorized or even illegal purposes.
In this paper, we address this concern by introducing unlearnable examples, which aims at making training examples unusable for Deep Neural Networks (DNNs). In other words, DNNs trained on unlearnable examples will have a performance equivalent to random guessing on normal test examples. Compared with preserving an individual’s privacy by obfuscating information from the dataset, what we aim to achieve here is different but more challenging. First, making an example unlearnable should not affect its quality for normal usage. For instance, an unlearnable “selfie” photo should be free from obvious visual defects so it can be used as a social profile picture. Ideally, this can be achieved by using imperceptible noise. In our setting, the noise can only be added to training examples on a single occasion (when the data is uploaded to the internet) prior to model training. However, DNNs are known to be robust to small noise either random (Fawzi et al., 2016) or adversarial (Szegedy et al., 2013; Goodfellow et al., 2014; Ma et al., 2018). It is still not clear whether small, imperceptible noise can stop the training of high-performance DNNs.
The development of unlearnable examples should take full advantage of the unique characteristics, and more importantly, the weaknesses of DNNs. One well-studied characteristic of DNNs is that they tend to capture more of the high-frequency components of the data (Wang et al., 2020a). Surprisingly, by exploiting this characteristic, we find that small random noise when applied in a class-wise †Correspondence to: Xingjun Ma (daniel.ma@deakin.edu.au), Yisen Wang (yisen.wang@pku.edu.cn)
manner to the training data can easily fool DNNs to overfit to such noise (shown in Section 4). However, early stopping can effectively counteract this type of noise. DNNs are also known to be vulnerable to adversarial (or error-maximizing) noise, which are small perturbations crafted to maximize the model’s error at the test time (Szegedy et al., 2013; Goodfellow et al., 2014). We find that error-maximizing noise cannot stop DNN learning when applied in a sample-wise manner to the training examples. This motivates us to explore the opposite direction to error-maximizing noise. Specifically, we propose a type of error-minimizing noise that can prevent the model from being penalized by the objective function during training, and thus can trick the model into believing there is “nothing” to learn from the example(s). We refer to an example that contains the errorminimizing noise as an unlearnable example. Error-minimizing noise can be generated in different forms: sample-wise and class-wise. Class-wise error-minimizing noise is superior to random noise and cannot be circumvented by early stopping. Sample-wise error-minimizing noise is the only effective noise that can make training examples unlearnable compared to random (Fawzi et al., 2016) or error-maximizing noise (Muñoz-González et al., 2017). Our main contributions are:
• We present a type of error-minimizing noise that can create unlearnable examples to prevent personal data from being freely exploited by deep learning models. The noise is small, imperceptible to human eyes, thus it does not reduce general data utility. • We propose a bi-level optimization process to effectively generate different forms of error-
minimizing noise: sample-wise and class-wise. • We empirically verify the effectiveness and flexibility of error-minimizing noise for cre-
ating unlearnable examples. We also demonstrate the practical application of unlearnable examples in real-world scenarios via a case study on face recognition.

heading: 2 RELATED WORK

text:
In this section, we briefly review most relevant works in data privacy, data poisoning, adversarial attacks against deep learning models.
Data Privacy. Privacy issues have been extensively studied in the field of privacy-preserving machine learning (Shokri & Shmatikov, 2015; Abadi et al., 2016; Phan et al., 2016; 2017; Shokri et al., 2017). While these works have made significant progress towards protecting data privacy, they are developed based on the assumption that the model can freely explore the training data and turn to protect the model from leaking sensitive information about the training data. In this paper, we consider a more challenging scenario where the goal of the defender is to make personal data completely unusable by unauthorized deep learning models. Fawkes (Shan et al., 2020) has made the first attempt towards this type of strict situation. By leveraging the targeted adversarial attack, Fawkes prevents unauthorized face tracker from tracking a person’s identity. This work is similar to ours as we share a common objective that prevents unauthorized data usage. In contrast to the targeted adversarial attack, we propose a novel error-minimizing noise to produce unlearnable examples which can be used as a generic framework for a wide range of data protection tasks.
Data Poisoning. Data poisoning attacks aim to degrade the model’s performance on clean examples by modifying the training examples. Previous work has demonstrated a poisoning attack on SVM (Biggio et al., 2012). Koh & Liang (2017) proposed to poison the most influential training examples using adversarial (error-maximizing) noise against DNNs, which has also been integrated into an endto-end framework (Muñoz-González et al., 2017). Although data poisoning attacks can potentially prevent free data exploitation, these approaches are quite limited against DNNs and hard to operate in real-world scenarios. For example, poisoned examples can only slightly decrease DNNs’ performance (Muñoz-González et al., 2017), and often appear distinguishable to clean examples (Yang et al., 2017) which will reduce normal data utility. The backdoor attack is another type of attack that poisons training data with a stealthy trigger pattern (Chen et al., 2017; Liu et al., 2020). However, the backdoor attack does not harm the model’s performance on clean data (Chen et al., 2017; Shafahi et al., 2018; Barni et al., 2019; Liu et al., 2020; Zhao et al., 2020). Thus, it is not a valid method for data protection. Different from these works, we generate unlearnable examples with invisible noise to “bypass” the training of DNNs.
Adversarial Attack. It has been found that adversarial examples (or attacks) can fool DNNs at the test time (Szegedy et al., 2013; Goodfellow et al., 2014; Kurakin et al., 2016; Carlini & Wagner, 2017; Madry et al., 2018; Jiang et al., 2019; Wu et al., 2020a; Bai et al., 2020; Croce & Hein, 2020; Wang
et al., 2020b; Duan et al., 2020; Ma et al., 2020). The adversary finds an error-maximizing noise that maximizes the model’s prediction error, and the noise can be crafted universally for the entire test set (Moosavi-Dezfooli et al., 2017). Adversarial training has been shown to be the most robust training strategy against error-maximizing noise (Madry et al., 2018; Zhang et al., 2019; Wang et al., 2019; Wu et al., 2020b; Wang et al., 2020c). Adversarial training can be formulated as a min-max optimization problem. In this paper, we explore the opposite direction of error-maximizing noise, i.e., finding small noise that minimizes the model’s error via a min-min optimization process.

heading: 3 UNLEARNABLE EXAMPLES AND ERROR-MINIMIZING NOISE

heading: 3.1 PROBLEM STATEMENT

text:
Assumptions on Defender’s Capability. We assume the defender has full access to the portion of data which they want to make unlearnable. However, the defender cannot interfere with the training process and does not have access to the full training dataset. In other words, the defender can only transform their portion of data into unlearnable examples. Moreover, the defender cannot further modify their data once the unlearnable examples are created.
Objectives. We formulate the problem in the context of image classification with DNNs. Given a typical K-class classification task, we denote the clean training and test datasets as Dc and Dt respectively, and the classification DNN trained on Dc as fθ where θ are the parameters of the network∗. Our goal is to transform the training data Dc into unlearnable dataset Du such that DNNs trained on the Du will perform poorly on the test set Dt. Suppose the clean training dataset consists of n clean examples, that is, Dc = {(xi, yi)}ni=1 with x ∈ X ⊂ Rd are the inputs and y ∈ Y = {1, · · · ,K} are the labels and K is the total number of classes. We denote its unlearnable version by Du = {(x′i, yi)}ni=1, where x′ = x + δ is the unlearnable version of training example x ∈ Dc and δ ∈ ∆ ⊂ Rd is the “invisible” noise that makes x unlearnable. The noise δ is bounded by ‖δ‖p ≤ with ‖ · ‖p is the Lp norm, and is set to be small such that it does not affect the normal utility of the example.
In the typical case, the DNN model will be trained onDc to learn the mapping from the input space to the label space: f : X → Y . Our goal is to trick the model into learning a strong correlation between the noise and the labels: f : ∆→ Y,∆ 6= X , when trained on Du:
arg min θ
E(x′,y)∼DuL(f(x ′), y) (1)
where, L is the classification loss such as the commonly used cross entropy loss. Noise Form. We propose two forms of noise: sample-wise and class-wise. For sample-wise noise, x′i = xi + δi, δi ∈ ∆s = {δ1, · · · , δn}, while for class-wise noise, x′i = xi + δyi , δyi ∈ ∆c = {δ1, · · · , δK}. Sample-wise noise needs to generate noise separately for each example. This may have more limited practicality. In contrast to sample-wise noise, a class of examples can be made unlearnable by the addition of class-wise noise, where all examples in the same class have the same noise added. As such, class-wise noise can be generated more efficiently and more flexibly in practical usage. However, we will see that class-wise noise may get more easily exposed.

heading: 3.2 GENERATING ERROR-MINIMIZING NOISE

text:
Ideally, the noise should be generated on an additional dataset that is different from Dc. This will involve a class-matching process to find the most appropriate class from the additional dataset for each class to protect in Dc. For simplicity, here we define the noise generation process on Dc and will verify the effectiveness of using an additional dataset in the experiments. Given a clean example x, we propose to generate the error-minimizing noise δ for training input x by solving the following bi-level optimization problem:
arg min θ E(x,y)∼Dc [ min δ L(f ′(x+ δ), y) ] s.t. ‖δ‖p ≤ (2)
where, f ′ denotes the source model used for noise generation. Note that this is a min-min bi-level optimization problem: the inner minimization is a constrained optimization problem that finds the ∗We omit the θ notation from fθ without ambiguity in the rest of this paper.
Lp-norm bounded noise δ that minimizes the model’s classification loss, while the outer minimization problem finds the parameters θ that also minimize the model’s classification loss.
Note that the above bi-level optimization has two components that optimize the same objective. In order to find effective noise δ and unlearnable examples, the optimization steps for θ should be limited, compared to standard or adversarial training. Specifically, we optimize δ over Dc after every M steps of optimization of θ. The entire bi-level optimization process is terminated once the error rate is lower than λ. The detailed training pipeline is described in Algorithm 1 in the Appendix.
Sample-wise Generation. We adopt the first-order optimization method PGD (Madry et al., 2018) to solve the constrained inner minimization problem as follows:
x′t+1 = Π ( x′t − α · sign(∇xL(f ′(x′t), y)) ) (3)
where, t is the current perturbation step (T steps in total), ∇xL(f(x′t), y) is the gradient of the loss with respect to the input, Π is a projection function that clips the noise back to the -ball around the original example x when it goes beyond, and α is the step size. The perturbation is iteratively applied for T steps after each M step of model training as we explained earlier. The final output is a unlearnable example x′ and the generated error-minimizing noise is δ = x′ − x. Class-wise Generation. Class-wise noise ∆c can be obtained by a cumulative perturbation on all examples in a given class. For each example in class k at step t, it applies δk to the original example x and follows Equation 3 to produce x′t+1. The δk accumulates over every example for the corresponding class k in the entire bi-level optimization process.

heading: 4 EXPERIMENTS

text:
In this section, we first demonstrate the effectiveness in creating unlearnable examples using random noise, error-maximizing noise and our proposed error-minimizing noise in both sample-wise and class-wise forms. We further empirically verify the effectiveness of error-minimizing noise on 4 benchmark image datasets. We then conduct a set of stability and transferability analyses of the noise. Finally, we show effectiveness in real-world scenarios via a case study on face recognition. More analyses regarding the effectiveness of error-minimizing noise on small patches or a mixture of class-wise noise can be found in Appendix F.
According to previous studies in adversarial research, small L∞-bounded noise within ‖δ‖∞ < = 8/255 on images are imperceptible to human observers. We consider the same constraint for all types and forms of the noise in our experiments, unless otherwise explicitly stated.
Experimental Setting for Error-Minimizing Noise. We apply error-minimizing noise to the training set of 4 commonly used image datasets: SVHN (Netzer et al., 2011), CIFAR-10, CIFAR-100 (Krizhevsky, 2009), and ImageNet subset (the first 100 classes) (Russakovsky et al., 2015). The experiments on the ImageNet subset are to confirm the effectiveness of high-resolution images. For all experiments, the ResNet-18 (RN-18) (He et al., 2016) is used as the source model f ′ to generate the noise. We use 20% of the training dataset to generate the class-wise noise and the entire training dataset for the sample-wise noise except for ImageNet †. We transform the entire training dataset into the unlearnable datasets for experiments in section 4.1 and section 4.2. Different percentages of unlearnable examples are used for experiments in section 4.3. We train four different DNNs on the unlearnable training sets: VGG-11 (Simonyan & Zisserman, 2014), ResNet-18 (RN-18), ResNet-50 (RN-50) and DenseNet-121 (DN-121) (Huang et al., 2017). We also use clean training sets as a comparison. Detailed training configurations settings can be found in Appendix B. We evaluate the effectiveness of unlearnable examples by examining the model’s accuracy on clean test examples, i.e., the lower the clean test accuracy the better the effectiveness.
Experimental Setting for Random and Error-Maximizing Noise. For random noise, we randomly sample the noise from [− , ] independently for each training example (eg. sample-wise) or each class (eg. class-wise). For error-maximizing (adversarial) noise, we generate the noise using PGD-20 attack (Madry et al., 2018) using a pre-trained ResNet-18 model on the training set. We generate sample-wise error-maximizing noise for each training example, and the class-wise noise based on 20% of the training set following the universal attack procedure in (Moosavi-Dezfooli et al., 2017).
†We use 20% of the first 100 class subset as the entire training set (due to the efficiency)
Both the random and error-maximizing noise are applied to the same amount of training examples as our error-minimizing noise.

heading: 4.1 COMPARISONS OF RANDOM, ERROR-MAXIMIZING AND ERROR-MINIMIZING NOISE

text:
First, we examine an extreme case that applies different types of noise to the entire training set. Figure 1 illustrates the effectiveness of both sample-wise and class-wise noise. In the sample-wise case, the network is robust to random or error-maximizing noise. This is understandable since DNNs are known to be robust to small random (Fawzi et al., 2016) and error-maximizing noise (Muñoz-González et al., 2017; Madry et al., 2018; Wang et al., 2019). Surprisingly, when applied in a class-wise manner, both types of noise can prevent the network from learning useful information from the data, especially after the 15-th epoch. This reveals that DNNs are remarkably vulnerable to class-wise noise. While effective in the middle and later training stages, class-wise random noise can still be circumvented by early stopping (eg. at epoch 15). This is also the case for error-maximizing noise, although not as easy as random noise since the highest clean test accuracy under error-maximizing noise is only 50%. From the perspective of making data unexploitable, both random and error-maximizing noise are only partially effective. In comparison, our error-minimizing noise is more flexible. As shown in Figure 1, the error-minimizing noise can reduce the model’s clean test accuracy to below 23% in both settings. Moreover, it remains effective across the entire training process.
The class-wise and sample-wise noises work in different ways. Class-wise noise has an explicit correlation with the label. Learning such correlation can effectively reduce the training error. Consequently, when there is class-wise noise, the model is tricked to learn the noise rather than the real content, reducing its generalization performance on clean data. The existence of class-wise noise only in the training data also breaks the i.i.d. assumption between the training and test data distribution. This also indicates that noises that can break the i.i.d. assumption might be effective techniques for data protection. However, in the sample-wise case, every sample has a different noise, and there is no explicit correlation between the noise and the label. In this case, only low-error samples can be ignored by the model, and normal and high-error examples have more positive impact on model learning than low-error examples. This makes error-minimizing noise more generic and effective in making data unlearnable.

heading: 4.2 EFFECTIVENESS OF ERROR-MINIMIZING NOISE ON DIFFERENT DATASETS

text: Table 1 reports the effectiveness of both the sample-wise (eg. ∆s) and the class-wise (eg. ∆c) errorminimizing noise on datasets SVHN, CIFAR-10, CIFAR-100 and ImageNet subset. As shown in the table, our proposed method can reliably create unlearnable examples in both forms on all 4 datasets with images of different resolutions. Moreover, the noise generated on RN-18 works remarkably well to protect the data from other types of models. Compared to sample-wise noise, class-wise noise is particularly more effective, which can reduce the model’s performance to a level that is close to random guessing. These results clearly show that error-minimizing noise is a promising technique for preventing unauthorized data exploration.

heading: 4.3 STABILITY ANALYSIS

text:
We run a set of experiments to analyze the stability of error-minimizing noise in creating unlearnable examples, and answer two key questions regarding its practical usage: 1) Is the noise still effective if only applied to a certain proportion or class of the data? and 2) Can the noise be removed by data augmentation or adversarial training? Experiments are conducted on CIFAR-10 with RN-18.
Different Unlearnable Percentages. In practical scenarios, it is very likely that not all the training data need to be made unlearnable. For example, only a certain number of web users have decided to use this technique but not all users, or only a specific class of medical data should be kept unexploited. This motivates us to examine the effectiveness of error-minimizing noise when applied only on a proportion of randomly selected training examples. In other words, we make a certain percentage of the training data unlearnable while keeping the rest of the data clean. We train the model on this partially unlearnable and partially clean training set Du +Dc. As a comparison, we also train the model on only the clean proportion, which is denoted by Dc. A quick glance at the Du +Dc results in Table 2 tells us that the effectiveness drops quickly when the data are not made 100% unlearnable. This is the case for both sample-wise and class-wise noise. The unlearnable effect is almost negligible even when the noise is applied to 40% of the data. Such a limitation against DNNs has also been identified in previous work for protecting face images using error-maximizing noise (Shan et al., 2020).
To better understand the above limitation, we take 80% as an example and plot the learning curves of the RN-18 model trained on 1) only the 20% clean proportion, 2) only the 80% unlearnable proportion, or 3) both. The results are shown in Figure 2 (a-b). Interestingly, we find that the 80% data with the error-minimizing noise are still unlearnable to the model, whereas the rest of the 20% clean data are sufficient for the model to achieve a good performance. In other words, models trained only on Dc demonstrate a similar performance as models trained on Du +Dc. This phenomenon is consistent across different unlearnable percentages. This indicates that the high performance of the model on < 100% unlearnable dataset may not be a failure of the error-minimizing noise. We further verify this by investigating the scenario where only one class is made unlearnable.
One Single Unlearnable Class. We take the ‘bird’ class of CIFAR-10 as an example, and apply the error-minimizing noise (either sample-wise or class-wise) to all training images in the bird class. We train RN-18 on each of the unlearnable training set, and plot the prediction confusion matrix of the model on the clean test set in Figure 2 (c-d). The ‘bird’ class is indeed unlearnable when either the sample-wise or the class-wise error-minimizing noise is added to the class. Compared to sample-wise noise, class-wise noise is more effective with almost all the test ‘bird’ images being misclassified into other classes. Interestingly, this customized unlearnable class does not seem to influence much of the learning on other classes. Only the images from the unlearnable class are incorrectly predicted into other classes, not the other way around. This not only confirms that the unlearnable group of data
is indeed unlearnable to the model and it suggests that our error-minimizing noise can be flexibly applied to suit different protection tasks. A similar result can also be demonstrated on more than one unlearnable class (see Appendix C). In summary, if an individual can only apply the noise to portion of his/her data, these data will not contribute to model training. If an individual can apply the noise to all his/her data, the model will fail to recognize this particular class of data. In other words, our method is effective for the defender to protect his/her own data.
Under Noise Filtering Techniques. The resistance of our error-minimizing noise to 4 types of data augmentation techniques and adversarial training is analyzed in Appendix D. The noise is fairly robust to all 4 data augmentation techniques, and the highest accuracy that can achieve using data augmentation is 58.51% on CIFAR-10. Comparing with data augmentation, the error-minimizing noise is less resistant to adversarial training. With slightly increased on CIFAR-10, the noise can only compromise the model’s clean test accuracy to 79%. Since adversarial training forces the model to learn only robust features (Ilyas et al., 2019), we believe our method can be improved by crafting the noise based on the robust features, which can be extracted from an adversarially pre-trained model on the clean data (Ilyas et al., 2019). We leave further explorations of these techniques as future work.

heading: 4.4 TRANSFERABILITY ANALYSIS

text:
Another important question we haven’t explored so far is that Can error-minimizing noise be generated on a different dataset? This is also important as a positive answer to the question increases the practicability of using unlearnable examples to protect millions of web users. We examine this capability for both sample-wise noise and class-wise error-minimizing noise.
Sample-wise Noise. For ∆s, we generate the noise and create unlearnable ‘ship’ class examples on CIFAR-10 and add the unlearnable ‘ship’ class to CIFAR-100. For testing, we also include the clean test set of ‘ship’ class to the test set of CIFAR-100. Note the main difference of this experiment to the previous singe unlearnable class experiment is the unlearnable examples are generated on a different dataset. The class-wise and the overall accuracy on the clean test set are shown in Figure 3a. We
find that the ‘ship’ class is indeed unlearnable to the model at the end, despite a small amount (60% clean test accuracy) of information being learned in the early stage. We suspect this is because the ‘ship’ class shares some common features with other classes in CIFAR-100. Overall, the generated unlearnable examples can transfer to a different dataset. Note that this experiment simulates the scenario where a user uses a different dataset (eg. CIFAR-10) to generate the sample-wise noise to make his/her personal images unlearnable before uploading them to the Internet, and these images are then collected into a large CIFAR-100 dataset.
Class-wise Noise. For ∆c, we use the entire ImageNet as the source dataset to generate the noise using RN-18, then apply the noise to CIFAR-10. All ImageNet images are resized to 32×32. For each CIFAR-10 class, we determine its corresponding class in ImageNet based on the visual similarities between the classes. The detailed class mapping can be found in Table 4 in the Appendix. We train RN-18, RN-50 and DN-121 on the unlearnable CIFAR-10 created with the ImageNet transferred noise, and show their learning curves in Figure 3b. As can be observed, the transferred class-wise noise works reasonably well on CIFAR-10 with the clean test accuracy of all three models being reduced to around 10%. Compared to the noise directly generated on CIFAR-10 (see Figure 1), here the models can still capture some useful features in the first epoch. We conjecture this is because CIFAR-10 classes are more generic than ImageNet classes, and noise that minimizes the error of fine-grained classes can become less effective on generic classes. We also conduct an experiment on the ImageNet transferred noise to make 4 classes unlearnable of CIFAR-10. We plot the prediction confusion matrix of the RN-18 trained on the 4-class unlearnable CIFAR-10 in Figure 3c. It shows that the 4 classes are indeed unlearnable, and the model’s performance on the other 6 classes is not affected. This confirms that transferred noise can also be used in customized scenarios.

heading: 4.5 REAL-WORLD SCENARIO: A CASE STUDY ON FACE RECOGNITION

text:
Here, we conduct a case study to apply error-minimizing noise to personal face images, which is arguably one most important real-world scenarios. In this scenario, the defender wants to prevent his/her face images from being exploited to train face recognition or verification systems. The setting is illustrated in Figure 4a. We assume the user has access to a small dataset of facial images and will use this small dataset to generate and apply the error-minimizing noise to his/her own face images before sharing them on online social media platforms. After this, the unlearnable version of face images on social media gets collected to train a DNN based facial recognition or verification system. The system will then be used to recognize one of the user’s clean face image captured somewhere by a camera. The goal is to prevent the DNN from learning the defender’s face images and make it perform poorly on his/her clean face images.
We conduct the experiments under two different settings: 1) partially unlearnable where a small subset of identities in the training set are unlearnable; or 2) fully unlearnable where the entire training set is unlearnable. We test our error-minimizing noise against both face recognition and verification models. Face recognition model classifies the identity (class) of a face image, while face verification model verifies whether two face images belong to the same identity. In the face verification problem, two face images are determined to be of the same identity if the cosine similarity between the features (extracted from a recognition model) of the two images is below a certain threshold.
Experimental Settings. We randomly split the WebFace dataset (Yi et al., 2014) into 80% for training and 20% for testing, according to each identity. In the partially unlearnable setting, we randomly select 50 identities from the training set of WebFace into a subset WebFace-50 as the users who want to hide their identities. We also randomly select 100 identities from CelebA (Liu
et al., 2015) into a subset CelebA-100 as the small dataset used to generate the unlearnable images for WebFace-50. The clean WebFace-50 part of the WebFace training data will be replaced by its unlearnable version for model training. This partially unlearnable version of WebFace training set consists of 10,525 clean identities and 50 unlearnable identities. In the fully unlearnable setting, the entire WebFace is made unlearnable. In both settings, the error-minimizing noises are generated using RN-18 and CelebA-100, following the procedure described in Section 4. We train Inception-ResNet models (Szegedy et al., 2016) following a standard training procedure (Taigman et al., 2014; Parkhi et al., 2015).
Effectiveness Against Face Recognition. Here, we adopt the partially unlearnable setting. The accuracy of the Inception-ResNet model on the clean WebFace test set is reported in the Figure 4b, separately for the 50 unlearnable identities and the 10,525 clean identities. The result confirms that the 50 identities with the error-minimizing noise are indeed unlearnable and the recognition accuracy of their clean face images is only 16%, a much lower than the rest of the identities (86%).
Effectiveness Against Face Verification. Here, we adopt both the partially and the fully unlearnable settings. In the partially unlearnable setting, we evaluate the model performance on 6000 (3000 positives and 3000 negatives) face image pairs randomly sampled from the clean test set of WebFace. The pair is labeled as positive if the two face images are of the same identity, negative otherwise. In the fully unlearnable setting, we independently train a second Inception-ResNet model on the fully unlearnable WebFace. To further eliminate possible (dis)similarities shared across the images from the same dataset (e.g., WebFace), we follow the standard face verification evaluation protocol (Deng et al., 2019) and use the 6000 face pairs from LFW (Huang et al., 2008) for testing.
Figure 7 in Appendix G shows the Receiver Operating Characteristic (ROC) performance of the models trained in both settings. The model trained in the partially unlearnable setting still has a good verification performance on unlearnable identities, although the Area Under the Curve (AUC) is lower than the clean identities. This is because a small subset of unlearnable examples is not powerful enough to stop the learning of a feature extractor. In fact, 2,622 (approximately equal to 25% of WebFace) clean identities are sufficient to train a high-quality facial feature extractor (Parkhi et al., 2015). This indicates that, while it is easy to make data unlearnable to classification models, it is much more challenging to stop the learning of a feature extractor. Nevertheless, the proposed error-minimizing noise is still effective in the fully unlearnable setting, reducing the AUC to 0.5321 (the clean setting AUC is 0.9975). Whilst there are still many unexplored factors, we believe our proposed error-minimization noise introduces a new practical tool for protecting personal data from unauthorized exploitation.

heading: 5 CONCLUSION

text: In this paper, we have explored the possibility of using invisible noise to prevent data from being freely exploited by deep learning. Different from existing works, our method makes data unlearnable to deep learning models. The effectiveness of this approach could have a broad impact for both the public and the deep learning community. We propose a type of error-minimizing noise and empirically demonstrate its effectiveness in creating unlearnable examples. The noise is effective in different forms (eg. sample-wise or class-wise), sizes (eg. full image or small patch), and is resistant to common data filtering methods. It can also be customized for a certain proportion of the data, one single class or for multiple classes. Furthermore, the noise can be easily transferred from existing public datasets to make private datasets unlearnable. Finally, we verify the usefulness for real-world scenarios via a case study on face recognition. Our work opens up a new direction of preventing free exploitation of data. Although there are still many practical obstacles for a large-scale application of the error-minimizing noise, we believe this study establishes an important first step towards preventing personal data being freely exploited by deep learning.

heading: ACKNOWLEDGEMENT

text: Yisen Wang is partially supported by the National Natural Science Foundation of China under Grant 62006153, and CCF-Baidu Open Fund (OF2020002). This research was undertaken using the LIEF HPC-GPGPU Facility hosted at the University of Melbourne, which was established with the assistance of LIEF Grant LE170100200.

heading: A ALGORITHM OF ERROR-MINIMIZATION GENERATION

text: Algorithm 1 Error-minimizing Perturbations 1: Input: Source Model θ, Perturbations δ, Lp , (x, y) ∈ Dc, Stop Error λ, Optimization steps M 2: Output: δ 3: repeat 4: for m in 1 · · ·M do 5: i,xi, yi = Next(x, y) 6: if sample-wise then 7: δ = δi 8: else if class-wise then 9: δ = δyi 10: end if 11: Optimize(xi + δ, yi, θ) 12: end for 13: for xj , yj in x, y do 14: δ = Perturbation(xi, yi, θ, δ) . Follow Equation 3 15: Cilp(δ,− , ) 16: end for 17: error = Eval(x, y, δ, θ) 18: until error < λ

heading: B MORE EXPERIMENT SETTING

text: For all experiments, we use Lp-norm with to regularize the imperceptibility, = 8/255 for CIFAR and SVHN, = 16/255 for ImageNet, different is used in Appendix D for additional understandings. The iterative steps T for Equation 3 is set to 20 steps for sample-wise noise and 1 for class-wise, α is set to /10. Since the class-wise noise is generated universally for each class, small iterative steps avoid overfitting to the specific example. For the class-wise experiments, we only use 20% of the training data Dc to generate the noise δ and apply to entire training dataset Dc → Du. The stop condition error rate is λ = 0.1 for ∆c and λ = 0.01 for ∆s. For SVHN and CIFAR-10, we set the M = 10 for CIFAR-10, M = 20 for CIFAR-100 and M = 100 for ImageNet in the mini-setting. For all models and experiments, we use the Stochastic Gradient Descent (SGD) (LeCun et al., 1998) optimizer with momentum 0.9, initial learning rate 0.025 and cosine scheduler (Loshchilov & Hutter, 2017) without the restart. We train all DNN models for 30 epochs on SVHN, 60 epochs on CIFAR-10, 100 epochs on CIFAR-100 and ImageNet. To generated fully unlearnable setting CIFAR-10 dataset, the computational cost is roughly 10% of the standard model training time for class-wise noise and 60% of standard model training time for sample-wise noise. Overall, the cost of generating unlearnable examples is far less than training a model on the data to be protected.

heading: C STABILITY ANALYSIS

heading: D RESISTANCE TO DATA AUGMENTATION AND ADVERSARIAL TRAINING

text:
Resistance to Data Augmentation. Another important property of the unlearnable examples created by error-minimizing noise is its resistance to data augmentations. Since standard data augmentation techniques like random shift, crop, flip and rotation have already been applied in previous experiments, here we consider 4 more advanced data augmentation techniques: Cutout (DeVries & Taylor, 2017), Mixup (Zhang et al., 2018a), Cutmix (Yun et al., 2019) and Fast Au-
toaugment (FA) (Lim et al., 2019). For Cutout, we set the cutout length to 16 pixels. For Mixup, we apply linear mixup of random pairs of training examples and their labels during the standard training process. For Cutmix, we apply linear mixup on the cutout region. For FA, we use the fixed augmentation policy, which consists of change contrast, brightness, sharpness, rotations and cutout. It is observed that advanced data augmentation techniques including Cutout, Mixup, Cutmix and FA can indeed remove the sample-wise noise to some extent, but far less effective on class-wise noise.
Adversarial Training. We also consider the Adversarial Training (AdvTrain), which is an augmentation based defence method against error-maximizing noise (Goodfellow et al., 2014; Madry et al., 2018). AdvTrain has been shown can effectively remove the non-robust features from the input and force the model to learn only the robust features (Ilyas et al., 2019). Compared to data augmentation techniques, adversarial training as a type of robust training technique is indeed more effective against both sample-wise and class-wise noise. However, adversarial training is known to suffer from a trade-off between robustness and accuracy (Zhang et al., 2019). For example, adversarial training only achieved 85% accuracy on the unlearnable CIFAR-10, there is still a roughly 10% (94.95% vs 85%) performance drop compared to standard training on the clean CIFAR-10. Moreover, due to the difficulty of min-max optimization, current adversarial training methods are still limited to small error-maximizing noise. To test this, we fix the maximum adversarial perturbation used by adversarial training to 8/255, while increasing the perturbation of error-minimizing noise to = 24/255. Note that adversarial training with perturbation 16/255 or 24/255 still suffers from convergence issues, even on small datasets like CIFAR-10. The results are shown in Figure 6. As can be confirmed, the clean test accuracy will drop to 79% on = 24/255 error-minimizing noise.
The above results indicate that 1) error-minimizing noise is resistant to standard data filtering especially the class-wise noise; 2) although it is less resistant to adversarial training, the model’s performance can still be significantly compromised by our error-minimizing noise noise. In future works, it is possible to develop more advanced unlearnable examples that can further decrease the performance of adversarial training. We believe our method can be improved by crafting the noise based on only the robust features, since adversarial training forces the model to learn only robust features (Ilyas et al., 2019).

heading: E CLASS-WISE NOISE TRANSFER FROM IMAGENET TO CIFAR-10

heading: F FLEXIBILITY ANALYSIS OF ERROR-MINIMIZING NOISE

text:
Here, we focus on the class-wise error-minimizing noise and further explore its flexibility from two perspectives: 1) effectiveness when applied to smaller patches rather than the entire image; and 2) effectiveness of two sets of mixed class-wise noise. These experiments are also conducted with RN-18 on the CIFAR-10 dataset. For all the error-minimizing noise, we fix the maximum perturbation to = 8/255.
Effectiveness on Smaller Patches. The unlearnable example can be very flexible and hard to be detected if the noise remains effective on smaller patches. To test this, we set the patch size to 32×32, 24× 24, 16× 16 and 8× 8 (CIFAR-10 image size is 32× 32). During the noise generation process when solving equation Equation 2, a random patch is selected and perturbed in each perturbation step and for each training example. Once a class-wise patch noise is generated, it then attached to a randomly selected location of a training example. The effectiveness of small patch noise is reported in Table 5. The effectiveness is still very high for patch size as small as 16× 16, although it is indeed decreased on smaller patches. An interesting observation is that the FA augmentation becomes less effective on 16× 16 noise than 24× 24 noise. We suspect this is because smaller patch noise can more easily escape the augmentation operations and stays unchanged after the augmentation.
Effectiveness of Mixed Noises. We conduct this mix noise to simulate two possible real-world scenarios: 1) different users apply different noise apply to their own data; or 2) one set of noise is exposed and upgraded to a new set of noise. In this experiment, we apply the noise on the full image. We repeat the class-wise noise generation twice and generate two sets of noise: ∆c1 and ∆c2. For each CIFAR-10 training example, we randomly apply one of the above two class-wise noise to create unlearnable example. We note this mixture by ∆c1 ∨∆c2. Note that the class-wise mixture will eventually become the sample-wise noise if we keep mixing more class-wise noise sets. We also perform another mixture between ∆c1 and a random noise ∆u sampled from [− , ] mixed by element-wise addition. We denote this mixture by ∆c1 + ∆u. The effectiveness of mixed noise is also reported in Table 5. For both mixtures, the proposed error-minimizing noise remains highly effective, although there is a slight decrease. Surprisingly, the mixture of one class-wise noise with random noise is even more effective than the mixture of two class-wise noise, especially against the FA data augmentation. This makes the error-minimizing noise even more flexible in practical usage.

heading: G RESULTS ON FACE VERIFICATION

heading: H CLASS-WISE NOISE VS. BACKDOOR ATTACK

text:
Here, we test if class-wise noise can be used as a trigger for the backdoor attack. Figure 8 shows the backdoor attack success rate when different types of class-wise noises are applied as the backdoor trigger. At the training time, we train RN-18 models on CIFAR-10 with 0%-100% of the training samples were made unlearnable by three types of class-wise noise: random noise, error-minimizing and our error-maximizing noise. At the test (attack) time, we compute the attack success rate as follows. There are 6 models for each type of class-wise corresponding the 6 unlearnable percentages. For each type of class-wise noise and each RN-18 model, we iteratively take a clean test image from the CIFAR-10 test set, then randomly select a target class (which is different from the true class of the test image). Then, we attach the target class class-wise noise to the clean test image. If the new test image is predicted by the model as the target class, then the attack is successful.
As shown in Figure 8, the class-wise error-maximizing (adversarial) noise is a highly effective trigger for backdoor attack, yet neither random nor our error-minimizing noise can be considered to be effective. The error-maximizing can achieve more than 75% attack success rate when only applied to 20% the training data. To achieve a similar level of attack success rate, both random and our error-minimizing noise should be added to at least 80% of the training data. This indicates that our method is different from backdoor attacks. The high attack success rate of adversarial noise may due to the fact that adversarial examples are hard (high error) examples, which force the model to pay more attention to the examples and remember more of the adversarial noise. Note that adversarial perturbations have also been used in backdoor research to enhance backdoor triggers (Turner et al., 2018; Zhao et al., 2020).

heading: I DIFFERENT GENERALIZATION METHODS FOR ERROR-MINIMIZATION NOISE

text:
The proposed error-minimizing noise is generated using PGD. Specifically, PGD is applied to solve the inner minimization problem in Equation 2. Since it is a typical constrained optimization problem, it can also be solved by other optimization (attack) methods such as FGSM (Goodfellow et al., 2014), L-BFGS (Szegedy et al., 2013) and C&W (Carlini & Wagner, 2017). However, the objective needs to be reformulated to apply some of these attacks. Here, we take L-BFGS (Szegedy et al., 2013) as an example to reformulate and solve the inner minimization problem in Equation 2. In (Szegedy et al., 2013), the adversarial attack problem is formulated as:
minimize c ‖δ‖p + L(x+ δ, y ′) y′ 6= y (4)
where c is a hyperparameter and the L is the objective function (e.g. the cross entropy adversarial loss). This form has been extended to other objective functions in C&W (Carlini & Wagner, 2017). The main objective of adversarial attack is to find small Lp (i.e. ‖·‖p) bounded noise δ that can trick the model to output a wrong label y′ 6= y. For unlearnable examples, we want to trick the model to predict the correct label y with the highest confidence (i.e. lowest error). Following Equation 4, the inner minimization problem in Equation 2 can be reformulated as:
minimize c ‖δ‖22 + L(x+ δ, y). (5)
We set c = 1.0 and use the cross entropy loss for L. We apply L-BFGS to solve Equation 5 using Adam (Kingma & Ba, 2015) optimizer and generate sample-wise noise ∆s on CIFAR-10. The number of optimization steps for Equation 5 is set to T = 200, while the number of optimization steps for the outer minimization in Equation 2 is set to M = 100 (see more details about T and M in Section 3.2). As shown in Figure 9, error-minimizing noise can also be generated using L-BFGS, and the noise is very effective in making the training examples unlearnable. However, compared to PGD, L-BFGS is slightly less effective.

title: UNLEARNABLE EXAMPLES: MAKING PERSONAL DATA UNEXPLOITABLE


summaries: The paper extends MuZero for nondeterministic domains (NDMZ). Compared to MuZero NDMZ also learns a function that determines who is to act (player 1,2 or chance) and a distribution of chance outcomes. This makes it possible to employ MCTS search adjusted to handle nondeterministic nodes on top of a tree constructed by NDMZ's neural nets.

summaries: This paper proposes NDMZ, which extends the previous MuZero algorithm to stochastic two-layer zero-sum games of perfect information. NDMZ formalize chance as a player (chance player) and introduces two additional quantities: the player identity policy and the chance player policy. NDMZ also introduce new node classes to MCTS, which allows it to accommodate chance.

summaries: This paper introduces NDMZ, short for nondeterministic MuZero, a deep reinforcement learning algorithm for model-based RL that doesn't use the rules of the game to perform search. The paper's contribution is mostly focused on describing how to construct the algorithm, and experimental results are provided at the end. A good analogy is that of a player that must play a (physical) board game by not only making decisions, but also acting out the game: producing random events, such as die rolls, and moving pieces on the board.

abstractText: The MuZero algorithm is known for achieving high-level performance on traditional zero-sum two-player games of perfect information such as chess, Go, and shogi, as well as visual, non-zero sum, single-player environments such as the Atari suite. Despite lacking a perfect simulator and employing a learned model of environmental dynamics, MuZero produces game-playing agents comparable to its predecessor, AlphaZero. However, the current implementation of MuZero is restricted only to deterministic environments. This paper presents Nondeterministic MuZero (NDMZ), an extension of MuZero for nondeterministic, two-player, zero-sum games of perfect information. Borrowing from Nondeterministic Monte Carlo Tree Search and the theory of extensive-form games, NDMZ formalizes chance as a player in the game and incorporates the chance player into the MuZero network architecture and tree search. Experiments show that NDMZ is capable of learning effective strategies and an accurate model of the game.

title: The *-minimax search procedure for trees containing chance nodes

venue: Artificial Intelligence,

title: A markovian decision process

venue: Indiana Univ. Math. J.,

authors:
C.B. Browne
E. Powley
D. Whitehouse
S.M. Lucas
P.I. Cowling
P. Rohlfshagen
S. Tavener
D. Perez
S. Samothrakis
S. Colton

title: A survey of monte carlo tree search methods

title: Efficient selectivity and backup operators in monte-carlo tree search

venue: Proceedings Computers and Games 2006. Springer-Verlag,

authors:
C. Hsueh
I. Wu
J. Chen
T. Hsu

title: Alphazero for a non-deterministic game

venue: In 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI),

authors:
Donald E. Knuth
Ronald W. Moore

title: An analysis of alpha-beta pruning

authors:
Levente Kocsis
Csaba Szepesvári

title: Bandit based monte-carlo planning

title: Game-playing and game-learning automata

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei Rusu
Joel Veness
Marc Bellemare
Alex Graves
Martin Riedmiller
Andreas Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
J. Pollack
A. Blair

title: Why did td-gammon work

venue: In NIPS,

title: Nannon: A nano backgammon for machine learning research

venue: In CIG,

title: PUCT) multi-armed bandits with episode context

authors:
Julian Schrittwieser
Ioannis Antonoglou
Thomas Hubert
Karen Simonyan
Laurent Sifre
Simon Schmitt
Arthur Guez
Edward Lockhart
Demis Hassabis
Thore Graepel
Timothy Lillicrap
David Silver

title: Mastering atari, go, chess and shogi by planning with a learned model, 2019

authors:
David Silver
Aja Huang
Chris J. Maddison
Arthur Guez
Laurent Sifre
George van den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot
Sander Dieleman
Dominik Grewe
John Nham
Nal Kalchbrenner
Ilya Sutskever
Timothy Lillicrap
Madeleine Leach
Koray Kavukcuoglu
Thore Graepel
Demis Hassabis

title: Mastering the game of go with deep neural networks and tree search

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018

title: Temporal difference learning and td-gammon

venue: J. Int. Comput. Games Assoc.,

authors: Jos WHM Uiterwijk. Monte carlo tree search in backgammon.

title: Online

venue: Available: http://hdl.handle.net/2268/28469 (current 2007).

authors:
Shi-Jim Yen
Cheng-Wei Chou
Jr-Chang Chen
I-Chen Wu
Kuo-Yuan Kao

title: Design and implementation of chinese dark chess programs

venue: IEEE Transactions on Computational Intelligence and AI in Games, 7:1–1,

authors:
S. Çalışır
M.K. Pehlivanoğlu

title: Model-free reinforcement learning algorithms: A survey

venue: 27th Signal Processing and Communications Applications Conference (SIU),

heading: 1 INTRODUCTION

text:
While the AlphaZero algorithm achieved superhuman performance in a variety of challenging domains, it relies upon a perfect simulation of the environment dynamics to perform precision planning. MuZero, the newest member of the AlphaZero family, combines the advantages of planning with a learned model of its environment, allowing it to tackle problems such as the Atari suite without the advantage of a simulator. This paper presents Nondeterministic MuZero (NDMZ), an extension of MuZero to stochastic, two-player, zero-sum games of perfect information. In it, we formalize the element of chance as a player in the game, determine a policy for the chance player via interaction with the environment, and augment the tree search to allow for chance actions.
As with MuZero, NDMZ is trained end-to-end in terms of policy and value. However, NDMZ aims to learn two additional quantities: the player identity policy and the chance player policy. With the assumption of perfect information, we change the MuZero architecture to allow agents to determine whose turn it is to move and when a chance action should occur. The agent learns the fixed distribution of chance actions for any given state, allowing it to model the effects of chance in the larger context of environmental dynamics. Finally, we introduce new node classes to the Monte Carlo Tree Search, allowing the search to accommodate chance in a flexible manner. Our experiments using Nannon, a simplified variant of backgammon, show that NDMZ approaches AlphaZero in terms of performance and attains a high degree of dynamics accuracy.

heading: 2 PRIOR WORK

heading: 2.1 EARLY TREE SEARCH

text: The classic search algorithm for perfect information games with chance events is expectiminimax, which augments the well-known minimax algorithm with the addition of of chance nodes (Mitchie, 1966; Maschler et al., 2013). Chance nodes assume the expected value of a random event taking place, taking a weighted average of each of its children, based on the probability of reaching the child, rather than the max or min. Chance nodes, min nodes, and max nodes are interleaved depending on the game being played. The *-minimax algorithm extends the alpha-beta tree pruning strategy to games with chance nodes (Ballard, 1983; Knuth & Moore, 1975).

heading: 2.2 MODEL-FREE REINFORCEMENT LEARNING

text: A notable success of model-free reinforcement learning for nondeterministic games is TD-Gammon, an adaptation of Sutton & Barto (2018)’s TD-Lambda algorithm to the domain of backgammon (Tesauro, 1995). Using temporal difference learning, a network is trained to produce the estimated value of a state. When it is time to make a move, each legal move is used to produce a successor state, and the move with the maximum expected outcome is chosen. Agents produced by TD-Gammon were able to compete with world-champion backgammon players, although it was argued that the stochastic nature of backgammon assisted the learning process (Pollack & Blair, 1996).

heading: 2.3 MONTE CARLO TREE SEARCH

text:
The Monte Carlo Tree Search (MCTS) algorithm attracted interest after its success with challenging deterministic problems such as the game Go, and it has been adapted for stochastic games in an number of different ways (Coulom, 2006; Browne et al., 2012). A version of MCTS by Van Lishout et al. (2007) called called McGammon (Monte Carlo Backgammon) was capable of finding expert moves in a simplified backgammon game. At a chance node, the next move is always chosen randomly; at choice nodes, the Upper Confidence bound applied to Trees (UCT) algorithm is used in the selection phase to choose player actions (Kocsis & Szepesvári, 2006).
The McGammon approach was adapted by Yen et al. (2014) to the game of Chinese Dark Chess and formalized as Nondeterministic Monte Carlo Tree Search (NMCTS). There are two node types in NMCTS: deterministic state nodes and nondeterministic state nodes. Nondeterministic state nodes contain at least one inner node; each inner node has its own visit count, win count, and subtree. Upon reaching a nondeterministic state node, an inner node is chosen using “roulette wheel selection” based on the probability distribution of possible resulting states. NMCTS was designed to suit the nature of Chinese Dark Chess, in which both types of state nodes may exist on the same level of the search tree; this is in contrast to backgammon, in which homogeneous layers of chance nodes and choice nodes are predictably interleaved.
Alternative MCTS approaches have been adapted for densely stochastic games, wherein the the branching factor at chance nodes is so great that successor states at chance nodes are unlikely to ever be resampled. These include Double Progressive Widening and Monte Carlo *-Minimax Search (Chaslot et al.; Lanctot et al., 2013). In this paper, however, we are concerned with games that are not densely stochastic.

heading: 2.4 ALPHAZERO AND MUZERO

text:
MCTS served as the foundation of the AlphaGo and AlphaZero algorithms, the latter of which attained superhuman performance in the deterministic domains of chess, Go, and shogi (Silver et al., 2016; b;a). AlphaZero substitutes neural network activations for random rollouts to produce policy and value evaluations, employs the Polynomial Upper Confidence Trees (PUCT) algorithm during search, and trains solely via self-play reinforcement learning (Rosin, 2011). Hsueh et al. (2018) adapted AlphaZero for a simplified, solved version of the nondeterministic game of Chinese Dark Chess, finding that AlphaZero is capable of attaining optimal play in a stochastic setting.
A notable limitation of AlphaZero is that the agent relies upon a perfect simulator in order to perform its lookahead search. The MuZero algorithm frees AlphaZero of this restriction, creating a model of environmental dynamics as well as game-playing strategies through interactions with the environment and self-play (Schrittwieser et al., 2019). Until recently, the state of the art in complex single-player domains such as Atari games involved model-free reinforcement learning approaches such as Q-learning and the family of algorithms that followed (Mnih et al., 2015; Çalışır & Pehlivanoğlu, 2019). Despite the burden of learning enviornmental dynamics, MuZero leverages its precision-planning capabilities to achieve an extremely strong degree of performance on these problems.
Given parameters θ and a state representation at timestep k, AlphaZero employs a single neural network fθ with a policy head and a value head: pk, vk = fθ(sk). In contrast, the MuZero model employs three networks for representation, prediction, and dynamics. A set of observations is passed into the representation function hθ to produce the initial hidden state: s0 = hθ((o1, . . . , ot)). The dynamics function recurrently takes a previous hidden state and an action image to produce an
immediate reward and the next hidden state: rk, sk = gθ(sk−1, ak). Any hidden state produced in such fashion may be passed into the prediction function fθ to produce a policy vector and scalar value: pk, vk = fθ(sk).
With this model, the agent may search over future trajectories a1, ..., ak using past observations o1, ..., ot; in principle any MDP planning algorithm may be used given the rewards and states produced by the dynamics function. MuZero uses a MCTS algorithm similar to AlphaZero’s search, wherein the representation function is used to generate the hidden state for the root node. Each child node then has its own hidden state, produced by the dynamics function, and prior probability and value, produced by the prediction function. These values are used in the tree search to select an action at+1 ∼ πt via PUCT.

heading: 3 NONDETERMINISTIC MUZERO

heading: 3.1 DEFINITIONS

text:
We consider here an extension of the MuZero algorithm for two-player, zero-sum games of perfect information with chance events. Following Lanctot et al. (2019), we will characterize such games as extensive-form games with the tuple 〈N,A,H,Z, u, ι, S〉, wherein
• N = {1, 2, c} includes the two rival players as well as the special chance player c; • A is the finite set of actions that players may take; • H is the set of histories, or sequence of actions taken from the start of the game; • Z ⊆ H is the subset of terminal histories; • u : Z → ∆nu ⊆ Rn, where ∆u = [umin, umax], is the utility function assigning each
player a utility at terminal states;
• ι : H → N is the player identity function, such that ι(h) identifies the player to act at history h;
• S is the set of states, in which S is a partition of H such that each state s ∈ S contains histories h ∈ s that cannot be distinguished by ι(s) = ι(h) where h ∈ s.
• The legal actions available at state s are denoted as A(s) ⊆ A; • Zero-sum games are characterized such that ∀z ∈ Z, ∑ i∈N ui(z) = 0; and
• A game of perfect information is one with only one history per state: ∀s ∈ S, |s| = 1.
A chance node (or chance event) is a history h such that ι(h) = c. A policy π : S → ∆(A(s)), where ∆(X) represents the set of probability distributions over X, describes agent behavior. An agent acts by sampling an action from its policy: a ∼ π. A deterministic policy is one where the distribution over actions has probability 1 on one action and zero on others. A policy that is not necessarily deterministic is called stochastic. The chance player always plays with a fixed, stochastic policy πchance.
A transition function T : S × A → ∆(S) defines a probability distribution over successor states s′ when choosing action a from state s. Because states are simply sequences of previous actions, a transition function can equivalently be represented using intermediate chance nodes between the histories of the predecessor and successor states h ∈ s and h′ ∈ s′. The transition function is then determined by πchance.
As we are concerned with perfect information games, we shall use s interchangeably with h throughout this text, such that s may refer to the single history h contained within it. For ease of notation we refer to the chance policy πchance as ψ.

heading: 3.2 MODIFICATIONS

text:
First, we shall extend N such that N = {1, 2, c, d} includes the new terminal player d. The terminal player is to act when a terminal state is reached, such that ∀z ∈ Z, ι(z) = d. We shall refer to nonchance, nonterminal players as choice players. Let us characterize the full action set A as the
union of the choice player action set Aπ , the chance player action set Aψ , and the terminal player action set Ad as follows: A = Aπ ∪ Aψ ∪ Ad. Let us introduce the special no-op action, which is produced when it is not a player’s turn to move, such that ∀n ∈ N and ∀s ∈ S,An(s) = {no-op} when ι(s) 6= n. The action set Ad of the terminal player contains the no-op action as well as the end action, which represents ending the game: Ad = {no-op, end}. We can see that for any given state, the set of legal chance actions and the set of legal choice actions are both subsets of the set of all actions: ∀s ∈ S,Aψ(s) ⊆ A, and ∀s ∈ S,Aπ(s) ⊆ A.
To provide input sk−1, ak to the dynamics function gθ, the original MuZero encodes the action performed as an image and stacks it with the current hidden state. As with any choice player action, we may then encode any chance action a ∈ Aψ taken from ψ(s) as an image and stack it with a previous hidden state to produce input for gθ.
For an agent to properly model a stochastic environment, it must determine when chance events occur as well as the distributions of their effects. The problem then is to learn an approximation of the player identity function ι(s) as well as the chance player policy ψ(s). We then add two quantities that our model, conditioned by parameters θ, must predict: the chance policy ck ≈ ψt+k and the player identity policy ik ≈ ιt+k in addition to the quantities already present in MuZero: the policy pk ≈ πt+k (which we now term the choice policy), value vk ≈ zt+k, and reward rk ≈ ut+k. Two modifications are made to the MuZero network architecture. The prediction function now produces the choice policy, chance policy, and value: pk, ck, vk = fθ(sk), while the dynamics function now produces the reward, next hidden state, and player identity policy: rk, sk, ik = gθ(sk−1, a), where the length of ik = |N|. We use the no-op action as a training target for the choice policy and chance policy when it is not that player’s turn to move.
Adding the L2 regularization term, we define our loss function as follows:
lt(θ) = K∑ k=0 lr(ut+k, r k t ) + l v(zt+k, v k t ) + l p(πt+k,p k t ) + l c(ψt+k, c k t ) + l i(ιt+k, i k t ) + c||θ||2 (1)

heading: 3.3 TREE SEARCH

text:
Equipped with these new quantities, we wish to modify our MCTS to accommodate chance nodes. To flexibly capture the dynamics of stochastic games, the model must determine who is to play before either making a player action, making a chance action, or terminating the search. We introduce the identity layer, a layer of nodes that we interleave with action layers. The identity layer employs our ι approximation to determine the direction of the search.
Let us declare the root node to be a choice node. As in MuZero, the root hidden state s0 is generated by passing observations into the representation function such that s0 = hθ((o1, . . . , ot)). We then derive the priors of the root node’s children by feeding the root hidden state into the prediction function: p0, , = fθ(s0); here, the chance policy and value may be ignored. Following MuZero, the children of the root node are taken from the set of legal actions derived from the true environment state, Aπ(st), and assigned edges corresponding to those actions; likewise, we select among the children of a choice node with PUCT during tree search.
The children of choice nodes are identity nodes. Upon expansion, the reward rk, next hidden state sk, and identity policy ik of an identity node is generated by applying the dynamics function to the hidden state of its parent sk−1 along with the image of its action: rk, sk, ik = gθ(sk−1, a). The prediction function is then applied to the next hidden state sk, yielding the choice policy, chance policy, and value: pk, ck, vk = fθ(sk). An identity node has a number of children equal to |N|; thus, in our example each identity node has four children corresponding to {1, 2, c, d}. A child is selected from an identity node using roulette wheel selection proportional to ik. The children from the choice player edges {1, 2} become choice nodes, the child from the chance edge c becomes a chance node, and the child from the terminal edge d becomes a terminal node.
Each chance node and nonroot choice node inherits the hidden state sk from its parent identity node and has a number of children equal to |A|. (We do not assume prior knowledge of |Aπ| or |Aψ|; so long as we begin with |A|, these are learned and approximated through training.) A choice node also inherits from its parent the value vk, and its children take their priors from the choice policy pk. A chance node inherits the chance policy ck from its parent and uses this to generate the priors of its
children; during search, the child of a chance node is also chosen using roulette wheel selection. All children of chance nodes and nonroot choice nodes are identity nodes.
In contrast with MuZero, backup is only performed when the leaf node is either a choice node or a terminal node. First, let us consider the case when the leaf node is a choice node. We will refer to identity nodes with a choice node parent as result nodes. We only employ PUCT during search when selecting among result nodes and use roulette wheel selection otherwise. Because of this, we only need add or subtract the value obtained from the leaf node to the result nodes found in the visit path. If the edge leading to the leaf node is the same as the edge leading to the parent of the result node, we add the value of the leaf node to the total value of the result node; otherwise, we subtract. If the leaf node is a terminal node, we start with the parent of the leaf node and search up the tree until we find the most recent choice node. We note the value and the edge leading to this most recent choice node, return to the leaf node, and proceed with backup as described above.
Pseudocode for a version of the algorithm applicable to board games lacking immediate rewards is given in full in Appendix A.

heading: 4 EXPERIMENTS

heading: 4.1 NANNON

text:
For testing, benchmarking, and evaluation, we used Nannon, a simplified variant of backgammon that is solvable through value iteration (Pollack, 2005). Nannon is properly considered as a parameterized set of games, such that the number of board points, checkers per player, and sides of dice may be changed, influencing the complexity of the game. It is played by rolling a single die. There is no stacking, and only one checker per point is allowed; however, two adjacent pieces of the same color form a block. The number of possible board states may be found with the following equation, where n is the number of points on the board and k is the number of checkers per player:
k∑ i=0 k∑ j=0 ( n i )( n− i j ) (k + 1− i)(k + 1− j) (2)
We chose two game configurations, both with a six-sided die: six points on the board with three checkers per player (6-3-6) and twelve points on the board with five checkers per player (12-5-6). 6- 3-6 Nannon has 2,530 states, and 12-5-6 Nannon has 1,780,776 states. The first game configuration has some surprising subtleties despite the small number of total states; the second, while much more complex, is still far more tractable than backgammon. Each configuration was solved using value iteration, yielding a lookup table with which the optimal policy could be derived (Bellman, 1957). This policy is used to guide the actions of the optimal player; by pitting agents produced by AlphaZero and NDMZ against the optimal player, we obtain a more objective estimate of their performance.

heading: 4.2 EXECUTION AND HYPERPARAMETERS

text:
The NDMZ algorithm was executed as follows. The Nannon game engine code was written in C++ using the OpenSpiel framework, while the algorithm was written in Python using Tensorflow 2.4. Dense multi-layer perceptrons were used instead of convolutional resnets. Models for fθ, gθ, and hθ were initialized with two hidden layers each of 256 weights, using SELU activation and LeCun Normal initialization (Klambauer et al., 2017). Experiments were carried out on a Kubernetes cluster with Ray using 500 CPU workers for evaluation and 300 CPU workers for self-play; a single T4 GPU was used for training.
One hundred rounds of self-play, training, and evaluation were performed. For both AlphaZero and NDMZ, the models run for three hundred games of self-play per round, while the tree search performs one hundred simulations per move. The 6-3-6 run used a replay buffer limit of 4,000 games, while the 12-5-6 run used a limit of 1,000, as games on the larger board are roughly four times longer; for both configurations, the replay buffer carries about 100,000 examples total. For MuZero, samples are pulled at random from randomly chosen games, and a K value of six is used, where K is the number of hypothetical steps in which the network is unrolled and trained via backpropagation through time. Around 600,000 examples are then seen per epoch for NDMZ and 100,000 for AlphaZero.
Training for both algorithms employs an Adam optimizer with a learning rate of 0.001 and a batch size of 512. We did not scale the hidden states to the same range as the action input, nor did we scale the loss by 1K or 1 2 . For the first twenty rounds of the trial, five epochs of training are performed; afterwards, only a single epoch is done. Evaluation of the AlphaZero and NDMZ agents is performed once before training begins and after every training iteration, consisting of 1,000 rounds of play versus the optimal player and 1,000 rounds of play versus an agent that makes moves at random (500 games of each color). For comparison with model-free algorithms, we ran the TD-Lambda algorithm on the same Nannon configurations. Three hundred games of self-play are performed per round, while training occurs with a learning rate of 0.001, λ = 0.7, and γ = 1.0.

heading: 4.3 DYNAMICS EVALUATION

text:
Tests were designed to provide more practical insight into the ability of the networks to capture the dynamics of the game. After each training iteration, five hundred games are played with random moves and two tests are performed.
For the first test, the game trajectories are analyzed in the following manner: For every position at timestep t reached in every game, the choice policy output pt of fθ is compared with the actual legal moves for that position: Aπ(stenv). If the choice policy ranks any illegal move with greater probability than a legal move, the position is marked a failure; otherwise, it is a success. This proceeds recurrently for K times, using the dynamics network gθ along with the move actually played to produce a new hidden state that is fed into fθ, obtaining pt+k for each k in 1, . . . ,K. The actual legal moves for these future states st+1, . . . , st+K are compared with the recurrently produced policies, and the results for all positions are averaged. We call this the top move dynamics test.
The second test proceeds along similar lines as the first; however, the position is marked a failure if any illegal move is given greater than uniform probability. For example, if pt has length 4 and an illegal move has probability > 0.25, the test for that position is a failure; otherwise it is a success. This we call the uniform dynamics test. Each test evaluates around 60,000 positions for 6-3-6 Nannon and 240,000 positions for 12-5-6 Nannon.

heading: 4.4 RESULTS AND CONCLUSION

text:
We observe in Figure 2 that, for both configurations, AlphaZero experiences a very sharp and immediate increase in performance against the random player; the performance of NDMZ, on the other hand, exhibits a gradual curve before reaching a plateau of near-convergence with the AlphaZero agent. This is similar to some of the results shown in Figure 2 of Schrittwieser et al. (2019), where we see that the Elo performance of the MuZero agent eventually converges with that of the AlphaZero agent in the domains of chess and shogi. Moreover, we see that both AlphaZero and NDMZ exceed the performance of the TD-Lambda agent by a significant margin in the 12-5-6 configuration. The dynamics experiments in Figure 3 show that NDMZ agents can predict valid moves with a high degree of accuracy even several moves deep in the search. By comparing the two graphs, we also observe that the performance of the agent improves as it better learns to model its environment.
From these results, we may conclude that NDMZ is capable of learning effective strategies and a useful model of the game. Future work could entail testing NDMZ on games with more unorthodox chance node interleavings, such as Chinese Dark Chess, and extending the algorithm to accommodate more complex single-player environments such as the Atari suite.

heading: A APPENDIX

text:
Algorithm Nondeterministic MuZero Tree Search 1: function NDMZSEARCH(senv) . senv is the raw environment state 2: create root node w0 3: EXPANDROOT(w0, senv) . adds children and hidden state to root 4: while within computational budget do 5: wL ← TREESELECT(w0) . returns a leaf node 6: if K(wL) = choice or K(wL) = terminal then . K is the kind of node 7: BACKUP(wL, v) 8: W← children of w0 . N is the number of visits 9: w1 ← sample a child w′ from W proportional to N(w
′)1/τ∑ b∈WN(b) 1/τ . τ : temperature param
10: return A(w1) 11: 12: function EXPANDROOT(w0, senv) 13: S(w0)← hθ(senv) . representation network assigns hidden state S to root. 14: K(w0)← choice . root is choice node 15: p, , ← fθ(S(w0)) . prediction network: choice policy logits 16: p← masked softmax of (p,Aπ(senv)) . scale for legal actions only 17: for e ∈ Aπ(senv) do . for each edge e taken from the set of legal actions 18: add child w′ with . N : visit count; W : total value; 19: N(w′)← 0;W (w′)← 0;Q(w′)← 0; . Q: mean value; P : prior probability; 20: and P (w′)← pa;E(w′)← e . E: edge leading to node 21: 22: function BACKUP(w) 23: if K(w) = terminal then . if w is a terminal node 24: n← w 25: while K(n) 6= choice do 26: n← parent of n . search up the tree until we find the closest choice node 27: e← E(n) . player identity of the choice node 28: v ← V (n) . value from the choice node 29: else 30: e← E(w) . player identity of the leaf node 31: v ← V (w) . value from leaf node 32: while w is not none do 33: j ← parent of w 34: if K(w) = identity and K(j) = choice then . if w is a result node 35: if E(j) = e then . if the edge leading to j is the same 36: W (w)←W (w) + v . add to total value 37: else 38: W (w)←W (w)− v . subtract from total value 39: N(w)← N(w) + 1 . increment visit count 40: Q(w)← W (w)N(w) . adjust mean value 41: w ← parent of w
42: function TREESELECT(w) 43: while K(w) is not terminal do 44: if w not expanded then . w is a leaf node 45: return EXPAND(w) . adds child nodes, hidden state, and value 46: W← children of w 47: if K(w) = chance or K(w) = identity then . chance or identity node 48: w ← sample w′ from W weighted by P (w′) . roulette wheel selection 49: else if K(w) = choice then . choice node
50: w ← arg max w′∈W
( Q(w′) + cpuctP (w ′) √∑ b∈W N(b)
1+N(w′)
) . PUCT
51: return w 52: 53: function EXPAND(w) 54: j ← parent of w 55: if K(j) = choice or K(j) = chance then . if w is the child of a choice or chance node 56: K(w)← identity . w is an identity node 57: , S(w),p← gθ(S(j), A(w)) . for board games, we ignore the reward 58: O(w), C(w), V (w)← fθ(S(w)) . choice policy, chance policy, and value 59: C← N . C is the set of child edges 60: else if K(j) = identity then . if w is the child of an identity node 61: S(w)← S(j) . w always inherits the hidden state of its parent 62: if A(w) = c then . if the edge leading to w is the chance edge c 63: K(w)← chance . w is a chance node 64: p← C(j) . p is the chance policy vector 65: C← A . A is the full action set 66: else if A(w) = d then . if the edge leading to w is the terminal edge d 67: K(w)← terminal . w is a terminal node 68: C← {} . terminal nodes have no children 69: else 70: K(w)← choice . w is a choice node 71: p← O(j) . p is the choice policy vector 72: V (w)← V (j) . w inherits value from parent 73: C← A 74: for e ∈ C do . for each edge in the set of child edges 75: add child w′ with 76: N(w′)← 0;W (w′)← 0;Q(w′)← 0; 77: and P (w′)← pe;E(w′)← e . assign prior to child from p along with edge e 78: return w