Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

group_bootstraps takes unusually long when there are rare classes #466

Open
StevenWallaert opened this issue Jan 31, 2024 · 8 comments
Open

Comments

@StevenWallaert
Copy link

Not really a bug per se but I want to report that:

I found it impossible to use group_bootstraps with a dataset of n around 10000, and the number of groups around 500, because it takes so long. I'm not sure but I have a feeling this shouldn't take that long.

@EmilHvitfeldt
Copy link
Member

Hello @StevenWallaert Do you mind clarifying a bit? Below I was able to apply group_bootstraps() on a data.frame with 10000 rows and 500 groups. Does this mirror your setup?

library(rsample)
library(modeldata)
library(dplyr)

ames <- slice_sample(ames, n = 10000, replace = TRUE)

ames$group <- sample(1:500, size = 10000, replace = TRUE)

tictoc::tic()
group_bootstraps(ames, group)
#> # Group bootstrap sampling 
#> # A tibble: 25 × 2
#>    splits               id         
#>    <list>               <chr>      
#>  1 <split [9991/3667]>  Bootstrap01
#>  2 <split [9998/3715]>  Bootstrap02
#>  3 <split [10007/3741]> Bootstrap03
#>  4 <split [9991/3528]>  Bootstrap04
#>  5 <split [9996/3837]>  Bootstrap05
#>  6 <split [10005/3593]> Bootstrap06
#>  7 <split [9998/3668]>  Bootstrap07
#>  8 <split [10007/3974]> Bootstrap08
#>  9 <split [10001/3729]> Bootstrap09
#> 10 <split [10001/3612]> Bootstrap10
#> # ℹ 15 more rows
tictoc::toc()
#> 7.219 sec elapsed

@StevenWallaert
Copy link
Author

Hey, thanks for your reply.
I tried your code above, and got following result:

> tictoc::tic()
> group_bootstraps(ames, group)
# Group bootstrap sampling 
# A tibble: 25 × 2
   splits               id         
   <list>               <chr>      
 1 <split [10002/4060]> Bootstrap01
 2 <split [10001/3692]> Bootstrap02
 3 <split [10004/3750]> Bootstrap03
 4 <split [10008/3592]> Bootstrap04
 5 <split [10001/3844]> Bootstrap05
 6 <split [9993/3562]>  Bootstrap06
 7 <split [10008/3613]> Bootstrap07
 8 <split [10002/3590]> Bootstrap08
 9 <split [10004/3675]> Bootstrap09
10 <split [9994/3379]>  Bootstrap10
# ℹ 15 more rows
# ℹ Use `print(n = ...)` to see more rows
> tictoc::toc()
11.04 sec elapsed

However, when I do the following with df as my datatframe, I get:

> tictoc::tic()
> df %>% 
+   group_bootstraps(group = ID)
# Group bootstrap sampling 
# A tibble: 25 × 2
   splits               id         
   <list>               <chr>      
 1 <split [10605/3971]> Bootstrap01
 2 <split [10613/3715]> Bootstrap02
 3 <split [10611/3827]> Bootstrap03
 4 <split [10608/3748]> Bootstrap04
 5 <split [10611/3605]> Bootstrap05
 6 <split [10611/3707]> Bootstrap06
 7 <split [10594/3907]> Bootstrap07
 8 <split [10600/4025]> Bootstrap08
 9 <split [10627/3705]> Bootstrap09
10 <split [10613/3780]> Bootstrap10
# ℹ 15 more rows
# ℹ Use `print(n = ...)` to see more rows
> tictoc::toc()
120.94 sec elapsed

roughly ten times longer. My df is nothing special: 10607 rows, 17 columns (ames is 75 columns).

Problem is that I need to go to 2000 resamples and I don't have a clue how long it will take. I usually abort because I'm afraid it will take too long. Maybe the option of a progress bar would be helpful?

@mikemahoney218
Copy link
Member

mikemahoney218 commented Feb 13, 2024

Do you have a ton of groups? It seems like something in the per-group implementation is inefficient (as the person who wrote that code, I'd believe it 😛 ) and the function takes dramatically longer as the number of groups increases:

bench::press(
  n = c(2, 5, 10, 50, 100, 1000, 2000),
  {
    df <- modeldata::sim_noise(
      num_samples = 10607, 
      num_vars = 16,
      outcome = "classification", 
      num_classes = n
    )
    bench::mark(
      rsample::group_bootstraps(df, class)
    )
  }
)
#> # A tibble: 7 × 7
#>   expression                    n      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr>                <dbl> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 rsample::group_bootstrap…     2  61.68ms  77.85ms  10.1       78.75MB  28.5   
#> 2 rsample::group_bootstrap…     5  71.09ms 143.22ms   8.43       75.5MB  30.3   
#> 3 rsample::group_bootstrap…    10   55.7ms  82.39ms  10.9       75.76MB  30.8   
#> 4 rsample::group_bootstrap…    50  70.44ms  83.85ms  11.2       82.37MB  28.0   
#> 5 rsample::group_bootstrap…   100 227.88ms 256.82ms   3.89     103.97MB  17.5   
#> 6 rsample::group_bootstrap…  1000    1.55m    1.55m   0.0107     7.27GB   0.430 
#> 7 rsample::group_bootstrap…  2000    12.1m    12.1m   0.00138   46.19GB   0.0565

Created on 2024-02-13 with reprex v2.0.2

(I see now you said 500 groups -- I'm wondering if they're unbalanced, and the issues come up when some groups are particularly small)

@mikemahoney218
Copy link
Member

Yeah, think the cause might be unbalanced classes (look at the difference in memory usage, wowza):

set.seed(1107)
df <- modeldata::sim_noise(
  num_samples = 10607, 
  num_vars = 16
)

df$group_1 <- sample.int(500, 10607, TRUE)
df$group_2 <- sample(c(
  rep(1, 4243), 
  rep(2, 4243), 
  sample.int(2121, 2121, TRUE)
), 10607)

bench::mark(
  rsample::group_bootstraps(df, group_1),
  rsample::group_bootstraps(df, group_2),
  check = FALSE
)
#> Warning: Some expressions had a GC in every iteration; so filtering is
#> disabled.
#> # A tibble: 2 × 6
#>   expression                             min median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr>                           <bch> <bch:>     <dbl> <bch:byt>    <dbl>
#> 1 rsample::group_bootstraps(df, group… 12.2s  12.2s   0.0820     1.69GB   0.164 
#> 2 rsample::group_bootstraps(df, group…  7.4m   7.4m   0.00225   29.02GB   0.0901

Created on 2024-02-13 with reprex v2.0.2

@mikemahoney218
Copy link
Member

mikemahoney218 commented Feb 13, 2024

Attached is a profile (readable via profvis::profvis()) of group_bootstraps(df, group_2). Almost all of the time is being spent subsetting freq_table here:

image

Looking at the source of balance_prop_helper(), I see a comment that suggests what's going wrong:

balance_prop_helper <- function(prop, data_ind, v, replace) {

  freq_table <- vec_count(data_ind$..group, sort = "location")

  # Calculate how many groups to sample each iteration
  # If sampling with replacement,
  # set `n` to the number of resamples we'd need
  # if we somehow got the smallest group every time.
  # If sampling without replacement, just reshuffle all the groups.
  n <- nrow(freq_table)
  if (replace) n <- n * prop * sum(freq_table$count) / min(freq_table$count)
  n <- ceiling(n)

  purrr::map(
    seq_len(v),
    function(x) {
      row_idx <- sample.int(nrow(freq_table), n, replace = replace)
      work_table <- freq_table[row_idx, ]
      cumulative_proportion <- cumsum(work_table$count) / sum(freq_table$count)
      crosses_target <- which(cumulative_proportion > prop)[[1]]
      is_closest <- cumulative_proportion[c(crosses_target, crosses_target - 1)]
      is_closest <- which.min(abs(is_closest - prop)) - 1
      crosses_target <- crosses_target - is_closest
      out <- work_table[seq_len(crosses_target), ]
      out$assignment <- x
      out
    }
  ) %>%
    list_rbind()
}

That n calculation is the problem. If you're working with a table that has 10607 rows and 500 groups, the worst case scenario for bootstrapping happens when a group has only one member, where n becomes 500 * 1 * 10607 / 1 == 5303500. That means for each bootstrap iteration, we're generating a 5,303,500 row data frame (before throwing out almost all of it), which becomes quite the performance hit.

So I think it would make sense to not do this -- get rid of the n over-sampling, and instead sample only the necessary number of times groups should be replicated.

Few other notes:

  • I think this only impacts bootstrapping, as n only gets inflated if replace = TRUE
  • If feasible, you might also consider lumping your smallest groups together into an "other" category, which should speed this up

group_bootstraps.zip

@mikemahoney218 mikemahoney218 changed the title group_bootstraps takes unusually long group_bootstraps takes unusually long when there are rare classes Feb 13, 2024
@mikemahoney218
Copy link
Member

Changing the helper to append rows is dramatically faster:

balance_prop_helper <- function(prop, data_ind, v, replace) {

  freq_table <- vec_count(data_ind$..group, sort = "location")
  n <- nrow(freq_table)

  purrr::map(
    seq_len(v),
    function(x) {
      row_idx <- sample.int(nrow(freq_table), n, replace = replace)
      work_table <- freq_table[row_idx, ]
      cumulative_proportion <- cumsum(work_table$count) / sum(freq_table$count)

      # if bootstrapping with small groups,
      # it's possible to repeatedly sample only small groups,
      # meaning you construct bootstrap sets with too few observations
      #
      # so here we loop until we've gotten the right number of groups
      while (max(cumulative_proportion) <= 1) {
        row_idx <- sample.int(nrow(freq_table), n, replace = replace)
        work_table <- rbind(work_table, freq_table[row_idx, ])
        cumulative_proportion <- cumsum(work_table$count) / sum(freq_table$count)
      }

      crosses_target <- which(cumulative_proportion > prop)[[1]]
      is_closest <- cumulative_proportion[c(crosses_target, crosses_target - 1)]
      is_closest <- which.min(abs(is_closest - prop)) - 1
      crosses_target <- crosses_target - is_closest
      out <- work_table[seq_len(crosses_target), ]
      out$assignment <- x
      out
    }
  ) %>%
    list_rbind()
}

That said, I haven't checked this to make sure it actually works in all the ways we care about -- CI suggests it maybe makes us slightly worse at matching strata, and it triggers a new "many-to-many" warning in dplyr::right_join(). I'd need to spend more time digging in to get this over the line (but if anyone gets a chance to look first, hopefully this helps!)

@StevenWallaert
Copy link
Author

Yes indeed, I have many small groups (between 1 and 120 members, 90% between 3 and 40 members). For now I work around by sampling group ids with replacement and then join the original tibble.
I'm not sure I entirely understand the n calculation issue (but that is ok).
The suggestion to lump groups together won't work for constructing percentile confidence intervals (as the bootstrapping should try to replicate the original sampling procedure as much as possible). However, for things like model selection the suggestion is probably fine.

@PalimPalimPalim
Copy link

PalimPalimPalim commented May 16, 2024

I have observed the same behaviour and my workaround is using tidyr nest and unnest.

dat <- tibble(x = rep(1:1000, 2), y = 1:2000) 

f <- function(df, column){
  tibble(
    "estimate" = mean(pull(df, {{column}})),
    "term" = "mean"
  )
}


# Version 1 using rsample::group_bootstraps
start_time <- Sys.time()

dat %>%
  group_bootstraps(group = x, times = 10) %>%
  mutate(mean_stats = purrr::map(splits, ~ f(analysis(.), y))) %>% 
  int_pctl(mean_stats)

print(difftime(Sys.time(), start_time, units = "secs"))

# Version 2 using tidyr nest and unnest
start_time <- Sys.time()
dat %>%
  nest(.by = x) %>%
  bootstraps(times = 10) %>%
  mutate(mean_stats = purrr::map(splits, ~ f(unnest(analysis(.), data), y))) %>% 
  int_pctl(mean_stats)

print(difftime(Sys.time(), start_time, units = "secs"))

Based on my understanding of group_bootstraps both versions should be equivalant, but the version using nest and unnest is roughly 20 times quicker.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants