Scalable Subset Sampling with Neural Conditional Poisson Networks
Authors: Adeel Pervez
Phillip Lippe
Efstratios Gavves
Venue: ICLR 2023 poster (2023)

Abstract: A number of problems in learning can be formulated in terms of the basic primitive of sampling $k$ elements out of a universe of $n$ elements. This subset sampling operation cannot directly be included in differentiable models and approximations are essential. Current approaches take an \emph{order sampling} approach to sampling subsets and depend on differentiable approximations of the Top-$k$ operator for selecting the largest $k$ elements from a set. We present a simple alternative method for sampling subsets based on \emph{conditional Poisson sampling}. Unlike order sampling approaches, the parallel complexity of the proposed method is independent of the subset size which makes the method scalable to large subset sizes. We adapt the procedure to make it efficient and amenable to discrete gradient approximations for use in differentiable models. Furthermore, the method also allows the subset size parameter $k$ to be differentiable. We demonstrate our approach on model explanation, image sub-sampling and stochastic $k$-nearest neighbor tasks outperforming existing methods in accuracy, efficiency and scalability.

Published as a conference paper at ICLR 2023
SCALABLE SUBSET SAMPLING WITH NEURAL CONDI- TIONAL POISSON NETWORKS
Adeel Pervez QUVA Lab, Informatics Institute University of Amsterdam a a.a. a.a.pervezuuv..
Phillip Lippe
Efstratios Gavves QUVA Lab, Informatics Institute University of Amsterdam e ggvveeeuvva...
QUVA Lab, Informatics Institute University of Amsterdam p. 1.lppe@uva.nl
ABSTRACT
A number of problems in learning can be formulated in terms of the basic primitive of sampling & elements of a universe of elements. This subset sampling operation cannot directly be included in differentiable models, and approximations are essential. Current approaches take an order sampling approach to sampling subsets and depend differentiable approximations of the Top-k operator for selecting the largest & elements from a set. We present simple alternative method for sampling subsets based on conditional Poisson sampling. Unlike order sampling approaches, the complexity of the proposed method independent of the subset size, which makes the method scalable to large subset sizes. We adapt the procedure to make it efficient and amenable to discrete gradient approximations for use in differentiable models. Furthermore, the method allows the subset size parameter k to be differentiable. We validate our approach extensively, on image and text model explanation, image subsampling and stochastic k-nearest neighbor tasks outperforming existing methods in accuracy, efficiency and scalability.
INTRODUCTION
The fundamental combinatorial operation of selecting subsets of elements from a given universe is ever increasingly being incorporated in differentiable neural models due to its range of applicability. Example applications include model explanations (Chen al., 2018), sequence modeling (Kool et 2019), point cloud modeling (Yang et al. 2019), and nearest neighbor networks (Grover et al. 2018).
Current neural network approaches for sampling subsets generally fall in the class of order sampling methods. In the order sampling scheme, each element in the universe is assigned an independent ranking random variable. To obtain a subset sample of size k. the largest (or smallest) & elements chosen. Thereby, the ranking variable distribution induces probability distribution over the possible subsets. However, the operation of choosing the largest elements (Top-k) is naturally not differentiable, since it is discrete operation. This means that the Top-k procedure cannot be directly used in gradient learning models. This has led to a number of proposals of relaxed and differentiable versions of the Top-k operator (Goyal al.) 2018 Pietruszka et al. 202 Plötz & Roth 2018). Building on Top-k approaches several methods of sampling subsets as k-hot vectors have appeared in the literature (Paulus et al. 2020 Xie & Ermon 2019).
In this paper, we explore Poisson sampling (Tillé 2006) and conditional Poisson sampling (Hájek & Dupaě 1981) as an alternative to order sampling for subsets. With Poisson sampling, each element in the set independently drawn to be selected for the subset or not. As these independent trials cannot guarantee a fixed size for subsets, with conditional Poisson sampling, the Poisson sampling procedure conditioned return subsets of exactly & elements. In practice, the conditioning amounts to repeating the Poisson sampling procedure until subset of size k is obtained.
The general (conditional) Poisson sampling approach has number of features which make it an attractive alternative to Top-k-based order sampling methods. Firstly, the sampling is done independently in Poisson sampling methods, which makes the procedure very efficient for sampling subsets with large values of By contrast, current Top-k methods (Goyal et al.) 2018) Plötz & Roth 2018) often have inner loop depending k, which makes them expensive for sampling large

---

Published as a conference paper at ICLR 2023
subsets in terms of both time and memory. Furthermore, computations in modern neural network models are vectorized. This makes sampling different subset size & for different elements in a batch difficult for current Top-k procedures, since the number of sampling iterations to obtain the Top-k elements depend on k. With Poisson sampling, it is trivial to sample different subset sizes for batched inputs, making it ideally suited vectorized computation. Finally, with Top-k, the subset size itself is not differentiable. With Poisson sampling, A appears as a scaling parameter for the probabilities of the individual elements in the universe. Therefore, the subset size parameter it can easily be incorporated in differentiable computations when having a differentiable sampling procedure.
Despite the aforementioned advantages, there are two difficulties with Poisson sampling. The first is that vanilla Poisson sampling can lead to large variance in the sampled subset size. This can be resolved with conditional Poisson sampling to obtain exact samples, but only at the cost of high computational complexity. The second (and main) difficulty is that neither Poisson sampling nor its conditional variant are differentiable and cannot be directly included in differentiable models.
In this paper, and in the context of differentiable subset sampling with neural networks, we propose neural conditional Poisson subsel sampling. We note that often we do not need subsets elements exactly, conditional Poisson sampling would have do, and instead sampling k-sized subsets in expectation is enough. With neural conditional Poisson subset sampling, we relax the constraint of sampling exactly & elements, thus allowing to trade off accuracy in the subset size for efficiency of sampling large subsets. Compared to Top-k approaches for sampling subsets (Xie & Ermon 2019). neural conditional Poisson subset sampling allows for efficient sampling of large subsets, easy choice of per-instance subset sizes, and differentiable subset sizes for a small loss in subset size accuracy, when an exact number of elements in the sampled subsets is not a necessity. Secondly, we adapt the sampling procedure so that gradient approximations for discrete variables are applicable. The resulting method is scalable and can be used sample large subsets even from image-size domains in full resolution a task that is to date infeasible for current subset sampling methods.
2 PRELIMINARIES
= ......... n denote universe consisting of elements. Each element i E U is assigned a "size" pi E (0, 1). We assume the sizes here to be normalized to the unit interval. Let x denote a (æ1, subset of the elements in U represented as indicator vector of size n, ; ..,), where I; E {0, 1} and x₁ = if the äth element is included in the subset. The sample size is the number of elements, i.e Σ xi. in the chosen subset. In this paper, we are concerned with sampling subsets of given size k from universe of n elements.
A sampling design (Tillé 2006), S. is way assign probability each subset of universe U, i.e., S P(U))) -> (0, IJ. where P(U) is the power set. Intuitively, a sampling procedure induces sampling design by assigning each subset with the probability with which the subset is chosen. Conversely, there could be a number of sampling procedures that correspond to the same sampling design. Occasionally, a sampling procedure also referred as a sampling design.
Inclusion Probability. Important parameters of a sampling design are the inclusion probabilities. The first order inclusion probability of an element i is the marginal probability, over the space of samples, that i is included in the sample. If 7; is an indicator variable where I; when i is included, the i-th inclusion probability is T : [T.]..
2.1 POISSON SAMPLING
Poisson sampling Tille 2006) is a probability- proportional-to -izsssze sampling design for sam- pling without replacement. This means that each element is included in the sample with prob- ability proportional to its size p., where we as- sume that >, P; 1. With Poisson sampling, the sample size is a random variable with ex- pected size k. Given independent uniform ran- dom variables u, ~ U(0, 1). an element is
Algorithm 1 Poisson Sampling
Require: Input p E 1)". Σ,p. = 1; integer; Require: Output S
I: for i= 1,..., n do
Sample
24 1)
if u, S kp; then S S (1)
end if end for included in the sample if u, < kp; (see Algo-
2

---

Published as a conference paper at ICLR 2023
rithm I. When kp; for some i, the corresponding elements always added to the output. The procedure is then repeated for the remaining elements after appropriate normalization (Tillé 2006). When using Poisson sampling, the resulting sample can have large variance in sample size due to independent sampling of elements.
2.2 CONDITIONAL. POISSON SAMPLING
Conditional Poisson sampling Hájek & Dupač 198T) is a sampling design over samples with exactly & elements. The design can be imple- mented simply by repeating the Poisson sam- pling procedure until a sample with exactly k elements is obtained. That is, discarding the en- tire sampled subset if it does not contain exactly element and repeating from scratch. Since the sampling has to be repeated, it may require many trials before a size k sample obtained. Hájek & Dupač (1981) 1) showed that conditional Pois- son sampling is a maximum entropy design, sub- ject to required inclusion probabilities p; (when Ep: = k) and sample size
Algorithm 2 Conditional Poisson Sampling
Require: Input E (0, 1)", Σ, = 1; integer;
Require: Output $
S ()
while [S] + do
S 0
4:
for = L,.., do
5:
Sample u; ~ ((0, 1) if < kp; then
S Su end if end for 10: end while
One potential difficulty with conditional Poisson sampling is that the inclusion probabilities m, which we would approach we repeated the sampling numerous times, are approximations of the desired probabilities Pt. when P1, --.. Pr, also used sampling probabilities. This is because with standard Poisson sampling with the probabilities pt, not all samples result in valid subset of size k.
It is possible improve the approximation by correcting the given p; obtain sampling probabilities p/. Using the corrected p/s for sampling leads to inclusion probabilities, n5, that are closer to the desired probabilities P: (Lundquist 2009).
3
NEURAL CONDITIONAL POISSON SUBSET SAMPLING
We first give an overview of the proposed sampling procedure, and we detail it next.
3.1 OVERVIEW
Conditional Poisson sampling only accepts samples of exactly elements, discarding the sample otherwise. This may require numerous sampling iterations, thus becoming an efficiency bottleneck. On the other hand, vanilla Poisson sampling can be viewed as repeating the same process only once, thus yielding high variance in the subset size. Furthermore, neither Poisson sampling nor the conditional extension is differentiable relative to the parameters p;. Oftentimes, it is not strictly necessary to sample exactly size k subsets (unlike conditional Poisson sampling), for as long as the subsets that we sample are size k in expectation and with low variance (unlike Poisson sampling). This, for example, is the case when we need to explain images in terms of large subsets of pixels.
Leveraging this observation, we propose neural conditional Poisson subset sampling (NCPSS), which intermediate between Poisson sampling and conditional Poisson sampling. Similar to conditional Poisson sampling, our sampling procedure performs multiple passes. Differently, however, for every new pass, and depending on whether our sample has more or less than & elements, we do not throw away the previously sampled subset: instead, we add remove elements from it. Crucially, repeat our sampling procedure only for a predetermined number passes. That is, unlike conditional Poisson sampling, do not need to sample exactly & elements to terminate. We show that this adaptation reduces variance in the subset size while yielding significant gains in sampling efficiency.
3.2 PROPOSED SAMPLING PROCEDURE
In the context of neural networks, we want to make our sampling procedure amenable to training by discrete variable gradient approximations. We, therefore, first adapt the Poisson sampling procedure
3

---

Published as a conference paper at ICLR 2023
so that the scaled probabilities kp, remain bounded in (0, 1). That is. if we have sampling probabilities Pj and their sum s : Σ, Pt. we compute the normalized probabilities pt/s. The reason is that we then only require for our new sampling procedure to sample from Bernoulli distributions, and can rely on popular gradient estimations for discrete operations, like StraightTThrouge (Bengio et al. 2013) or Gugmell-igmoid relaxations (Maddison et al. 2017).
Reversing samples. To sample a subset of size & with Poisson sampling, we multiply the normalized probabilities by k. Unfortunately, this results in probabilities p.k/s that can be greater than if k/s > 1. Specifically, elements with p:k/s > will certainly be included in the sample, which, however, is no longer valid Bernoulli sample since the "probability" parameter is greater than 1.
We make, however, the observation that if k/s > 1, we could still sample from the complementary distribution with probabilities 1 - Pt. since E - p:)
and (n k)/(n ()----) s) S where n is the total number of elements. This implies that if & > we can perform Poisson sampling with probabilities (1 pt) to compute the individual sampling probabilities as (1 pt)(n k)/(n - s). Performing Bernoulli sampling with these new probabilities gives a sample with expected size k. In this case, rather than sampling the elements to include from our full set, we sample instead the k elements (in expectation) to exclude. For the final sample, we simply flip (i.e., flip Is and Os) our obtained "exclusion" sample of expected size k having used only Bernoulli samples.
Reducing variance by iterating. Our new sampling procedure is based on Poisson sampling. and thus will return samples of size k in expectation. To reduce variance in sample size, we perform a (small) prescribed number of passes. Let U {1, ..... n be our full set and St the currently sampled subset at iteration f. During each new pass 1+ we either add or remove elements from St to get closer to size k. Specifically, if our current sampled subset is smaller than it should (S&tl < k), we make a new pass over the unselected elements, U-S,, to sample new elements add. Conversely, if our current sampled subset is larger than it should (|S{a) > k), we make a new pass over the currently selected elements S,, and use the inverted probabilities,
Benelese]] k--000 n-1509
35-
30-
Count
1 Pi, to sample which elements to remove.
While this procedure is more efficient than conditional Poisson sam- pling by relaxing the constraint of obtaining exactly size-k subsets, we can also show that it produces samples of lower variance com- pared to regular Poisson sampling. Specifically, under reasonable assumptions and for the simpler case of equal input probabilities, i.c.,
260
200
Subset Size
Num liaratonssS, 10300 (- 3000
300
500
Pi = P2 ... Pn. the subset size variance decreases exponentially with the number of iterations. This implies that only a few iterations required to obtain samples that close to the target size k.
300
200
Proposition 3.1. Let St {0, 13" denote the subset and qi bounding the probability at step i in the iterative Poisson sam- pling procedure. Then after T iterations we have Var([Sr)) S Var([Si I[=224 9. where V'r((S;)) is the Poisson sampling vari- ance. Assuming that the probability bound is bounded away from 1, i.e., 9: < 1- for > O, the procedure obtains an exponential decrease in variance with the number of steps T.
260
280
300
320
340
Subset Size
Figure 1: Histograms showing subset size distribution with = 1 iteration (top) and 5 iter- ations (bottom), when choos- ing k = 300 elements from n 3000 elements. We ob- serve a large reduction in vari- ance with 5 iterations.
We provide the proof of this proposition in Appendix an empirical verification of the exponential reduction in variance in Figure | with the details of the experiment given in Appendix E
well
3.3 END-TO-END ALGORITHM
Next, we introduce Neural Conditional Possion Subset Sampling (NCPSS), a differentiable way of using the previously described sampling procedure a gradient- based learning framework. Given a probability vector p; parameterized by neural network and sum = Ee Pi. for each i, we adjust the sampling probabilities to the subset size s. We refer to these probabilities as qi and compute them as:
kkp:/s 1 (n- (n-b)(1 - (p - k>s
k k<=s
qi
(1)
4

---

Published as a conference paper at ICLR 2023
Algorithm 3 Iterative Poisson Sampling
Require: Input p E (0, 1)": integer; iterations
12:
if <= then
I: Initialize empty output set O.
13:
Optionally apply correction to kp,/s for each i
2: Repeat 3-9 for iterations.
to obtain corrected probabilities Pl.
3: if O has less than & elements then
14:
Bernoulli(p.) for cach i.
4: Run Sample-Appro--K-Haee only with ps where
15:
clse
in # and &
[O].
16:
Optionally correct (n (1 - p.) s) for each to obtain corrected probabilities pi.
5:
Add result to O.
6: else if O has more than & elements then
17:
= Bernoullipp) ) for each i.
7: Run Sample-Approx K- K-Hot only with p. coordi-
18: end if
nates with x; k |O| and p = p. Remove result from
19: if > 8 then
20: I = x.
9: end
21: end if
10: Function Gample-Approx-Ae --oot (p.
22: Return
11:
Compute -Ex EEp.. pi.
23: EndF
In the forward pass, we run the approximate conditional Poisson sampling procedure to ob- tain a k-hot sample x, which can be used as input to the downstream neural network. the backward pass, the gradient relative to is used as the straight-through gradient relative to qi- As the new Poisson sampling procedure relies only Bernoulli samples,
also relax the entire approximate conditional Poisson sam- pling procedure by the numbel-Sigmoin relax- ation (Maddison et al.] 2017). In this paper, however, we rely exclusively on the described straight- -hhrough gradient estimation, since it showed work well in our experiments. The full algorithm is described in Algorithmm]aan pseudocode is given in the appendix in Algo- shows the modular ar-
Forward
Backward
Berative Poisson Sampler
Straight-Through
Graciant
rithm 4 Also, Figure 2 chitecture with the conditional Poisson subset sampling and ttraigh-tthrough gradients.
Figure 2: Diagram of the proposed k-hot sampling procedure with traighh-thhouue gradients. The vector of probabilities p is output by neural net- work. The vector q is computed using Equation [
3.4 OTHER CONSIDERATIONS
Number of iterations. The method described in Algorithm B depends repeating the Poisson sampling procedure for a number of iterations t. Here we note that does not depend on the subset size parameter l unlike Top-k procedures and is a fixed constant. Second, we note that the function of the parameter is to reduce variance in the subset size and a few iterations is enough to obtain with high probability sample size within 1 of k. even for large In our experiments, we choose I between 5 and 8. Empirical results on the sample variance are discussed in Appendix E and Figure
Differentiable subset size. We observe Equation I and Algorithm that the subset size parameter k appears only as scaling parameter in the probability vector. This implies that A can be made differentiable assuming that the samples can be differentiated, for instance using the straight-through estimator described earlier or some kind of relaxation. In this case, we learn & as fraction of the overall number of elements n,, i.e. k/n i (as a continuous sigmoid output), and then rescale it by n. Note that this procedure is different from Top-k procedures, which usually use & in an internal loop index, making differentiation difficult.
Correction for inclusion probabilities. Given of desired probabilities pa such that Σp. k. the conditional Poisson design does not necessarily lead to inclusion probabilities n, such that ,, = p.. However, it gets approximately close, i.e. Mi Dc. when d Dupaë 1981) 1). Furthermore, Bondesson et al. (2006); Lundquist (2009) suggest corrections for the sampling probabilities improve the approximation, which we discuss in more detail in Appendix C
P1(1 pt) is large (Hájek &
Complexity. The parallel (vectorized) complexity of the method (Algorithm 3 is constant, ((1), up to the logarithmic factors required for reduction operations such summation. This is because each
5

---

Published as a conference paper at ICLR 2023
Poisson sampling step has constant parallel complexity up reductions and we only iterate for constant number of steps because of exponential variance reduction.
4 RELATED WORK
few approaches for selecting subsets have appeared in the literature. Some of these methods (Pietruszka et al.) 202 I Plötz & Roth 2018 Xie et al. 2020) are designed to satisfy pre-defined constraints, such as fixed subset size. Other methods use regularization objectives to find some optimal subset size (De Cao et al. 2000:oouizos et al. 20188) , The methods can be further classified
in terms of whether they are deterministic (Pietruszka et al 2021 Plötz & Roth 2018 Xie et al.
2020) or stochastic (Chen al. 2018 Paulus et al. 2020 Xie & Ermon 2019).
Deterministic methods with constraints on the subset size often depend on relaxations of the Top-k operator for selecting the largest elements from a set. One such relaxation is developed by Plötz & Roth 2018) as a repeated temperature-scaler softmax that is iterated le times. At each iteration, an element sampled from the categorical distribution induced by the softmax. For the next iteration, the categorical distribution is re-normalized after setting the probability of the selected sample to zero. The relaxation replaces samples from the distribution by expectations. Top-k relaxations have been proposed with optimal transport (Xie et al. 2020) and tournament selection (Pietruszka et al., (021).
The Top-k relaxations are deterministic operations which can be combined with ranking distributions for sampling subsets. Building on Reservoir Sampling Efraimidis & Spirakis (2006). Xie & Ermon (2019) define a subset sampling operation by using the Gumbel distribution as a ranking distribution and using the Top-k relaxation defined by Plötz & Roth R (2018). A similar approach is taken by Goyal cct al. (2018). Another sampling method is used by [Chen et al. (018)) where independent samples are taken from the Concrete distribution (Maddison al.) 2017) followed by the element- wise maximum. This has the disadvantage that features may be repeated and fewer than & elements might be finally selected.
In comparison, our proposed method is stochastic, and we impose a weaker constraint on the expected subset size rather than hard constraint the exact size and reduce variance. We also allow controlling the subset size per-instance by adding a regularization objective.
Poisson sampling, conditional Poisson sampling (Hájek & Dupač 1981 Tille 2006 and related methods have been traditionally used in applications such as survey design (Ogus & Clark 1971 and the consumer price index (Ohisson 1990).
EXPERIMENTS
We validate neural conditional Poisson sampling three different tasks: model explainability for text and image classification Chen et al. (2018), high resolution image sub-sanpling Huijben et al.] (2019), as well differentiable k-nearest neighbor search Plötz & Roth (2018). Specifically, image sub-sampling requires sampling from as many as 260K elements, which is the pixel resolution of the images. Sampling from large spaces is intractable with current models due extreme dimensionality, showing the scalability of the proposed method. Last, we validate with ablation experiments the efficiency, variance reduction, and inclusion probability approximation for the method. For lack of space, the latter experiments can be found in Appendix
5.1 LEARNING TO EXPLAIN TEXT CLASSIFICATION
For the task of model explainability, we work with the Learning to Explain framework of of et al. (2018). The aim is to generate post hoc instance-wise explanations of a classifier model, achieved by building an explainer network e to select the ls input features with maximal mutual information with the model prediction per instance.
Since it is difficult to compute the mutual information directly, the framework works with a variational lowerbound of mutual information parameterized by a neural network. The optimization problem solved by in the learning to explain framework written as
max Bllog q (X))), where S ~ e(X),
(2)
e.g

---

Published as a conference paper at ICLR 2023
Table 1: Learning to explain text classification measured in post-hoc accuracy.
Model
IMDB (k = 10)
20NewsGroup (k 25)
20NewsGroup (I: 50)
1.2X
Chen et al.
2018
90.8
50.5
34.7
RSS
Xie & Ermon
2019
91.7
58.6
58.0
RSS
[Xie & Ermon
2019
ST
91.7
51.9
58.4
NCPSS
91.2
67.9
66.5
NCPSS differentiable k
91.2
65.7
68.2
Table 2: Learning explain image classification measured in post-hoc accuracy. The RSS baseline
runs out of GPU memory on sizes greater than 100. The baseline CIFAR-10 and STL-10 models have 80% and 75% accuracy respectively
CIFAR- 10
STL-10
k
100
150
100
400
600
700
RSS (Xie & Ermon 2019
50.7
54.1
42.5
NCPSS NCPSS diffcrentiable k
63.6
65.2
68.0
50.6
56.3
57.6
59.6
60.3
64.9
65.3
46.2
50.1
51.7
53.4
where (Xxs) is the variational lower bound parameterized by neural network, Xs is the subset of k: features output by the explainer network e.
In practice, the output of the explainer network is a k-hot vector distribution from which sample S used to mask features the true input X by element-wise multiplication, i.e., Xs = @ For the text classification experiments two classes for sentiment classification. We follow the same pre- pre-processin as in Chen et al. (0018) by resizing each review to 400 words. We also use the 20Newsgroups dataset (Rennie & Lang 2008
the Large Movie Review Dataset (Maas et al.) 201 11) with
for classification posts 20 different newsgroups. We resize each document to 1000 words by padding or cutting.
The models to be explained both cases are convolutional neural networks, which achieve 90% and 70% test accuracy IMDB and 20Newgsroups, respectively. For the 20Newsgroups dataset we use pretrained GLoVe embeddings (Pennington et al., 2014). while for IMDB we train from scratch. For the IMDB dataset we select 10 words as explanations, while for the 20Newsgroups dataset we use & E {25. 50} words. We use the same network architecture as in Chen et al. (2018) for the IMDB dataset. For 20Newsgroups we use similar architecture but with two extra convolutional layer each the explainer and the variational net- work and filter size of 128. We evaluate the final performance using post hoc accuracy (Chen et al.) 2018). For evaluation we always use hard binary vectors masks S.
NCPSS
2000
1000
10
30
40
50
Subset Size
RelaxSubSample
1500
1000
500
15
20
25
30
15
43
45
50
Subset Size
The results are shown Table T In the simpler IMDB dataset both model and RelaxSubSampling (RSS) explain well classifications with a small number of words k. matching the ac- curacy of the full model. For the larger 20Newsgroups, however, neural conditional Poisson sampling outperforms RelaxSubSam- pling by significant margin of 7-10%, while coming close the accuracy of the full model. Moverover, when comparing sam- pled tokens, we see that RelaxSubSample (Xie & Ermon 2019) samples often invalid words like padding tokens unlike neural conditional Poisson sampling, as seen in F This shows that Relax RelaxSubSampling is unable to take advantage of larger subset sizes when going from & = 25 to 50. These results validate claim that method performs better with larger subsets, whereas Gumbel Top-k relaxations deteriorate because of their longer softmax iteration chains. For NCPSS, both A 25 and & 50 achieve post-hoc accuracies close the original test accuracy.
Figure 3: Histograms showing frequency of sampled tokens that correspond to actual words and not padding for our method (top) and RelaxSubSample (bottom) on the 20Newsgroups evaluation set. i is set to 50 and only doc- uments with at least 50 words were considered. RelaxSubSam- ple shows a large variation the number of actual words selected.
7

---

Published as a conference paper at ICLR 2023
edu writes stuff del for bandwidth sake why sigh you don have more than mbs of memory using with windows is of memory windows will access mb ram better memory as to why what you did didn work it is because and paths are stored inside the group ini files all the sudden things went from drive to drive however you wanted to copy an application up to the and re setup it up that should work normally but as previously stated this will only hurt things unless you ve got more than mbs of ram and are using whats above as the personally have mb ram and run mb with great deal of success however if you are looking to speed up windows the three things noted that work the best are graphics card oo processor even an helps some other disk cache hesides ve tried several and lightning for windows and norton cache give me major headaches as well think the purpose the original poster was trying serve is to avoid the significant amount of disk access that windows does startup it like it trying to it bit in wearing the damn drive out estimate it only reading mb of programs data but from the performance the drive gives it sounds like they are scattered all over the drive my drive is however compressed what is it that takes so much perhaps if would take the trouble to this startup process less people would be wanting to find solution themselves
Class: comp.os os ms windwwiddwssiis. Predicted: comp.os.m comp.oss.mm. mss winnswwwiiwsss, Words Selected: 20/261, Total Tokens Selected: 20
Figure 4: Example text explanation with the 20Newsgroups dataset for correctly classified document with differentiable set size with an average explanation size of 50 words. this case the model chooses smaller explanation size of 20 words. In this case all chosen tokens correspond to actual words and no padding tokens or similar are selected. See the appendix for examples on longer inputs.
Differentiable explanation sizes. For explaining text documents with 20Newsgroups we also experiment with learning optimal differentiable subset sizes of k, for which we consider a prior k to be either 25 or 50. For this we add a squared loss term in the loss expression as 7 k)², where P4 is the mini-batch average k computed the network, and is the regularization strength chosen from {0.1, 0.01, 0.001}. Constraining only the average explanation size allows the model to choose the explanation size per instance, often yielding even stronger explanations in terms of post-hoc accuracies, see Table For instance, in Figure 4 the model chose a 20-word explanation for correct classification although the average explanation is conditioned to 50 words. Examples of longer explanations can be found in the appendix.
5.2 LEARNING TO EXPLAIN IMAGE CLASSIFICATION
We repeat the experiment now for explaining image classification models on CIFAR-10 Krizhevsky 2009) and STL--10 (Coates et al. 201 using the same "learning to explain" framework (Chen et al., 2018) and sub-pixel explainers. This means that the explainer outputs a 3x32x32 size mask for CIFAR-10 10 with 32x32 resolution, and 3x96x96 for STL-10. Generating such explanations requires large subset sizes. For CIFAR-I0 we explain a simple CNN model with 8 convolutional layers that achieves 80% val. accuracy, and for STL-10 a ResNet- 10 model that achieves 75% val. accuracy.
We choose simple CNN explainer and variational network chitecture. For CIFAR-10 10 the explainer has 5 convolutional layers of 64 filters and no subsampling. The variational network has 3 convolutional layers of size 32 with 4x4 max pooling layers after each intermediate layer and 2x2 average pooling at the output. For STL-10 the explainer has 5 convolutional layers with 96 filters. The variational network has 5 hidden convolutional layers of sizes [64, 128, 256, 512] with max pooling layers for downsampling and a final global average pooling layer with 10 outputs.
We compare against RelaxSubSample (Xie & Ermon 2019) for 50, 100 for CIFAR-10, and k = 100 for STL.0. For larger subset sizes, we experienced RelaxSubSample to run out of GPU memory. The reason is the large input sizes on STL-10, as well as the fact that RelaxSubSample needs to perform & softmax opera- tions per image, and all must be kept in memory for backpropaga- tion. In contrast, NCPSS is casily scalable, such that we also run our method with & E (400, 500, 600, 700} on STL-10. We choose the relaxation temperatures for RelaxSubSample from (0.1, 0.5, 1.0).
Figure 5: Learning to explain im- age classification with 700 sub- pixels on STL-
8

---

Efficiency comparison. We compare the time taken per epoch for our method and the baseline Gumbel Top-k method RelaxSubSample for increasing subset size & on the learning to explain task on CIFAR- 10, see Table in Appendix E The proposed algorithm, NCPSS, trains almost twice as fast as Relax for A = 50, and twice as fast for k = 100. In general, the runtime was only minimally affected by different subset sizes i and sampling iterations t. Published as a conference paper at ICLR 2023
We show results in Table 2 Overall, neural conditional Poisson sampling outperforms the Gumbel- Top-k RelaxSubSample by a large margin on the same subset sizes, over 10% for CIFAR-10 10 and 8% for STL-10. Furthermore, that NCPSS makes efficient use of the set sizes. Note that in these experiments, the post hoc accuracy of the best model is still below the original model, which can likely be addressed by better explainer or variational network architecture. We provide examples explanations (the negative of the generated mask, for better illustration) of correct predictions by our method in Section 5.2 Finally, for CIFAR- 10 and STL-10, we also experiment with differentiable subset sizes with our method when the average explanation size is regularized to be, e.g., 50 and 100 by adding a term in the loss function as we did for our document classification experiments. Generally, we find that adding a differentiable average subset size constraint leads to worse evaluation accuracy.
see clear increase of performance with larger subset size, indicating
Subset size variation. We show that our method leads to very low variation in the sampled subset sizes on real data with only a few iterations t. We sample 1000 subsets for different input data points and compute the minimum, maximum, and mean subset size for l E {50, 100} and & E {3. 5, 8). E show only a small variation (+44 at t = 8) in subset sizes given t.
Results in Table g in Appendix
5.3 SUBSAMPLING LARGE IMAGES
Last, to showcase the capacity of neural conditional Poisson sampling for large-scale inputs and experiments, we subsample large images for down- stream classification task following Huijben et al. (2019). For this, we create subset of the CelehA-HQ (Lee et al. 2020) dataset with 512x512 images, half of them featuring the eyeglasses attribute and the other half not. The eyeglasses attribute then serves the classification target. The task of the subsampler is to compute a global input mask. We replace the Gumbel sampling layer used by Huijben et al. (2019) with our iterative Poisson sam- pler. We subsample 5, 10 and 15 percent of the pixels which are fed to the downstream classifier. We use a small 6-layer CNN with max-pooling layers for downsampling, final global average pooling layer for the output, and train the model for 80 epochs. We obtain accuracies of 93.4, 95.1 and 95.4 percent for 5, 10 and 15 percent pixels respectively. This experiment is intractable with the method from Huijben et al. (2019) due to high memory usage. Example images are shown in Figure 6 We also experimented with per-instance features for eye glasses classification. Qualitative results for this can be seen in Appendix G.I
Figure 6: 512x512 sub-sampled Celeb HQ images for eye glasses classification. Selected pattern is shown in red.
By contrast, the method from Huijben et al. (2019) is infeasible for such large images since attempts to create the full subsampling matrix, requiring over 27GB of memory for 512x512 12 images and batch size of 10. To make comparison with Huijben et al. 2019 possible, we downscaled images to 64x64, on which NCPSS obtains 2-3% higher accuracy (91.1 v. 89.1 for 15% selected pixels and 89.4% v. 86.6 for 10% selected pixels, see Appendix D
6 CONCLUSION
We presented a method for sampling subset of lt elements from an n element universe. The method is intermediate between Poisson and conditional Poisson sampling by reducing variance in Poisson sampling and generating samples that are close to k-hot. The main limitations of the method are: I) the subset size l is only achieved in expectation, so there is not much advantage gained for very small subsets in terms of complexity, and 2) there are theoretical guarantees for the ttraight gradient. In spite of this, the method is efficient and scalable to sampling of large subset sizes beyond what is achievable by current Gumbel Top-k methods.
9

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENTS
This work is financially supported by Qualcomm Technologies Inc., the University of Amsterdam and the allowance Top consortia for Knowledge and Innovation (TKIs) from the Netherlands Ministry of Economic Affairs and Climate Policy.
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 3o0.:33088332 3432, 2013. URL
http://arxiv. org/ /a////////// / 308..08. 3432
Lennart Bondesson, Imbi Traat, and Anders Lundqvist. Pareto sampling versus sampford and conditional poisson sampling. Scandinavian Journal of Statistics, (3(4);69 2006. ISSN 0303-6898. Publisher: Board of the Foundation of the Scandinavian Journal of Statistics, Wiley.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information- theoretic perspective on model interpretation. In International Conference on Machine Learning. pp. 883-892. PMLR, 2018.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215-222 223. JMLR Workshop and Conference Proceedings, 2011.
Nicola De Cao, Michael Sejr Schlichtkrull. Wilker Aziz, and Ivan Titov. How do decisions emerge across layers in neural models? interpretation with differentiable masking. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 3243-3255. Association for Computational Linguistics, 2020. doi: 10.18653/ 1/20220 htt22220..mmlll.. emnlp-main.266 m62n.262. 262.
Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with reservoir. Information processing letters, 97(5):181-185 2006.
Kartik Goyal, Graham Neubig. Chris Dyer, and Taylor Berg-Kinkpatrick A continuous relaxation of beam search for end-to-end training of neural sequence models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations, In International Conference Learning Representations, 2018.
Hájek and V. Dupač. Sampling from a Finite Population. Statistics Series. M. Dekker, 1981. ISBN 9780824712914.
Iris AM Huijben, Bastiaan S Veeling, and Ruud JG van Sloun. Deep probabilistic subsampling for task-adaptive compressed sensing. In International Conference on Learning Representations, 2019.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where find them: The gumbel-top-k trick for sampling sequences without replacement. In International Conference on Machine Learning, pp. 3499-3508. PMLR, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Cheng-Han Lee, Ziwei Liu, Lingyun Wu, and Ping Luo. Maskgan: Towards diverse and interactive facial image manipulation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning Sparse Neural Networks through L.0 Regularization. In International Conference on Learning Representations, 2018.
Anders Lundquist. Contributions to the theory of unequal probability sampling. phdthesis, Institutio nen för Matematik och Matematisk Statistik, Umeå universitet, 2009.
10

---

Published as a conference paper at ICLR 2023
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computationna Linguistics: Human Language Technologies, pp. 142-150. Association for Computational Linguistics, 2011.
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In Proceedings of the international conference on learning Representations. International Conference on Learning Representations, 2017.
Jack L. Ogus and Donald F. Clark. The Annual Survey of Manufactures: Report Methodology.
Number v. Technical paper. U.S. Bureau the Census, 1971.
Esbjörn Ohlsson. Sequential poisson sampling from a business register and its application to the Swedish consumer price index. Statistiska centralbyrån, 1990.
Max Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient estimation with stochastic softmax tricks. Advances in Neural Information Processing Systems, 33:5691-5704, 2020.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1D144-1122
Michal Pietruszka, tukasz Borchmann, and Filip Graliński. Successive halving top-k operator. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021.
Tobias Plötz and Stefan Roth. Neural nearest neighbors networks. Advances in Neural information processing systems, 31, 2018.
Jason Rennie and Ken Lang. http://gwoon.ccom/////m///eeeee/
The 20 newsgroups data
set.
URL:
2008.
Yves Tillé. Sampling algorithms. Springer, 2006.
Sang Michael Xie and Stefano Ermon. Reparameterizable subset sampling via continuous relaxations. In IJCAI, 2019.
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. Advances in Neural Information Processing Systems, 33:20520-200 20531, 2020.
Jiancheng Yang. Qiang Zhang, Bingbing Ni, Linguo Li, Jinxian Liu, Mengdie Zhou, and Qi Tian. Modeling point clouds with self-attention and gumbel subset sampling. arXiv: 933450335 [cs), 2019.

---

Published as a conference paper at ICLR 2023
A PSEUDOCODE FOR ITERATIVE POISSON SAMPLING
Algorithm 4 Iterative Poisson Sampling Pseudocode
Require: Input E IR: integer, integer;
12: Function
Sample-Approx-K-Hon
(p.
Set 0, f 1, 04, mask
k.mask)
1 pin = kin = k:
13: Set e = Σ p- mask, n = Σ mask
2: while t do
14: k <= then
3:
8 == Gample-Approx-A K- K-Hot(p, k mask)
15: Set kp/c
4:
Set 5 =S+ f f.s
16: else
5: Set E
17: Set (n (1 p))(nn
6:
if l <= r then
18: end
7:
Set f -1,mask
s.p
19: Sample independently from q
pin, = r- kin
20: k <= c then
8:
else
21: Return mask
9:
Set f = 1, mask = 1 1-8,p 8. = pin. h:
22: else
kin
23: Return (1 1-s) 5) mask
10:
end if
24: end if
end while
25: EndFunction
B PROOF OF PROPOSITION 3.1
Proposition 3.1. Let S. E (0. 1 denote the subset and qi bounding the probability at step i in the iterative Poisson sampling procedure. Then after T iterations have V Var([Srl) S Var([Si)) II: qs, where Var([Sil) is the Poisson sampling variance. Assuming that the probability bound is bounded away from 1, i.e., < -e - > O, the procedure obtains exponential decrease in variance with the number of steps T.
Proof. By design we have that E[[S: S:-1] k, where & is the required subset size. Note that V Var([S]] is the plain Poisson sampling subset size variance. Using the following upper bound for the variance of the binomial distribution,
Varl;n. = =pp(1 p) S np,
we have
Var((S][[Sia-i) 1n--ss - -1:--1)4
Combining with [[X = Var(XX + 2 we
Var([S]] S1.12) E[Vari [S|| S1:11))
(3)
< [nk n| a|Si-1l - k|S 1S 11n-22
| gb
(4)
s q: Var( S11-2).
(5)
Unrolling from T to 1 we get
T Var([Srl) S Var((S:) II 9:-
2=2
Combined with the assumption that d bounded away from 1, the right hand side gives exponential decay in the Poisson sampling variance Var(Si) over I' steps.
Conditional Poisson sampling would need on average 1/(2) (1-pp(111p01 (1-p)"=* =)= steps given that the success probability for size k in each sample is (1)p nk
12

---

Published as a conference paper at ICLR 2023
C CORRECTION FOR INCLUSION PROBABILITY
Given desired probabilities Pt such that Σ P: = k. the conditional Poisson design does not lead to inclusion probabilities N; such that T, P;- However, H, p; and the approximation improves when d :- E, p1 pp)) is large Hājek & Dupač (9881). Bondesson et al. (2006); Lundquist (2009) develop corrections p for sampling probabilities to improve the approximation relative desired inclusion probabilities p, depending whether d large small. For large d, the suggested correction uses p such that
Pt
1/2 d
exp
(6)
Pi
where a is chosen so that E; p. cases is to use 7/4 such that
k. Another correction that subsumes the large and very small
p/ p
ps Pi
exp aresinh 11/2 Pi
a ))
a
where is recommended by Lundquist (2009) to be chosen as = 1/2 d2/2. For our experiments we found the correction from equation work better than the one from equation ( which we choose to use. In general. in our experiments, we find the corrections to be useful only when is small and & less than n//2. Otherwise, for large
inclusion probabilities were approximated quite well by the uncorrected probabilities in our experiments. We experimentally validate the inclusion probability correction in Appendix
D SUBSAMPLING COMPARISON
We compare the performance of method on image subsampling task for downstream classifi- cation with deep probabilistic sampling (DPS) Huijben et al. (2019) which uses Gumbel sampling for sampling subsets. We use the CelebA dataset for this experiment. Since we find that the DPS method is infeasible to use on large images due to its high memory requirement, we compare on images downscaled to 64x64. We prepare the dataset described in Section (.3 and build classifier for the eyeglasses attribute. We use 5 layer CNN with maxpooling downsampling layers and train for 100 epochs. For DPS we use temperatures of 0.5 and
Table 3; Subsampling comparison on CelobA eyeglasses attribute classification evaluation set
Model
Percent Pixels
Percent Evaluation Accuracy
NCPSS
10
89.4
DPS Huijben et al.
2019
10
86.6
NCPSS
15
91.1
DPS Huijben et al.
2019
15
89.1
Table 4: Subsampling performance on CelebA-HQ 512x512 images for eyeglasses attribute classifi- cation on the evaluation set
Model
Percent Pixels
Percent Evaluation Accuracy
NCPSS
5
93.1
NCPSS
10
95.1
NCPSS
15
95.4
D.1 TIMING COMPARISON
Our method is significantly comparison for the subsampled eyeglasses classification experiment described above with 64x64 images. The times are for 80 epochs.
efficient than Top-k methods for large k. Below provide timing
13

---

Published as a conference paper at ICLR 2023
Table 5: Training time comparison CelebA 64x64 images for subsampled eyeglasses attribute
classification
Method
Pixels
Time/80 epochs
NCPSS
10%
41 minutes
DPS Huijben et al. (019
10%
3 hours
NCPSS
15%
41 minutes
DPS
Huijben et al. (0119)
4.4 hours
E FURTHER VALIDATION OF THE METHOD
In this section we verify some properties of the proposed method. First, we verify that the actual inclusion probabilities are close the desired probabilities and the conditions under which the correction described in Section intrioonimmproeess the approximation. Second, we verify that the method indeed reduces variance the subset size at the exponential rate suggested by Proposition 3.1
E. VERIFYING THE APPROXIMATION FOR INCLUSION PROBABILITIES
First we verify that our proposed method generates k-hot samples with probabilities close to the prescribed probabilities. We generate random probability vectors, p, of dimension chosen from (100, 500} that are normalized to sum to 1. Next we generate 1000 k-hot vectors using our method both with and without the correction described in Appendix C We estimate the inclusion probability by averaging across the 1000 k-hot samples for each dimension, denoting the empirical probabilities by p. We compute the mean squared error as (p: - p./k)?. We repeat the procedure for values of k E {10, 20, 30, 40, 50, 60). The root mean squared (RMS) error with and without the correction for various values of & is shown in Table
Table 6: Root mean squared error for inclusion probabilities
k (n 100)
Method
10
30
40
50
60
NCPSS
0.0165
0.0095
0.0071
0.0042
0.0030
0.0043
NCPSS+cr.
0.0116
0.0082
0.0060
0.0037
0.0027
0.0043
& (n 500)
Method
50
100
1.50
200
250
300
NCPSS
0.0048
0.0030
0.0021
0.0015
0.0017
0.0082
NCPSS+er.
0.0045
0.0028
0.0020
0.0015
0.0017
0.0369
From the table we find that the empirical inclusion probabilities are already quite close the desired probabilities without the correction for the chosen values of n and k. The largest RMS error is about 0.016 for & = 10 and n = 100 and the error generally decreases for large values of up to n/2. We also find from the table that the correction helps more for smaller n but only for values of k less than about n/2 beyond which makes the error worse. Since the results show that the correction can help improve the approximation when & is small relative n, treat the correction modeling choice depending on the experiment.
E.2 SUBSET SIZE VARIANCE
We examine the variance of the size of the subset selected with our method and its relation with
the number of iterations t performed by Algorithm 3 We choose probability vector of n = 3000 dimensions and choose 1000 subsets of size k = 300 and run the algorithm for t 1 and The results show
iterations. Histograms of the subset size distribution are shown in Figure | significant decrease in variance with small number of iterations.
14

---

Published as a conference paper at ICLR 2023
E.3 EFFICIENCY COMPARISON
Table 7: Time per epoch in seconds versus & on CIFAR-10
k:
Baseline
Method
50
100
150
200
RelaxSuhSample
22s
28s
32s
10s
NCPSS
13s
13s
13s
13s
13s
10s
E,4 SUBSET SIZE VARIATION
Table 8: Variation in subset size with number of iterations & on CIFAR-10.
50
100
Mean
Min
Max
Mean
Min
Max
3
49.9
45
60
99.7
94
105
49.95
47
54
100.1
95
104
50.01
49
99.9
96
102
E.5 KNN CLASSIHICATION
We show that our method is also competitive against other methods when using smaller subset sizes (k=9) on a stochastic nearest neighbors classification task with deep features Grover et al. (2018): Xie Hrmon (019)). We use the same setup as Xie et al. (2020) except that cosine distance rather than Fuclidean distance, since our method requires the weights of the elements to be normalized to (0, 1).
We use = neighbours and compare against RelaxSubSample NeuralSort Grover et al. 2018)) 8), SOFT Top-k Xie et al. (2020). The results shown Table From the result see that although we do slightly worse on MNIST, we outperform all baselines except the deterministic SOFT Top-k and are on-par with SOFT Top-k on CIFAR- 10. The results show that our method performs well and on-par with other similar methods, also in the regime of small subset sizes k.
Table 9: kNN Test Set Classification Accuracy for It = 9
Model
MNIST CIFAR-10
kNN Grover et al. 2018
97.2
35.4
KNN+PCA Grover
2018
97.6
40.9
kNN+AF Grover al. 2018)
97.6
44.2
ANN+RellxxSuhSampl Xie & Ermon 2019
99.3
90.1
&Nu Grover et al 2018
99.5
90.7
+NN Xie al. (002
99.3
92.2
KNN+Sofi- Topk
al. 2020
92.6
kNN+NCPSS
99.2
92.5
F LEARNING TO EXPLAIN: TEXT EXAMPLES
In the following show examples of explanations generated by method for the 20Newsgroups dataset with differentiable set size. The mean size was set to 50 words. This allows the model to choose per-instance explanation sizes.
15

---

Published as a conference paper at ICLR 2023
in article liu se writes intersection between line and polygon by dave tom from graph- ies cornell edu in recent years many geometric problems have been successfully new language called postscript see postscript language by adobe systems incorporated isbn co so given line and polygon we can write postscript program that draws the line and the polygon and then outputs the answer by oulput we mean the program command called which actually prints page of paper containing the line and the polygon quick examination of the paper provides an answer to the reduced problem and thus the original problem in modern postscript the point in polygon problem can be solved even more easily to wit title point in polygon creator allen ab ce purdue edu for the of comp graphics humor sense thereof this program will test whether point is inside given polygon currently it uses the even odd rule but that can be changed by replacing with these are level operators so if you ve only got level you re out of luck the result will be printed on the output stream caution only accurate to device pixels put huge scale in first if you aren sure point to test put and here of polygon in counter order put array of pairs of here get pop length roll sub pop yes no
Class: comp.graphics, Predicted: comp.graphics, Words Selected: 13/223, Total Token Selected: 13
in article apr sps mot com email sps mot com writes their problem wasn giving them any more money the finance guy then brought in the manager on duty who proceeded to give me hard time reminded him that was the customer and didn think should be treated like that and that he didn back off he could forget the whole deal he made some smart remark so told him where he could stick it back my check and left needless to say they were not pleased by the turn of events that nothing when friend of mine went shopping for small sedan few years ago she brought me along as token male so the wouldn give her the treatment her first choice was mazda and second choice was nissan we went to mazda dealership and described what we wanted we started negotiating on the price and the kept playing the let me run this price by the sales manager after playing the good salesman bad salesman game we finally told him that if he didn have the authority to negotiate price perhaps we should be speaking directly to someone who did he brought in the sales manager who proceeded to dick us around with every trick in the book read don get taken every time for list fimally after playing few more rounds of you 11 have to work with us on this price also known as each time you come up thousand dollars we Il come down ten the gave signal to his two sales stood up and said well we can come down any more so guess we can help you and they out of the room leaving us sitting in the salesman office all by ourselves hmm read that sometimes bug their own offices so they can leave and listen in on discussing the sales offer and mentioned this to my friend while we were sitting there wondering why they would leave us in the office instead of showing us to the door for lack of anything better to do picked up the phone on the desk and called another mazda dealership asked for salesman and began discussing what kind of price they would consider few sentences into the conversation mr broke into the line and began telling me how rude he thought it was that would call another dealership from his phone said that since he announced that our business was over he shouldn care and every time tried to talk to the other sales guy the sales manager would out our voices with his own how did he know that was using the phone anyway finally hung up and we headed out of the sales manager and come out of little room and he begins to us again we say that we won bother him anymore we re going next door to the nissan dealership then comes the part wish could have as we go out the front door the sales manager across the entire customers and all go ahead you deserve to buy nissan so my friend bought just so the guilty won go ll mention that the sales manager name was gary from his manner his refusal to come down to reasonable price and his anger at the end my guess is that he had bet our original salesman who was young that he be able to get at least dollars out of us and he was that we wouldn fall for his tricks
Class: rec.autos, Predicted: rec.autos, Words Selected: 62/583, Total Token Selected: 64
16

---

Published as a conference paper at ICLR 2023
previously wrote yeah the phillies played over their heads almost the whole year but it all caught up to them in one game streak am as old as man and was big phillies fan at the time age september is still painful thing to remember but can tell you that the phillies never led the league by that year going by memory alone believe their biggest lead was games and they were ahead when the famous game losing streak began streak during which it seemed that they found just about every way to lose known to man anyway think they just before the end and won their last couple games and were still in the thing until the final day but finished tied with the giants one game out and didn the dodgers or somebody else finish two games back that has to be one of the closest last minute ever ok you guys up my childhood memories so went and did some research on the final month or so of the season it turns out that my were pretty darn accurate at least as far as the phillies record goes on september this was the top of the standings gb philadelphia cincinnati st louis san francisco this game by game description of the remainder of the phillies season date score opponent lead pitcher starting and winner loser houston houston short houston san francisco win san francisco san francisco short los angeles los angeles wise los angeles st louis cardinals take over place from cincinnati st louis short san francisco san francisco giants move into tie for nd with st louis san francisco cardinals back in sole of nd place houston short houston houston los angeles wise los angeles short los angeles los angeles reds move back into tie for nd with cardinals well so far so good for the phillies but now all falls apart cincinnati reds take sole of nd place cincinnati short cincinnati milwaukee milwaukee short cards now back in rd giants in th milwaukee milwaukee lose games in days reds take over st cardinals back in rd st louis short cardinals take over nd place drop to rd louis reds and cardinals now fied for st st louis cardinals take game lead over reds cincinnati short phillies game losing streak cards lead reds by game did not play cards lose to mets reds tied for st game back cincinnati cards beat mets take first by from reds and phillies what finish and the final standings were gb st louis philadelphia cincinnati san francisco now it doesn appear to me that phillies pitchers and short were really least by the four man rotation standard of the day until well along into the game losing streak at which time was probably desperate for win at any cost because the phillies substantial lead had the way they were used at that time may have made the problem worse although had one of his games of the year in the final day of the reds that cost the reds share of the pennant pitched complete game six hitter striking out five and walking one it would be to see though how the total innings for the year for and short up against the rest of the league also notice that the phillies played every day from at least september through october while they didn play substantially more games than the other teams the other teams each had couple days off during that stretch eric smith netcom com com ci
Class: rec. baseball, Predicted: rec. pec.sport. baseball, Words Selected: 77/594, Total Token Selected: 81
17

---

Published as a conference paper at ICLR 2023
in article ponder jesse writes hi have you used mac system or if the answer positive you would know if ms windows mature os this is silly is unix mature os depends on who you ask and how you define mature system is if anything less mature than windows days ago people that ms windows is not real os can see why they have such question ms windows many people microsoft mac but did lousy job for example you can not create hierarchy groups there is no way to create group in group if you know how please tell me so why do you need something like to create groups under the apple menu everyone knows that apple menu items are of the program manager if you want program launcher there are lots available documentation it not easy to find the reason why causes an error and this is easy on mac give me break having spent hours moving system extensions around and the mac to see why certain app crashes all the time find this group file after group users have to use file manager to delete files but if users forget to delete some related files the disk will be full of nonsense files oh great ever hear of wonder why apple implemented them share problem once you create two windows doing and editing in some language good editor there will be sharing problem you just can not open or save the program if is loaded it makes sense to prevent from saving but not opening eh don follow it by no means easy to satisfy everybody but if microsoft want to keep their they should evaluate the user interface more carefully before products distribute why is it that find the mac desktop incredibly annoying whenever use it no flame please yeah right you post flame bait yet ask for no flames the only thing worse than ala internet silver ucs indiana edu frog is frog ala bitnet
Class: comp.os.ms windows.iss; Predicted: comp windows misc, Words Selected: 27/334, Total Tokens Selected: 27
am very interested in hearing from all of you who are using or implementing interactive applications what types of widgets you would like to have in your applications widget is usually located in the same scene as other objects of the application it may let you manipulate application data the camera objects in the scene and so on or view the status of the application or objects via the widget shape color position orientation and so on or do whatever missed but you think is possible for example widget can be virtual shown as partially transparent sphere super imposed on the object to be feedback widget can be with ends to objects the length of the changes as the objects move and value is shown on the indicating the distance widget can provide both manipulation and feedback for example the can be used to change the distance between the objects along its own axis please mail me or post your opinions on interaction the information gathered will help me design ui construction tool your help is very much appreciated tony lau cs ubc ca se student dept of computer science
Class: comp.graphics, Predicted: comp.windows.x, Words Selected: 44/190 Total Token Selected: 48
18

---

Published as a conference paper at ICLR 2023
G
IMAGE CLASSIFICATION EXAMPLES
G.1 CELEBA
Figure Per-instance examples on Celeba with 150x 150 images for eye glasses attribute classification with 500 pixels.
G.2 CIFAR-10
Figure 8: Learning to explain image classification with 100 sub-pixels on CIFAR-10.
G.3 STL-10
19

---

Published as a conference paper at ICLR 2023
Figure 9: Learning to explain image classification with 700 sub-pixels on STL-10.
20

---

Published as a conference paper at ICLR 2023
Figure 10: Learning to explain image classification with 800 sub-pixels on STL-10.
21


Reviews:
[{"review_id": "v6N-r_7sNwr", "reviewer": "Reviewer_ZXrw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper describes a method for subset sampling based on conditional Poisson sampling, called neural conditional Poisson subset sampling.  This approach builds on the general conditional Poisson sampling approach, which samples each element in the subset independently, and conditions this procedure to return subsets of exactly $k$ elements.  Conditional Poisson sampling has some weaknesses, including high computational complexity, and that it is not differentiable and thus cannot be included in differentiable models.  The proposed neural conditional Poisson subset sampling approach addresses these issues, allowing for efficient sampling of large subsets, and is fully differentiable.", "summary_of_the_review": "While the approach described in this paper is relatively simple and straightforward, it is in fact more scalable than a number of prior approaches for subset sampling, and also has the advantage of being fully differentiable.  This paper is well written, and the empirical results are convincing.  Taken together, this is a good paper and should be accepted. \n", "strength_and_weaknesses": "Strengths:\n* The proposed approach is scalable, allowing for efficient sampling of large subsets.\n* The proposed approach is fully differentiable, allowing it to be incorporated into differentiable models that are trained via gradient-based learning methods.\n* The experiments in this paper show strong empirical evidence that the proposed approach outperforms competing approaches in terms of both predictive performance and runtime performance, sometimes by a significant margin.\n\nWeaknesses:\n* The proposed neural conditional Poisson subset sampling assumes that the $k$ elements for a sampled subset are drawn IID from the universe of $n$ elements.  That is, it assumes that there are no interactions (correlations) between elements within a subset.  This is a significant limitation.  Scenarios involving text or image data may often involve interactions between elements within a subset, which may not be represented well with the approach in this paper.\n* No theoretical analysis of the runtime complexity of the proposed algorithm (Algorithm 3) is provided in the paper.  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "er_yLvCYKwF", "reviewer": "Reviewer_oHmW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work aims to propose a differentiable and scalable k-subset sampling algorithm based on conditional Poisson sampling. The scalability comes from the conditional Poisson sampling scheme where each instance is sampled independently such that the vectorized complexity of the proposed algorithm is independent of the subset size k. The differentiability is achieved by the use of a straight-through gradient estimator. It further carries out experiments on learning to explain text and image, image subsampling, and k-nearest neighbor search.", "summary_of_the_review": "The proposed approach demonstrates good scalability. My main concern is that the sampled subset size is not guaranteed.", "strength_and_weaknesses": "I find the most compelling part of the proposed algorithm is scalability as shown in the subsampling large image experiment where some baselines fail. The technical details seem solid to me. Still, there are a few concerns:\n- My main concern is that the subset size being k is not a hard constraint. Even though Figure 1 shows that increasing the number of iterations in the conditional Poisson sampling process might mitigate this issue and result in a distribution over subset sizes being more concentrated on the desired subset size, this is at the price of high computational cost and it is not guaranteed that all the sampled subsets would have their subset size being exactly k. While this guarantee is achieved by the other existing subset sampling approaches such as RSS.\n- I wonder for the conditional Poisson sampling, what is the expected number of iterations to sample a subset with a size being exactly k? Besides, while Proposition 3.1 is about the decreasing rate of variance, I wonder if this result can be generalized to the case of arbitrary input probabilities instead of the equal input probability assumption.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bRDAr-3b3O", "reviewer": "Reviewer_iTJN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new approach to sampling subsets from a set of $n$ elements using an iterative version of Poisson sampling. This avoids the high variance of standard Poisson sampling and the high cost of conditional Poisson sampling by iteratively adding or deleting elements a finite number of times. The lower variance and computational efficiency of the approach are also empirically validated across a range of experiments.", "summary_of_the_review": "The paper introduces a novel approach for subset sampling that has low variance and is significantly more scalable than prior approaches. The approach is theoretically principled and outperforms baselines on a range of empirical experiments. It would be interesting to see some convergence rates for the deviation of the subset size from the expected size in a future work.", "strength_and_weaknesses": "Strengths:\n\n1. The approach is elegant, intuitive and also theoretically proved to have low (exponentially decaying) variance.\n2. There are clear empirical improvements over prior work in a wide range of applications including some applications like subsampling high resolution images which are computationally infeasible with prior work (due to high memory requirements).\n\nWeaknesses:\n\n1. The approximate (straight-through) gradients may be too far from the true gradients. While straight-through gradients appear to be doing well in the current set of experiments, will it be feasible to explore some of the other gradient estimators mentioned, even just for the same tasks, to comment more conclusively on the right estimator?\n\n2. The approach lacks a discussion of convergence rates. Specifically, it would be interesting to see some tail bounds on the deviation from the mean after T iterations but it is fine to leave that for future work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "aHCqXH97GMk", "reviewer": "Reviewer_H9tb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new technique for subset sampling via conditional Poisson sampling. Given a universe of $n$ elements and inclusion probabilities $p_i$ for each element $i$, the problem is to sample a subset of size $k$ that respects the inclusion probabilities.\n\nPoisson sampling samples each element with probability $kp_i$, leading to set of size $k$ in expectation, while conditioninal Poisson sampling would repeat unconditional Poisson until a set of size $k$ is achieved. Both of these have limitations, as uncoditinoal sampling only produces a set of size $k$ in expectation ( and may have high variance) and if $k p_i \\geq 1$, element $i$ is always included; conditional sampling may not respect the inclusion probabilities.\n\nThis paper suggests techniques for handling these various issues, along with a differentiable variant that can be used in a gradient-base learning framework. Additionally, the subset size $k$ can also be made differentiable, which is useful when the exact subset size is not known and needs to be optimized, for e.g., when selecting features that are most important for downstream classification models.", "summary_of_the_review": "My score is based primarily on the fact that the proposed approach is:\n- modular\n- quick\n- flexible in choice of subset size $k$, and also allows for optimizing $k$ in a differentiable manner\n- can be used for selecting interpretable features for downstream classification tasks\n\nThat being said, I am not an expert in subset selection and do not know much about current state of the art, and my score of weak accept is based on my current understanding of the paper. I'm happy to increase my score based on the author feedback and discussion.", "strength_and_weaknesses": "Strengths:\n- The algorithm is quite elegant and simple. It also remarkably modular, as it can be used for a variety of downstream tasks, such as feature selection for explainability of downstream classifiers.\n\n- The authors identify flaws with the Poisson sampling approach, and show algorithms that can overcome said challenges.\n\n- I am not familiar with the state of the art for subset selection, but it appears that the proposed algorithm performs at least as well as competing approaches, is quicker, and is more flexible with respect to choice of $k$ or optimizing $k$.\n\nWeaknesses:\n- This motivation for using Poisson sampling requires some more work. There exist exact sampling methods such as weighted reservoir sampling (https://en.wikipedia.org/wiki/Reservoir_sampling#Weighted_random_sampling) that do not suffer from the problems experienced conditional  / unconditional sampling. Since the differentiable part of the Poisson network is an application of the Gumbel-Softmax trick to replace the differentiation of Bernoulli r.v.s, why not use the same technique for reservoir sampling?\n\n- The experiments section is nice, but it seems like the three experiments are really variations of the same problem, i.e., selecting a mask that helps choose features that explain a text / image / face classifier. This surely cannot be the only application of subset selection --  what are the other standard baseline applications of subset selection? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster