Categories
Offsites

torch time series, final episode: Attention

This is the final post in a four-part introduction to time-series forecasting with torch. These posts have been the story of a quest for multiple-step prediction, and by now, we’ve seen three different approaches: forecasting in a loop, incorporating a multi-layer perceptron (MLP), and sequence-to-sequence models. Here’s a quick recap.

  • As one should when one sets out for an adventurous journey, we started with an in-depth study of the tools at our disposal: recurrent neural networks (RNNs). We trained a model to predict the very next observation in line, and then, thought of a clever hack: How about we use this for multi-step prediction, feeding back individual predictions in a loop? The result , it turned out, was quite acceptable.

  • Then, the adventure really started. We built our first model “natively” for multi-step prediction, relieving the RNN a bit of its workload and involving a second player, a tiny-ish MLP. Now, it was the MLP’s task to project RNN output to several time points in the future. Although results were pretty satisfactory, we didn’t stop there.

  • Instead, we applied to numerical time series a technique commonly used in natural language processing (NLP): sequence-to-sequence (seq2seq) prediction. While forecast performance was not much different from the previous case, we found the technique to be more intuitively appealing, since it reflects the causal relationship between successive forecasts.

Today we’ll enrich the seq2seq approach by adding a new component: the attention module. Originally introduced around 20141, attention mechanisms have gained enormous traction, so much so that a recent paper title starts out “Attention is Not All You Need”2.

The idea is the following.

In the classic encoder-decoder setup, the decoder gets “primed” with an encoder summary just a single time: the time it starts its forecasting loop. From then on, it’s on its own. With attention, however, it gets to see the complete sequence of encoder outputs again every time it forecasts a new value. What’s more, every time, it gets to zoom in on those outputs that seem relevant for the current prediction step.

This is a particularly useful strategy in translation: In generating the next word, a model will need to know what part of the source sentence to focus on. How much the technique helps with numerical sequences, in contrast, will likely depend on the features of the series in question.

Data input

As before, we work with vic_elec, but this time, we partly deviate from the way we used to employ it. With the original, bi-hourly dataset, training the current model takes a long time, longer than readers will want to wait when experimenting. So instead, we aggregate observations by day. In order to have enough data, we train on years 2012 and 2013, reserving 2014 for validation as well as post-training inspection.

vic_elec_daily <- vic_elec %>%
  select(Time, Demand) %>%
  index_by(Date = date(Time)) %>%
  summarise(
    Demand = sum(Demand) / 1e3) 

elec_train <- vic_elec_daily %>% 
  filter(year(Date) %in% c(2012, 2013)) %>%
  as_tibble() %>%
  select(Demand) %>%
  as.matrix()

elec_valid <- vic_elec_daily %>% 
  filter(year(Date) == 2014) %>%
  as_tibble() %>%
  select(Demand) %>%
  as.matrix()

elec_test <- vic_elec_daily %>% 
  filter(year(Date) %in% c(2014), month(Date) %in% 1:4) %>%
  as_tibble() %>%
  select(Demand) %>%
  as.matrix()

train_mean <- mean(elec_train)
train_sd <- sd(elec_train)

We’ll attempt to forecast demand up to fourteen days ahead. How long, then, should be the input sequences? This is a matter of experimentation; all the more so now that we’re adding in the attention mechanism. (I suspect that it might not handle very long sequences so well).

Below, we go with fourteen days for input length, too, but that may not necessarily be the best possible choice for this series.

n_timesteps <- 7 * 2
n_forecast <- 7 * 2

elec_dataset <- dataset(
  name = "elec_dataset",
  
  initialize = function(x, n_timesteps, sample_frac = 1) {
    
    self$n_timesteps <- n_timesteps
    self$x <- torch_tensor((x - train_mean) / train_sd)
    
    n <- length(self$x) - self$n_timesteps - 1
    
    self$starts <- sort(sample.int(
      n = n,
      size = n * sample_frac
    ))
    
  },
  
  .getitem = function(i) {
    
    start <- self$starts[i]
    end <- start + self$n_timesteps - 1
    lag <- 1
    
    list(
      x = self$x[start:end],
      y = self$x[(start+lag):(end+lag)]$squeeze(2)
    )
    
  },
  
  .length = function() {
    length(self$starts) 
  }
)

batch_size <- 32

train_ds <- elec_dataset(elec_train, n_timesteps, sample_frac = 0.5)
train_dl <- train_ds %>% dataloader(batch_size = batch_size, shuffle = TRUE)

valid_ds <- elec_dataset(elec_valid, n_timesteps, sample_frac = 0.5)
valid_dl <- valid_ds %>% dataloader(batch_size = batch_size)

test_ds <- elec_dataset(elec_test, n_timesteps)
test_dl <- test_ds %>% dataloader(batch_size = 1)

Model

Model-wise, we again encounter the three modules familiar from the previous post: encoder, decoder, and top-level seq2seq module. However, there is an additional component: the attention module, used by the decoder to obtain attention weights.

Encoder

The encoder still works the same way. It wraps an RNN, and returns the final state.

encoder_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, num_layers = 1, dropout = 0) {
    
    self$type <- type
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    }
    
  },
  
  forward = function(x) {
    
    x <- self$rnn(x)
    
    # return last states for all layers
    # per layer, a single tensor for GRU, a list of 2 tensors for LSTM
    x <- x[[2]]
    x
    
  }
)

Attention module

In basic seq2seq, whenever it had to generate a new value, the decoder took into account two things: its prior state, and the previous output generated. In an attention-enriched setup, the decoder additionally receives the complete output from the encoder. In deciding what subset of that output should matter, it gets help from a new agent, the attention module.

This, then, is the attention module’s raison d’être: Given current decoder state and well as complete encoder outputs, obtain a weighting of those outputs indicative of how relevant they are to what the decoder is currently up to. This procedure results in the so-called attention weights: a normalized score, for each time step in the encoding, that quantify their respective importance.

Attention may be implemented in a number of different ways. Here, we show two implementation options, one additive, and one multiplicative.

Additive attention

In additive attention, encoder outputs and decoder state are commonly either added or concatenated (we choose to do the latter, below). The resulting tensor is run through a linear layer, and a softmax is applied for normalization.

attention_module_additive <- nn_module(
  
  initialize = function(hidden_dim, attention_size) {
    
    self$attention <- nn_linear(2 * hidden_dim, attention_size)
    
  },
  
  forward = function(state, encoder_outputs) {
    
    # function argument shapes
    # encoder_outputs: (bs, timesteps, hidden_dim)
    # state: (1, bs, hidden_dim)
    
    # multiplex state to allow for concatenation (dimensions 1 and 2 must agree)
    seq_len <- dim(encoder_outputs)[2]
    # resulting shape: (bs, timesteps, hidden_dim)
    state_rep <- state$permute(c(2, 1, 3))$repeat_interleave(seq_len, 2)
    
    # concatenate along feature dimension
    concat <- torch_cat(list(state_rep, encoder_outputs), dim = 3)
    
    # run through linear layer with tanh
    # resulting shape: (bs, timesteps, attention_size)
    scores <- self$attention(concat) %>% 
      torch_tanh()
    
    # sum over attention dimension and normalize
    # resulting shape: (bs, timesteps) 
    attention_weights <- scores %>%
      torch_sum(dim = 3) %>%
      nnf_softmax(dim = 2)
    
    # a normalized score for every source token
    attention_weights
  }
)

Multiplicative attention

In multiplicative attention, scores are obtained by computing dot products between decoder state and all of the encoder outputs. Here too, a softmax is then used for normalization.

attention_module_multiplicative <- nn_module(
  
  initialize = function() {
    
    NULL
    
  },
  
  forward = function(state, encoder_outputs) {
    
    # function argument shapes
    # encoder_outputs: (bs, timesteps, hidden_dim)
    # state: (1, bs, hidden_dim)

    # allow for matrix multiplication with encoder_outputs
    state <- state$permute(c(2, 3, 1))
 
    # prepare for scaling by number of features
    d <- torch_tensor(dim(encoder_outputs)[3], dtype = torch_float())
       
    # scaled dot products between state and outputs
    # resulting shape: (bs, timesteps, 1)
    scores <- torch_bmm(encoder_outputs, state) %>%
      torch_div(torch_sqrt(d))
    
    # normalize
    # resulting shape: (bs, timesteps) 
    attention_weights <- scores$squeeze(3) %>%
      nnf_softmax(dim = 2)
    
    # a normalized score for every source token
    attention_weights
  }
)

Decoder

Once attention weights have been computed, their actual application is handled by the decoder. Concretely, the method in question, weighted_encoder_outputs(), computes a product of weights and encoder outputs, making sure that each output will have appropriate impact.

The rest of the action then happens in forward(). A concatenation of weighted encoder outputs (often called “context”) and current input is run through an RNN. Then, an ensemble of RNN output, context, and input is passed to an MLP. Finally, both RNN state and current prediction are returned.

decoder_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, attention_type, attention_size = 8, num_layers = 1) {
    
    self$type <- type
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        batch_first = TRUE
      )
    }
    
    self$linear <- nn_linear(2 * hidden_size + 1, 1)
    
    self$attention <- if (attention_type == "multiplicative") attention_module_multiplicative()
      else attention_module_additive(hidden_size, attention_size)
    
  },
  
  weighted_encoder_outputs = function(state, encoder_outputs) {

    # encoder_outputs is (bs, timesteps, hidden_dim)
    # state is (1, bs, hidden_dim)
    # resulting shape: (bs * timesteps)
    attention_weights <- self$attention(state, encoder_outputs)
    
    # resulting shape: (bs, 1, seq_len)
    attention_weights <- attention_weights$unsqueeze(2)
    
    # resulting shape: (bs, 1, hidden_size)
    weighted_encoder_outputs <- torch_bmm(attention_weights, encoder_outputs)
    
    weighted_encoder_outputs
    
  },
  
  forward = function(x, state, encoder_outputs) {
 
    # encoder_outputs is (bs, timesteps, hidden_dim)
    # state is (1, bs, hidden_dim)
    
    # resulting shape: (bs, 1, hidden_size)
    context <- self$weighted_encoder_outputs(state, encoder_outputs)
    
    # concatenate input and context
    # NOTE: this repeating is done to compensate for the absence of an embedding module
    # that, in NLP, would give x a higher proportion in the concatenation
    x_rep <- x$repeat_interleave(dim(context)[3], 3) 
    rnn_input <- torch_cat(list(x_rep, context), dim = 3)
    
    # resulting shapes: (bs, 1, hidden_size) and (1, bs, hidden_size)
    rnn_out <- self$rnn(rnn_input, state)
    rnn_output <- rnn_out[[1]]
    next_hidden <- rnn_out[[2]]
    
    mlp_input <- torch_cat(list(rnn_output$squeeze(2), context$squeeze(2), x$squeeze(2)), dim = 2)
    
    output <- self$linear(mlp_input)
    
    # shapes: (bs, 1) and (1, bs, hidden_size)
    list(output, next_hidden)
  }
  
)

seq2seq module

The seq2seq module is basically unchanged (apart from the fact that now, it allows for attention module configuration). For a detailed explanation of what happens here, please consult the previous post.

seq2seq_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, attention_type, attention_size, n_forecast, 
                        num_layers = 1, encoder_dropout = 0) {
    
    self$encoder <- encoder_module(type = type, input_size = input_size, hidden_size = hidden_size,
                                   num_layers, encoder_dropout)
    self$decoder <- decoder_module(type = type, input_size = 2 * hidden_size, hidden_size = hidden_size,
                                   attention_type = attention_type, attention_size = attention_size, num_layers)
    self$n_forecast <- n_forecast
    
  },
  
  forward = function(x, y, teacher_forcing_ratio) {
    
    outputs <- torch_zeros(dim(x)[1], self$n_forecast)$to(device = device)
    encoded <- self$encoder(x)
    encoder_outputs <- encoded[[1]]
    hidden <- encoded[[2]]
    # list of (batch_size, 1), (1, batch_size, hidden_size)
    out <- self$decoder(x[ , n_timesteps, , drop = FALSE], hidden, encoder_outputs)
    # (batch_size, 1)
    pred <- out[[1]]
    # (1, batch_size, hidden_size)
    state <- out[[2]]
    outputs[ , 1] <- pred$squeeze(2)
    
    for (t in 2:self$n_forecast) {
      
      teacher_forcing <- runif(1) < teacher_forcing_ratio
      input <- if (teacher_forcing == TRUE) pred$unsqueeze(3) else y[ , t - 1]
      out <- self$decoder(pred$unsqueeze(3), state, encoder_outputs)
      pred <- out[[1]]
      state <- out[[2]]
      outputs[ , t] <- pred$squeeze(2)
      
    }
    
    outputs
  }
  
)

When instantiating the top-level model, we now have an additional choice: that between additive and multiplicative attention. In the “accuracy” sense of performance, my tests did not show any differences. However, the multiplicative variant is a lot faster.

net <- seq2seq_module("gru", input_size = 1, hidden_size = 32, attention_type = "multiplicative",
                      attention_size = 8, n_forecast = n_timesteps)

# training RNNs on the GPU currently prints a warning that may clutter 
# the console
# see https://github.com/mlverse/torch/issues/461
# alternatively, use 
# device <- "cpu"
device <- torch_device(if (cuda_is_available()) "cuda" else "cpu")

net <- net$to(device = device)

Training

Just like last time, in model training, we get to choose the degree of teacher forcing. Below, we go with a fraction of 0.0, that is, no forcing at all.

optimizer <- optim_adam(net$parameters, lr = 0.001)

num_epochs <- 100

train_batch <- function(b, teacher_forcing_ratio) {
  
  optimizer$zero_grad()
  output <- net(b$x$to(device = device), b$y$to(device = device), teacher_forcing_ratio)
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$backward()
  optimizer$step()
  
  loss$item()
  
}

valid_batch <- function(b, teacher_forcing_ratio = 0) {
  
  output <- net(b$x$to(device = device), b$y$to(device = device), teacher_forcing_ratio)
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  
  loss$item()
  
}

for (epoch in 1:num_epochs) {
  
  net$train()
  train_loss <- c()
  
  coro::loop(for (b in train_dl) {
    loss <-train_batch(b, teacher_forcing_ratio = 0.3)
    train_loss <- c(train_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, training: loss: %3.5f n", epoch, mean(train_loss)))
  
  net$eval()
  valid_loss <- c()
  
  coro::loop(for (b in valid_dl) {
    loss <- valid_batch(b)
    valid_loss <- c(valid_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, validation: loss: %3.5f n", epoch, mean(valid_loss)))
}
# Epoch 1, training: loss: 0.83752 
# Epoch 1, validation: loss: 0.83167

# Epoch 2, training: loss: 0.72803 
# Epoch 2, validation: loss: 0.80804 

# ...
# ...

# Epoch 99, training: loss: 0.10385 
# Epoch 99, validation: loss: 0.21259 

# Epoch 100, training: loss: 0.10396 
# Epoch 100, validation: loss: 0.20975 

Evaluation

For visual inspection, we pick a few forecasts from the test set.

net$eval()

test_preds <- vector(mode = "list", length = length(test_dl))

i <- 1

vic_elec_test <- vic_elec_daily %>%
  filter(year(Date) == 2014, month(Date) %in% 1:4)


coro::loop(for (b in test_dl) {
  
  input <- b$x
  output <- net(b$x$to(device = device), b$y$to(device = device), teacher_forcing_ratio = 0)
  preds <- as.numeric(output)
  
  test_preds[[i]] <- preds
  i <<- i + 1
  
})

test_pred1 <- test_preds[[1]]
test_pred1 <- c(rep(NA, n_timesteps), test_pred1, rep(NA, nrow(vic_elec_test) - n_timesteps - n_forecast))

test_pred2 <- test_preds[[21]]
test_pred2 <- c(rep(NA, n_timesteps + 20), test_pred2, rep(NA, nrow(vic_elec_test) - 20 - n_timesteps - n_forecast))

test_pred3 <- test_preds[[41]]
test_pred3 <- c(rep(NA, n_timesteps + 40), test_pred3, rep(NA, nrow(vic_elec_test) - 40 - n_timesteps - n_forecast))

test_pred4 <- test_preds[[61]]
test_pred4 <- c(rep(NA, n_timesteps + 60), test_pred4, rep(NA, nrow(vic_elec_test) - 60 - n_timesteps - n_forecast))

test_pred5 <- test_preds[[81]]
test_pred5 <- c(rep(NA, n_timesteps + 80), test_pred5, rep(NA, nrow(vic_elec_test) - 80 - n_timesteps - n_forecast))


preds_ts <- vic_elec_test %>%
  select(Demand, Date) %>%
  add_column(
    ex_1 = test_pred1 * train_sd + train_mean,
    ex_2 = test_pred2 * train_sd + train_mean,
    ex_3 = test_pred3 * train_sd + train_mean,
    ex_4 = test_pred4 * train_sd + train_mean,
    ex_5 = test_pred5 * train_sd + train_mean) %>%
  pivot_longer(-Date) %>%
  update_tsibble(key = name)


preds_ts %>%
  autoplot() +
  scale_color_hue(h = c(80, 300), l = 70) +
  theme_minimal()
A sample of two-weeks-ahead predictions for the test set, 2014.

(#fig:unnamed-chunk-11)A sample of two-weeks-ahead predictions for the test set, 2014.

We can’t directly compare performance here to that of previous models in our series, as we’ve pragmatically redefined the task. The main goal, however, has been to introduce the concept of attention. Specifically, how to manually implement the technique – something that, once you’ve understood the concept, you may never have to do in practice. Instead, you would likely make use of existing tools that come with torch (multi-head attention and transformer modules), tools we may introduce in a future “season” of this series.

Thanks for reading!

Photo by David Clode on Unsplash

Bahdanau, Dzmitry, Kyunghyun Cho, and Yoshua Bengio. 2014. “Neural Machine Translation by Jointly Learning to Align and Translate.” CoRR abs/1409.0473. http://arxiv.org/abs/1409.0473.

Dong, Yihe, Jean-Baptiste Cordonnier, and Andreas Loukas. 2021. “Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth.” arXiv E-Prints, March, arXiv:2103.03404. http://arxiv.org/abs/2103.03404.

Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. “Attention Is All You Need.” arXiv E-Prints, June, arXiv:1706.03762. http://arxiv.org/abs/1706.03762.

Vinyals, Oriol, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey E. Hinton. 2014. “Grammar as a Foreign Language.” CoRR abs/1412.7449. http://arxiv.org/abs/1412.7449.

Xu, Kelvin, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron C. Courville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio. 2015. “Show, Attend and Tell: Neural Image Caption Generation with Visual Attention.” CoRR abs/1502.03044. http://arxiv.org/abs/1502.03044.

  1. For important papers see: Bahdanau, Cho, and Bengio (2014), Vinyals et al. (2014), Xu et al. (2015).↩︎

  2. Dong, Cordonnier, and Loukas (2021), thus replying to Vaswani et al. (2017), whose 2017 paper “went viral” for stating the opposite.↩︎

Categories
Offsites

Massively Parallel Graph Computation: From Theory to Practice

Graphs are useful theoretical representations of the connections between groups of entities, and have been used for a variety of purposes in data science, from ranking web pages by popularity and mapping out social networks, to assisting with navigation. In many cases, such applications require the processing of graphs containing hundreds of billions of edges, which is far too large to be processed on a single consumer-grade machine. A typical approach to scaling graph algorithms is to run in a distributed setting, i.e., to partition the data (and the algorithm) among multiple computers to perform the computation in parallel. While this approach allows one to process graphs with trillions of edges, it also introduces new challenges. Namely, because each computer only sees a small piece of the input graph at a time, one needs to handle inter-machine communication and design algorithms that can be split across multiple computers.

A framework for implementing distributed algorithms, MapReduce, was introduced in 2008. It transparently handled communication between machines while offering good fault-tolerance capabilities and inspired the development of a number of distributed computation frameworks, including Pregel, Apache Hadoop, and many others. Still, the challenge of developing algorithms for distributed computation on very large graphs remained, and designing efficient algorithms in this context even for basic problems, such as connected components, maximum matching or shortest paths, has been an active area of research. While recent work has demonstrated new algorithms for many problems, including our algorithms for connected components (both in theory and practice) and hierarchical clustering, there was still a need for methods that could solve a range of problems more quickly.

Today we present a pair of recent papers that address this problem by first constructing a theoretical model for distributed graph algorithms and then demonstrating how the model can be applied. The proposed model, Adaptive Massively Parallel Computation (AMPC), augments the theoretical capabilities of MapReduce, providing a pathway to solve many graph problems in fewer computation rounds. We also show how the AMPC model can be effectively implemented in practice. The suite of algorithms we describe, which includes algorithms for maximal independent set, maximum matching, connected components and minimum spanning tree, work up to 7x faster than current state-of-the-art approaches.

Limitations of MapReduce
In order to understand the limitations of MapReduce for developing graph algorithms, consider a simplified variant of the connected components problem. The input is a collection of rooted trees, and the goal is to compute, for each node, the root of its tree. Even this seemingly simple problem is not easy to solve in MapReduce. In fact, in the Massively Parallel Computation (MPC) model — the theoretical model behind MapReduce, Pregel, Apache Giraph and many other distributed computation frameworks — this problem is widely believed to require at least a number of rounds of computation proportional to log n, where n is the total number of nodes in the graph. While log n may not seem to be a large number, algorithms processing trillion-edge graphs often write hundreds of terabytes of data to disk in each round, and thus even a small reduction in the number of rounds may bring significant resource savings.

The problem of finding root nodes. Nodes are represented by blue circles. Gray arrows point from each node to its parent. The root nodes are the nodes with no parents. The orange arrows illustrate the path an algorithm would follow from a node to the root of the tree to which it belongs.

A similar subproblem showed up in our algorithms for finding connected components and computing a hierarchical clustering. We observed that one can bypass the limitations of MapReduce by implementing these algorithms through the use of a distributed hash table (DHT), a service that is initialized with a collection of key-value pairs and then returns a value associated with a provided key in real-time. In our implementation, for each node, the DHT stores its parent node. Then, a machine that processes a graph node can use the DHT and “walk up” the tree until it reaches the root. While the use of a DHT worked well for this particular problem (although it relied on the input trees being not too deep), it was unclear if the idea could be applied more broadly.

The Adaptive Massively Parallel Computation Model
To extend this approach to other problems, we started by developing a model to theoretically analyze algorithms that utilize a DHT. The resulting AMPC model builds upon the well-established MPC model and formally describes the capabilities brought by the use of a distributed hash table.

In the MPC model there is a collection of machines, which communicate via message passing in synchronous rounds. Messages sent in one round are delivered in the beginning of the following round and constitute that round’s entire input (i.e., the machines do not retain information from one round to the next). In the first round, one can assume that the input is randomly distributed across the machines. The goal is to minimize the number of computation rounds, while assuring load-balancing between machines in each round.

Computation in the MPC model. Each column represents one machine in subsequent computation rounds. Once all machines have completed a round of computation, all messages sent in that round are delivered, and the following round begins.

We then formalized the AMPC model by introducing a new approach, in which machines write to a write-only distributed hash table each round, instead of communicating via messages. Once a new round starts, the hash table from the previous round becomes read-only and a new write-only output hash table becomes available. What is important is that only the method of communication changes — the amount of communication and available space per machine is constrained exactly in the same way as in the MPC model. Hence, at a high level the added capability of the AMPC model is that each machine can choose what data to read, instead of being provided a piece of data.

Computation in the AMPC model. Once all machines have completed a round of computation, the data they produced is saved to a distributed hash table. In the following round, each machine can read arbitrary values from this distributed hash table and write to a new distributed hash table.

Algorithms and Empirical Evaluation
This seemingly small difference in the way machines communicate allowed us to design much faster algorithms to a number of basic graph problems. In particular, we show that it is possible to find connected components, minimum spanning tree, maximal matching and maximal independent set in a constant number of rounds, regardless of the size of the graph.

To investigate the practical applicability of the AMPC algorithms, we have instantiated the model by combining Flume C++ (a C++ counterpart of FlumeJava) with a DHT communication layer. We have evaluated our AMPC algorithms for minimum spanning tree, maximal independent set and maximum matching and observed that we can achieve up to 7x speedups over implementations that did not use a DHT. At the same time, the AMPC implementations used 10x fewer rounds on average to complete, and also wrote less data to disk.

Our implementation of the AMPC model took advantage of hardware-accelerated remote direct memory access (RDMA), a technology that allows reading from the memory of a remote machine with a latency of a few microseconds, which is just an order of magnitude slower than reading from local memory. While some of the AMPC algorithms communicated more data than their MPC counterparts, they were overall faster, as they performed mostly fast reads using RDMA, instead of costly writes to disk.

Conclusion
With the AMPC model, we built a theoretical framework inspired by practically efficient implementations, and then developed new theoretical algorithms that delivered good empirical performance and maintained good fault-tolerance properties. We’ve been happy to see that the AMPC model has already been the subject of further study and are excited to learn what other problems can be solved more efficiently using the AMPC model or its practical implementations.

Acknowledgements
Co-authors on the two papers covered in this blog post include Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, and Warren Schudy. We also thank members of the Graph Mining team for their collaborations, and especially Mohammad Hossein Bateni for his input on this post. To learn more about our recent work on scalable graph algorithms, see videos from our recent Graph Mining and Learning workshop.

Categories
Offsites

torch time series, take three: Sequence-to-sequence prediction

Today, we continue our exploration of multi-step time-series forecasting with torch. This post is the third in a series.

  • Initially, we covered basics of recurrent neural networks (RNNs), and trained a model to predict the very next value in a sequence. We also found we could forecast quite a few steps ahead by feeding back individual predictions in a loop.

  • Next, we built a model “natively” for multi-step prediction. A small multi-layer-perceptron (MLP) was used to project RNN output to several time points in the future.

Of both approaches, the latter was the more successful. But conceptually, it has an unsatisfying touch to it: When the MLP extrapolates and generates output for, say, ten consecutive points in time, there is no causal relation between those. (Imagine a weather forecast for ten days that never got updated.)

Now, we’d like to try something more intuitively appealing. The input is a sequence; the output is a sequence. In natural language processing (NLP), this type of task is very common: It’s exactly the kind of situation we see with machine translation or summarization.

Quite fittingly, the types of models employed to these ends are named sequence-to-sequence models (often abbreviated seq2seq). In a nutshell, they split up the task into two components: an encoding and a decoding part. The former is done just once per input-target pair. The latter is done in a loop, as in our first try. But the decoder has more information at its disposal: At each iteration, its processing is based on the previous prediction as well as previous state. That previous state will be the encoder’s when a loop is started, and its own ever thereafter.

Before discussing the model in detail, we need to adapt our data input mechanism.

Data input

We continue working with vic_elec , provided by tsibbledata.

Again, the dataset definition in the current post looks a bit different from the way it did before; it’s the shape of the target that differs. This time, y equals x, shifted to the left by one.

The reason we do this is owed to the way we are going to train the network. With seq2seq, people often use a technique called “teacher forcing” where, instead of feeding back its own prediction into the decoder module, you pass it the value it should have predicted. To be clear, this is done during training only, and to a configurable degree.

n_timesteps <- 7 * 24 * 2
n_forecast <- n_timesteps

vic_elec_get_year <- function(year, month = NULL) {
  vic_elec %>%
    filter(year(Date) == year, month(Date) == if (is.null(month)) month(Date) else month) %>%
    as_tibble() %>%
    select(Demand)
}

elec_train <- vic_elec_get_year(2012) %>% as.matrix()
elec_valid <- vic_elec_get_year(2013) %>% as.matrix()
elec_test <- vic_elec_get_year(2014, 1) %>% as.matrix()

train_mean <- mean(elec_train)
train_sd <- sd(elec_train)

elec_dataset <- dataset(
  name = "elec_dataset",
  
  initialize = function(x, n_timesteps, sample_frac = 1) {
    
    self$n_timesteps <- n_timesteps
    self$x <- torch_tensor((x - train_mean) / train_sd)
    
    n <- length(self$x) - self$n_timesteps - 1
    
    self$starts <- sort(sample.int(
      n = n,
      size = n * sample_frac
    ))
    
  },
  
  .getitem = function(i) {
    
    start <- self$starts[i]
    end <- start + self$n_timesteps - 1
    lag <- 1
    
    list(
      x = self$x[start:end],
      y = self$x[(start+lag):(end+lag)]$squeeze(2)
    )
    
  },
  
  .length = function() {
    length(self$starts) 
  }
)

Dataset as well as dataloader instantations then can proceed as before.

batch_size <- 32

train_ds <- elec_dataset(elec_train, n_timesteps, sample_frac = 0.5)
train_dl <- train_ds %>% dataloader(batch_size = batch_size, shuffle = TRUE)

valid_ds <- elec_dataset(elec_valid, n_timesteps, sample_frac = 0.5)
valid_dl <- valid_ds %>% dataloader(batch_size = batch_size)

test_ds <- elec_dataset(elec_test, n_timesteps)
test_dl <- test_ds %>% dataloader(batch_size = 1)

Model

Technically, the model consists of three modules: the aforementioned encoder and decoder, and the seq2seq module that orchestrates them.

Encoder

The encoder takes its input and runs it through an RNN. Of the two things returned by a recurrent neural network, outputs and state, so far we’ve only been using output. This time, we do the opposite: We throw away the outputs, and only return the state.

If the RNN in question is a GRU (and assuming that of the outputs, we take just the final time step, which is what we’ve been doing throughout), there really is no difference: The final state equals the final output. If it’s an LSTM, however, there is a second kind of state, the “cell state”. In that case, returning the state instead of the final output will carry more information.

encoder_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, num_layers = 1, dropout = 0) {
    
    self$type <- type
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    }
    
  },
  
  forward = function(x) {
    
    x <- self$rnn(x)
    
    # return last states for all layers
    # per layer, a single tensor for GRU, a list of 2 tensors for LSTM
    x <- x[[2]]
    x
    
  }
  
)

Decoder

In the decoder, just like in the encoder, the main component is an RNN. In contrast to previously-shown architectures, though, it does not just return a prediction. It also reports back the RNN’s final state.

decoder_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, num_layers = 1) {
    
    self$type <- type
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        batch_first = TRUE
      )
    }
    
    self$linear <- nn_linear(hidden_size, 1)
    
  },
  
  forward = function(x, state) {
    
    # input to forward:
    # x is (batch_size, 1, 1)
    # state is (1, batch_size, hidden_size)
    x <- self$rnn(x, state)
    
    # break up RNN return values
    # output is (batch_size, 1, hidden_size)
    # next_hidden is
    c(output, next_hidden) %<-% x
    
    output <- output$squeeze(2)
    output <- self$linear(output)
    
    list(output, next_hidden)
    
  }
  
)

seq2seq module

seq2seq is where the action happens. The plan is to encode once, then call the decoder in a loop.

If you look back to decoder forward(), you see that it takes two arguments: x and state.

Depending on the context, x corresponds to one of three things: final input, preceding prediction, or prior ground truth.

  • The very first time the decoder is called on an input sequence, x maps to the final input value. This is different from a task like machine translation, where you would pass in a start token. With time series, though, we’d like to continue where the actual measurements stop.

  • In further calls, we want the decoder to continue from its most recent prediction. It is only logical, thus, to pass back the preceding forecast.

  • That said, in NLP a technique called “teacher forcing” is commonly used to speed up training. With teacher forcing, instead of the forecast we pass the actual ground truth, the thing the decoder should have predicted. We do that only in a configurable fraction of cases, and – naturally – only while training. The rationale behind this technique is that without this form of re-calibration, consecutive prediction errors can quickly erase any remaining signal.

state, too, is polyvalent. But here, there are just two possibilities: encoder state and decoder state.

  • The first time the decoder is called, it is “seeded” with the final state from the encoder. Note how this is the only time we make use of the encoding.

  • From then on, the decoder’s own previous state will be passed. Remember how it returns two values, forecast and state?

seq2seq_module <- nn_module(
  
  initialize = function(type, input_size, hidden_size, n_forecast, num_layers = 1, encoder_dropout = 0) {
    
    self$encoder <- encoder_module(type = type, input_size = input_size,
                                   hidden_size = hidden_size, num_layers, encoder_dropout)
    self$decoder <- decoder_module(type = type, input_size = input_size,
                                   hidden_size = hidden_size, num_layers)
    self$n_forecast <- n_forecast
    
  },
  
  forward = function(x, y, teacher_forcing_ratio) {
    
    # prepare empty output
    outputs <- torch_zeros(dim(x)[1], self$n_forecast)$to(device = device)
    
    # encode current input sequence
    hidden <- self$encoder(x)
    
    # prime decoder with final input value and hidden state from the encoder
    out <- self$decoder(x[ , n_timesteps, , drop = FALSE], hidden)
    
    # decompose into predictions and decoder state
    # pred is (batch_size, 1)
    # state is (1, batch_size, hidden_size)
    c(pred, state) %<-% out
    
    # store first prediction
    outputs[ , 1] <- pred$squeeze(2)
    
    # iterate to generate remaining forecasts
    for (t in 2:self$n_forecast) {
      
      # call decoder on either ground truth or previous prediction, plus previous decoder state
      teacher_forcing <- runif(1) < teacher_forcing_ratio
      input <- if (teacher_forcing == TRUE) y[ , t - 1, drop = FALSE] else pred
      input <- input$unsqueeze(3)
      out <- self$decoder(input, state)
      
      # again, decompose decoder return values
      c(pred, state) %<-% out
      # and store current prediction
      outputs[ , t] <- pred$squeeze(2)
    }
    outputs
  }
  
)

net <- seq2seq_module("gru", input_size = 1, hidden_size = 32, n_forecast = n_forecast)

# training RNNs on the GPU currently prints a warning that may clutter 
# the console
# see https://github.com/mlverse/torch/issues/461
# alternatively, use 
# device <- "cpu"
device <- torch_device(if (cuda_is_available()) "cuda" else "cpu")

net <- net$to(device = device)

Training

The training procedure is mainly unchanged. We do, however, need to decide about teacher_forcing_ratio, the proportion of input sequences we want to perform re-calibration on. In valid_batch(), this should always be 0, while in train_batch(), it’s up to us (or rather, experimentation). Here, we set it to 0.3.

optimizer <- optim_adam(net$parameters, lr = 0.001)

num_epochs <- 50

train_batch <- function(b, teacher_forcing_ratio) {
  
  optimizer$zero_grad()
  output <- net(b$x$to(device = device), b$y$to(device = device), teacher_forcing_ratio)
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$backward()
  optimizer$step()
  
  loss$item()
  
}

valid_batch <- function(b, teacher_forcing_ratio = 0) {
  
  output <- net(b$x$to(device = device), b$y$to(device = device), teacher_forcing_ratio)
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  
  loss$item()
  
}

for (epoch in 1:num_epochs) {
  
  net$train()
  train_loss <- c()
  
  coro::loop(for (b in train_dl) {
    loss <-train_batch(b, teacher_forcing_ratio = 0.3)
    train_loss <- c(train_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, training: loss: %3.5f n", epoch, mean(train_loss)))
  
  net$eval()
  valid_loss <- c()
  
  coro::loop(for (b in valid_dl) {
    loss <- valid_batch(b)
    valid_loss <- c(valid_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, validation: loss: %3.5f n", epoch, mean(valid_loss)))
}
Epoch 1, training: loss: 0.37961 

Epoch 1, validation: loss: 1.10699 

Epoch 2, training: loss: 0.19355 

Epoch 2, validation: loss: 1.26462 

# ...
# ...

Epoch 49, training: loss: 0.03233 

Epoch 49, validation: loss: 0.62286 

Epoch 50, training: loss: 0.03091 

Epoch 50, validation: loss: 0.54457

It’s interesting to compare performances for different settings of teacher_forcing_ratio. With a setting of 0.5, training loss decreases a lot more slowly; the opposite is seen with a setting of 0. Validation loss, however, is not affected significantly.

Evaluation

The code to inspect test-set forecasts is unchanged.

net$eval()

test_preds <- vector(mode = "list", length = length(test_dl))

i <- 1

coro::loop(for (b in test_dl) {
  
  input <- b$x
  output <- net(input$to(device = device))
  preds <- as.numeric(output)
  
  test_preds[[i]] <- preds
  i <<- i + 1
  
})

vic_elec_jan_2014 <- vic_elec %>%
  filter(year(Date) == 2014, month(Date) == 1)

test_pred1 <- test_preds[[1]]
test_pred1 <- c(rep(NA, n_timesteps), test_pred1, rep(NA, nrow(vic_elec_jan_2014) - n_timesteps - n_forecast))

test_pred2 <- test_preds[[408]]
test_pred2 <- c(rep(NA, n_timesteps + 407), test_pred2, rep(NA, nrow(vic_elec_jan_2014) - 407 - n_timesteps - n_forecast))

test_pred3 <- test_preds[[817]]
test_pred3 <- c(rep(NA, nrow(vic_elec_jan_2014) - n_forecast), test_pred3)


preds_ts <- vic_elec_jan_2014 %>%
  select(Demand) %>%
  add_column(
    mlp_ex_1 = test_pred1 * train_sd + train_mean,
    mlp_ex_2 = test_pred2 * train_sd + train_mean,
    mlp_ex_3 = test_pred3 * train_sd + train_mean) %>%
  pivot_longer(-Time) %>%
  update_tsibble(key = name)


preds_ts %>%
  autoplot() +
  scale_colour_manual(values = c("#08c5d1", "#00353f", "#ffbf66", "#d46f4d")) +
  theme_minimal()
One-week-ahead predictions for January, 2014.

(#fig:unnamed-chunk-8)One-week-ahead predictions for January, 2014.

Comparing this to the forecast obtained from last time’s RNN-MLP combo, we don’t see much of a difference. Is this surprising? To me it is. If asked to speculate about the reason, I would probably say this: In all of the architectures we’ve used so far, the main carrier of information has been the final hidden state of the RNN (one and only RNN in the two previous setups, encoder RNN in this one). It will be interesting to see what happens in the last part of this series, when we augment the encoder-decoder architecture by attention.

Thanks for reading!

Photo by Suzuha Kozuki on Unsplash

Categories
Offsites

Contactless Sleep Sensing in Nest Hub

People often turn to technology to manage their health and wellbeing, whether it is to record their daily exercise, measure their heart rate, or increasingly, to understand their sleep patterns. Sleep is foundational to a person’s everyday wellbeing and can be impacted by (and in turn, have an impact on) other aspects of one’s life — mood, energy, diet, productivity, and more.

As part of our ongoing efforts to support people’s health and happiness, today we announced Sleep Sensing in the new Nest Hub, which uses radar-based sleep tracking in addition to an algorithm for cough and snore detection. While not intended for medical purposes1, Sleep Sensing is an opt-in feature that can help users better understand their nighttime wellness using a contactless bedside setup. Here we describe the technologies behind Sleep Sensing and discuss how we leverage on-device signal processing to enable sleep monitoring (comparable to other clinical- and consumer-grade devices) in a way that protects user privacy.

Soli for Sleep Tracking
Sleep Sensing in Nest Hub demonstrates the first wellness application of Soli, a miniature radar sensor that can be used for gesture sensing at various scales, from a finger tap to movements of a person’s body. In Pixel 4, Soli powers Motion Sense, enabling touchless interactions with the phone to skip songs, snooze alarms, and silence phone calls. We extended this technology and developed an embedded Soli-based algorithm that could be implemented in Nest Hub for sleep tracking.

Soli consists of a millimeter-wave frequency-modulated continuous wave (FMCW) radar transceiver that emits an ultra-low power radio wave and measures the reflected signal from the scene of interest. The frequency spectrum of the reflected signal contains an aggregate representation of the distance and velocity of objects within the scene. This signal can be processed to isolate a specified range of interest, such as a user’s sleeping area, and to detect and characterize a wide range of motions within this region, ranging from large body movements to sub-centimeter respiration.

Soli spectrogram illustrating its ability to detect a wide range of motions, characterized as (a) an empty room (no variation in the reflected signal demonstrated by the black space), (b) large pose changes, (c) brief limb movements, and (d) sub-centimeter chest and torso displacements from respiration while at rest.

In order to make use of this signal for Sleep Sensing, it was necessary to design an algorithm that could determine whether a person is present in the specified sleeping area and, if so, whether the person is asleep or awake. We designed a custom machine-learning (ML) model to efficiently process a continuous stream of 3D radar tensors (summarizing activity over a range of distances, frequencies, and time) and automatically classify each feature into one of three possible states: absent, awake, and asleep.

To train and evaluate the model, we recorded more than a million hours of radar data from thousands of individuals, along with thousands of sleep diaries, reference sensor recordings, and external annotations. We then leveraged the TensorFlow Extended framework to construct a training pipeline to process this data and produce an efficient TensorFlow Lite embedded model. In addition, we created an automatic calibration algorithm that runs during setup to configure the part of the scene on which the classifier will focus. This ensures that the algorithm ignores motion from a person on the other side of the bed or from other areas of the room, such as ceiling fans and swaying curtains.

The custom ML model efficiently processes a continuous stream of 3D radar tensors (summarizing activity over a range of distances, frequencies, and time) to automatically compute probabilities for the likelihood of user presence and wakefulness (awake or asleep).

To validate the accuracy of the algorithm, we compared it to the gold-standard of sleep-wake determination, the polysomnogram sleep study, in a cohort of 33 “healthy sleepers” (those without significant sleep issues, like sleep apnea or insomnia) across a broad age range (19-78 years of age). Sleep studies are typically conducted in clinical and research laboratories in order to collect various body signals (brain waves, muscle activity, respiratory and heart rate measurements, body movement and position, and snoring), which can then be interpreted by trained sleep experts to determine stages of sleep and identify relevant events. To account for variability in how different scorers apply the American Academy of Sleep Medicine’s staging and scoring rules, our study used two board-certified sleep technologists to independently annotate each night of sleep and establish a definitive groundtruth.

We compared our Sleep Sensing algorithm’s outputs to the corresponding groundtruth sleep and wake labels for every 30-second epoch of time to compute standard performance metrics (e.g., sensitivity and specificity). While not a true head-to-head comparison, this study’s results can be compared against previously published studies in similar cohorts with comparable methodologies in order to get a rough estimate of performance. In “Sleep-wake detection with a contactless, bedside radar sleep sensing system”, we share the full details of these validation results, demonstrating sleep-wake estimation equivalent to or, in some cases, better than current clinical and consumer sleep tracking devices.

Aggregate performance from previously published accuracies for detection of sleep (sensitivity) and wake (specificity) of a variety of sleep trackers against polysomnography in a variety of different studies, accounting for 3,990 nights in total. While this is not a head-to-head comparison, the performance of Sleep Sensing on Nest Hub in a population of healthy sleepers who simultaneously underwent polysomnography is added to the figure for rough comparison. The size of each circle is a reflection of the number of nights and the inset illustrates the mean±standard deviation for the performance metrics.

Understanding Sleep Quality with Audio Sensing
The Soli-based sleep tracking algorithm described above gives users a convenient and reliable way to see how much sleep they are getting and when sleep disruptions occur. However, to understand and improve their sleep, users also need to understand why their sleep is disrupted. To assist with this, Nest Hub uses its array of sensors to track common sleep disturbances, such as light level changes or uncomfortable room temperature. In addition to these, respiratory events like coughing and snoring are also frequent sources of disturbance, but people are often unaware of these events.

As with other audio-processing applications like speech or music recognition, coughing and snoring exhibit distinctive temporal patterns in the audio frequency spectrum, and with sufficient data an ML model can be trained to reliably recognize these patterns while simultaneously ignoring a wide variety of background noises, from a humming fan to passing cars. The model uses entirely on-device audio processing with privacy-preserving analysis, with no raw audio data sent to Google’s servers. A user can then opt to save the outputs of the processing (sound occurrences, such as the number of coughs and snore minutes) in Google Fit, in order to view personal insights and summaries of their night time wellness over time.

The Nest Hub displays when snoring and coughing may have disturbed a user’s sleep (top) and can track weekly trends (bottom).

To train the model, we assembled a large, hand-labeled dataset, drawing examples from the publicly available AudioSet research dataset as well as hundreds of thousands of additional real-world audio clips contributed by thousands of individuals.

Log-Mel spectrogram inputs comparing cough (left) and snore (right) audio snippets.

When a user opts in to cough and snore tracking on their bedside Nest Hub, the device first uses its Soli-based sleep algorithms to detect when a user goes to bed. Once it detects that a user has fallen asleep, it then activates its on-device sound sensing model and begins processing audio. The model works by continuously extracting spectrogram-like features from the audio input and feeding them through a convolutional neural network classifier in order to estimate the probability that coughing or snoring is happening at a given instant in time. These estimates are analyzed over the course of the night to produce a report of the overall cough count and snoring duration and highlight exactly when these events occurred.

Conclusion
The new Nest Hub, with its underlying Sleep Sensing features, is a first step in empowering users to understand their nighttime wellness using privacy-preserving radar and audio signals. We continue to research additional ways that ambient sensing and the predictive ability of consumer devices could help people better understand their daily health and wellness in a privacy-preserving way.

Acknowledgements
This work involved collaborative efforts from a multidisciplinary team of software engineers, researchers, clinicians, and cross-functional contributors. Special thanks to D. Shin for his significant contributions to this technology and blogpost, and Dr. Logan Schneider, visiting sleep neurologist affiliated with the Stanford/VA Alzheimer’s Center and Stanford Sleep Center, whose clinical expertise and contributions were invaluable to continuously guide this research. In addition to the authors, key contributors to this research from Google Health include Jeffrey Yu, Allen Jiang, Arno Charton, Jake Garrison, Navreet Gill, Sinan Hersek, Yijie Hong, Jonathan Hsu, Andi Janti, Ajay Kannan, Mukil Kesavan, Linda Lei, Kunal Okhandiar‎, Xiaojun Ping, Jo Schaeffer, Neil Smith, Siddhant Swaroop, Bhavana Koka, Anupam Pathak, Dr. Jim Taylor, and the extended team. Another special thanks to Ken Mixter for his support and contributions to the development and integration of this technology into Nest Hub. Thanks to Mark Malhotra and Shwetak Patel for their ongoing leadership, as well as the Nest, Fit, Soli, and Assistant teams we collaborated with to build and validate Sleep Sensing on Nest Hub.


1 Not intended to diagnose, cure, mitigate, prevent or treat any disease or condition. 

Categories
Offsites

LEAF: A Learnable Frontend for Audio Classification

Developing machine learning (ML) models for audio understanding has seen tremendous progress over the past several years. Leveraging the ability to learn parameters from data, the field has progressively shifted from composite, handcrafted systems to today’s deep neural classifiers that are used to recognize speech, understand music, or classify animal vocalizations such as bird calls. However, unlike computer vision models, which can learn from raw pixels, deep neural networks for audio classification are rarely trained from raw audio waveforms. Instead, they rely on pre-processed data in the form of mel filterbanks — handcrafted mel-scaled spectrograms that have been designed to replicate some aspects of the human auditory response.

Although modeling mel filterbanks for ML tasks has been historically successful, it is limited by the inherent biases of fixed features: even though using a fixed mel-scale and a logarithmic compression works well in general, we have no guarantee that they provide the best representations for the task at hand. In particular, even though matching human perception provides good inductive biases for some application domains, e.g., speech recognition or music understanding, these biases may be detrimental to domains for which imitating the human ear is not important, such as recognizing whale calls. So, in order to achieve optimal performance, the mel filterbanks should be tailored to the task of interest, a tedious process that requires an iterative effort informed by expert domain knowledge. As a consequence, standard mel filterbanks are used for most audio classification tasks in practice, even though they are suboptimal. In addition, while researchers have proposed ML systems to address these problems, such as Time-Domain Filterbanks, SincNet and Wavegram, they have yet to match the performance of traditional mel filterbanks.

In “LEAF, A Fully Learnable Frontend for Audio Classification”, accepted at ICLR 2021, we present an alternative method for crafting learnable spectrograms for audio understanding tasks. LEarnable Audio Frontend (LEAF) is a neural network that can be initialized to approximate mel filterbanks, and then be trained jointly with any audio classifier to adapt to the task at hand, while only adding a handful of parameters to the full model. We show that over a wide range of audio signals and classification tasks, including speech, music and bird songs, LEAF spectrograms improve classification performance over fixed mel filterbanks and over previously proposed learnable systems. We have implemented the code in TensorFlow 2 and released it to the community through our GitHub repository.

Mel Filterbanks: Mimicking Human Perception of Sound
The first step in the traditional approach to creating a mel filterbank is to capture the sound’s time-variability by windowing, i.e., cutting the signal into short segments with fixed duration. Then, one performs filtering, by passing the windowed segments through a bank of fixed frequency filters, that replicate the human logarithmic sensitivity to pitch. Because we are more sensitive to variations in low frequencies than high frequencies, mel filterbanks give more importance to the low-frequency range of sounds. Finally, the audio signal is compressed to mimic the ear’s logarithmic sensitivity to loudness — a sound needs to double its power for a person to perceive an increase of 3 decibels.

LEAF loosely follows this traditional approach to mel filterbank generation, but replaces each of the fixed operations (i.e., the filtering layer, windowing layer, and compression function) by a learned counterpart. The output of LEAF is a time-frequency representation (a spectrogram) similar to mel filterbanks, but fully learnable. So, for example, while a mel filterbank uses a fixed scale for pitch, LEAF learns the scale that is best suited to the task of interest. Any model that can be trained using mel filterbanks as input features, can also be trained on LEAF spectrograms.

Diagram of computation of mel filterbanks compared to LEAF spectrograms.

While LEAF can be initialized randomly, it can also be initialized in a way that approximates mel filterbanks, which have been shown to be a better starting point. Then, LEAF can be trained with any classifier to adapt to the task of interest.

Left: Mel filterbanks for a person saying “wow”. Right: LEAF’s output for the same example, after training on a dataset of speech commands.

A Parameter-Efficient Alternative to Fixed Features
A potential downside of replacing fixed features that involve no learnable parameter with a trainable system is that it can significantly increase the number of parameters to optimize. To avoid this issue, LEAF uses Gabor convolution layers that have only two parameters per filter, instead of the ~400 parameters typical of a standard convolution layer. This way, even when paired with a small classifier, such as EfficientNetB0, the LEAF model only accounts for 0.01% of the total parameters.

Top: Unconstrained convolutional filters after training for audio event classification. Bottom: LEAF filters at convergence after training for the same task.

Performance
We apply LEAF to diverse audio classification tasks, including recognizing speech commands, speaker identification, acoustic scene recognition, identifying musical instruments, and finding birdsongs. On average, LEAF outperforms both mel filterbanks and previous learnable frontends, such as Time-Domain Filterbanks, SincNet and Wavegram. In particular, LEAF achieves a 76.9% average accuracy across the different tasks, compared to 73.9% for mel filterbanks. Moreover we show that LEAF can be trained in a multi-task setting, such that a single LEAF parametrization can work well across all these tasks. Finally, when combined with a large audio classifier, LEAF reaches state-of-the-art performance on the challenging AudioSet benchmark, with a 2.74 d-prime score.

D-prime score (the higher the better) of LEAF, mel filterbanks and previously proposed learnable spectrograms on the evaluation set of AudioSet.

Conclusion
The scope of audio understanding tasks keeps growing, from diagnosing dementia from speech to detecting humpback whale calls from underwater microphones. Adapting mel filterbanks to every new task can require a significant amount of hand-tuning and experimentation. In this context, LEAF provides a drop-in replacement for these fixed features, that can be trained to adapt to the task of interest, with minimal task-specific adjustments. Thus, we believe that LEAF can accelerate development of models for new audio understanding tasks.

Acknowledgements
We thank our co-authors, Olivier Teboul, Félix de Chaumont-Quitry and Marco Tagliasacchi. We also thank Dick Lyon, Vincent Lostanlen, Matt Harvey, and Alex Park for helpful discussions, and Julie Thomas for helping to design figures for this post.

Categories
Offsites

torch time series continued: A first go at multi-step prediction

We pick up where the first post in this series left us: confronting the task of multi-step time-series forecasting.

Our first attempt was a workaround of sorts. The model had been trained to deliver a single prediction, corresponding to the very next point in time. Thus, if we needed a longer forecast, all we could do is use that prediction and feed it back to the model, moving the input sequence by one value (from ([x_{t-n}, …, x_t]) to ([x_{t-n-1}, …, x_{t+1}]), say).

In contrast, the new model will be designed – and trained – to forecast a configurable number of observations at once. The architecture will still be basic – about as basic as possible, given the task – and thus, can serve as a baseline for later attempts.

Data input

We work with the same data as before, vic_elec from tsibbledata.

Compared to last time though, the dataset class has to change. While, previously, for each batch item the target (y) was a single value, it now is a vector, just like the input, x. And just like n_timesteps was (and still is) used to specify the length of the input sequence, there is now a second parameter, n_forecast, to configure target size.

In our example, n_timesteps and n_forecast are set to the same value, but there is no need for this to be the case. You could equally well train on week-long sequences and then forecast developments over a single day, or a month.

Apart from the fact that .getitem() now returns a vector for y as well as x, there is not much to be said about dataset creation. Here is the complete code to set up the data input pipeline:

n_timesteps <- 7 * 24 * 2
n_forecast <- 7 * 24 * 2 
batch_size <- 32

vic_elec_get_year <- function(year, month = NULL) {
  vic_elec %>%
    filter(year(Date) == year, month(Date) == if (is.null(month)) month(Date) else month) %>%
    as_tibble() %>%
    select(Demand)
}

elec_train <- vic_elec_get_year(2012) %>% as.matrix()
elec_valid <- vic_elec_get_year(2013) %>% as.matrix()
elec_test <- vic_elec_get_year(2014, 1) %>% as.matrix()

train_mean <- mean(elec_train)
train_sd <- sd(elec_train)

elec_dataset <- dataset(
  name = "elec_dataset",
  
  initialize = function(x, n_timesteps, n_forecast, sample_frac = 1) {
    
    self$n_timesteps <- n_timesteps
    self$n_forecast <- n_forecast
    self$x <- torch_tensor((x - train_mean) / train_sd)
    
    n <- length(self$x) - self$n_timesteps - self$n_forecast + 1
    
    self$starts <- sort(sample.int(
      n = n,
      size = n * sample_frac
    ))
    
  },
  
  .getitem = function(i) {
    
    start <- self$starts[i]
    end <- start + self$n_timesteps - 1
    pred_length <- self$n_forecast
    
    list(
      x = self$x[start:end],
      y = self$x[(end + 1):(end + pred_length)]$squeeze(2)
    )
    
  },
  
  .length = function() {
    length(self$starts) 
  }
)

train_ds <- elec_dataset(elec_train, n_timesteps, n_forecast, sample_frac = 0.5)
train_dl <- train_ds %>% dataloader(batch_size = batch_size, shuffle = TRUE)

valid_ds <- elec_dataset(elec_valid, n_timesteps, n_forecast, sample_frac = 0.5)
valid_dl <- valid_ds %>% dataloader(batch_size = batch_size)

test_ds <- elec_dataset(elec_test, n_timesteps, n_forecast)
test_dl <- test_ds %>% dataloader(batch_size = 1)

Model

The model replaces the single linear layer that, in the previous post, had been tasked with outputting the final prediction, with a small network, complete with two linear layers and – optional – dropout.

In forward(), we first apply the RNN, and just like in the previous post, we make use of the outputs only; or more specifically, the output corresponding to the final time step. (See that previous post for a detailed discussion of what a torch RNN returns.)

model <- nn_module(
  
  initialize = function(type, input_size, hidden_size, linear_size, output_size,
                        num_layers = 1, dropout = 0, linear_dropout = 0) {
    
    self$type <- type
    self$num_layers <- num_layers
    self$linear_dropout <- linear_dropout
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    }
    
    self$mlp <- nn_sequential(
      nn_linear(hidden_size, linear_size),
      nn_relu(),
      nn_dropout(linear_dropout),
      nn_linear(linear_size, output_size)
    )
    
  },
  
  forward = function(x) {
    
    x <- self$rnn(x)
    x[[1]][ ,-1, ..] %>% 
      self$mlp()
    
  }
  
)

For model instantiation, we now have an additional configuration parameter, related to the amount of dropout between the two linear layers.

net <- model(
  "gru", input_size = 1, hidden_size = 32, linear_size = 512, output_size = n_forecast, linear_dropout = 0
  )

# training RNNs on the GPU currently prints a warning that may clutter 
# the console
# see https://github.com/mlverse/torch/issues/461
# alternatively, use 
# device <- "cpu"
device <- torch_device(if (cuda_is_available()) "cuda" else "cpu")

net <- net$to(device = device)

Training

The training procedure is completely unchanged.

optimizer <- optim_adam(net$parameters, lr = 0.001)

num_epochs <- 30

train_batch <- function(b) {
  
  optimizer$zero_grad()
  output <- net(b$x$to(device = device))
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$backward()
  optimizer$step()
  
  loss$item()
}

valid_batch <- function(b) {
  
  output <- net(b$x$to(device = device))
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$item()
  
}

for (epoch in 1:num_epochs) {
  
  net$train()
  train_loss <- c()
  
  coro::loop(for (b in train_dl) {
    loss <-train_batch(b)
    train_loss <- c(train_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, training: loss: %3.5f n", epoch, mean(train_loss)))
  
  net$eval()
  valid_loss <- c()
  
  coro::loop(for (b in valid_dl) {
    loss <- valid_batch(b)
    valid_loss <- c(valid_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, validation: loss: %3.5f n", epoch, mean(valid_loss)))
}
# Epoch 1, training: loss: 0.65737 
# 
# Epoch 1, validation: loss: 0.54586 
# 
# Epoch 2, training: loss: 0.43991 
# 
# Epoch 2, validation: loss: 0.50588 
# 
# Epoch 3, training: loss: 0.42161 
# 
# Epoch 3, validation: loss: 0.50031 
# 
# Epoch 4, training: loss: 0.41718 
# 
# Epoch 4, validation: loss: 0.48703 
# 
# Epoch 5, training: loss: 0.39498 
# 
# Epoch 5, validation: loss: 0.49572 
# 
# Epoch 6, training: loss: 0.38073 
# 
# Epoch 6, validation: loss: 0.46813 
# 
# Epoch 7, training: loss: 0.36472 
# 
# Epoch 7, validation: loss: 0.44957 
# 
# Epoch 8, training: loss: 0.35058 
# 
# Epoch 8, validation: loss: 0.44440 
# 
# Epoch 9, training: loss: 0.33880 
# 
# Epoch 9, validation: loss: 0.41995 
# 
# Epoch 10, training: loss: 0.32545 
# 
# Epoch 10, validation: loss: 0.42021 
# 
# Epoch 11, training: loss: 0.31347 
# 
# Epoch 11, validation: loss: 0.39514 
# 
# Epoch 12, training: loss: 0.29622 
# 
# Epoch 12, validation: loss: 0.38146 
# 
# Epoch 13, training: loss: 0.28006 
# 
# Epoch 13, validation: loss: 0.37754 
# 
# Epoch 14, training: loss: 0.27001 
# 
# Epoch 14, validation: loss: 0.36636 
# 
# Epoch 15, training: loss: 0.26191 
# 
# Epoch 15, validation: loss: 0.35338 
# 
# Epoch 16, training: loss: 0.25533 
# 
# Epoch 16, validation: loss: 0.35453 
# 
# Epoch 17, training: loss: 0.25085 
# 
# Epoch 17, validation: loss: 0.34521 
# 
# Epoch 18, training: loss: 0.24686 
# 
# Epoch 18, validation: loss: 0.35094 
# 
# Epoch 19, training: loss: 0.24159 
# 
# Epoch 19, validation: loss: 0.33776 
# 
# Epoch 20, training: loss: 0.23680 
# 
# Epoch 20, validation: loss: 0.33974 
# 
# Epoch 21, training: loss: 0.23070 
# 
# Epoch 21, validation: loss: 0.34069 
# 
# Epoch 22, training: loss: 0.22761 
# 
# Epoch 22, validation: loss: 0.33724 
# 
# Epoch 23, training: loss: 0.22390 
# 
# Epoch 23, validation: loss: 0.34013 
# 
# Epoch 24, training: loss: 0.22155 
# 
# Epoch 24, validation: loss: 0.33460 
# 
# Epoch 25, training: loss: 0.21820 
# 
# Epoch 25, validation: loss: 0.33755 
# 
# Epoch 26, training: loss: 0.22134 
# 
# Epoch 26, validation: loss: 0.33678 
# 
# Epoch 27, training: loss: 0.21061 
# 
# Epoch 27, validation: loss: 0.33108 
# 
# Epoch 28, training: loss: 0.20496 
# 
# Epoch 28, validation: loss: 0.32769 
# 
# Epoch 29, training: loss: 0.20223 
# 
# Epoch 29, validation: loss: 0.32969 
# 
# Epoch 30, training: loss: 0.20022 
# 
# Epoch 30, validation: loss: 0.33331 

From the way loss decreases on the training set, we conclude that, yes, the model is learning something. It probably would continue improving for quite some epochs still. We do, however, see less of an improvement on the validation set.

Naturally, now we’re curious about test-set predictions. (Remember, for testing we’re choosing the “particularly hard” month of January, 2014 – particularly hard because of a heatwave that resulted in exceptionally high demand.)

Evaluation

With no loop to be coded, evaluation now becomes pretty straightforward:

net$eval()

test_preds <- vector(mode = "list", length = length(test_dl))

i <- 1

coro::loop(for (b in test_dl) {
  
  input <- b$x
  output <- net(input$to(device = device))
  preds <- as.numeric(output)
  
  test_preds[[i]] <- preds
  i <<- i + 1
  
})

vic_elec_jan_2014 <- vic_elec %>%
  filter(year(Date) == 2014, month(Date) == 1)

test_pred1 <- test_preds[[1]]
test_pred1 <- c(rep(NA, n_timesteps), test_pred1, rep(NA, nrow(vic_elec_jan_2014) - n_timesteps - n_forecast))

test_pred2 <- test_preds[[408]]
test_pred2 <- c(rep(NA, n_timesteps + 407), test_pred2, rep(NA, nrow(vic_elec_jan_2014) - 407 - n_timesteps - n_forecast))

test_pred3 <- test_preds[[817]]
test_pred3 <- c(rep(NA, nrow(vic_elec_jan_2014) - n_forecast), test_pred3)


preds_ts <- vic_elec_jan_2014 %>%
  select(Demand) %>%
  add_column(
    mlp_ex_1 = test_pred1 * train_sd + train_mean,
    mlp_ex_2 = test_pred2 * train_sd + train_mean,
    mlp_ex_3 = test_pred3 * train_sd + train_mean) %>%
  pivot_longer(-Time) %>%
  update_tsibble(key = name)


preds_ts %>%
  autoplot() +
  scale_colour_manual(values = c("#08c5d1", "#00353f", "#ffbf66", "#d46f4d")) +
  theme_minimal()
One-week-ahead predictions for January, 2014.

(#fig:unnamed-chunk-6)One-week-ahead predictions for January, 2014.

Compare this to the forecast obtained by feeding back predictions. The demand profiles over the day look a lot more realistic now. How about the phases of extreme demand? Evidently, these are not reflected in the forecast, not any more than in the “loop technique”. In fact, the forecast allows for interesting insights into this model’s personality: Apparently, it really likes fluctuating around the mean – “prime” it with inputs that oscillate around a significantly higher level, and it will quickly shift back to its comfort zone.

Discussion

Seeing how, above, we provided an option to use dropout inside the MLP, you may be wondering if this would help with forecasts on the test set. Turns out it did not, in my experiments. Maybe this is not so strange either: How, absent external cues (temperature), should the network know that high demand is coming up?

In our analysis, we can make an additional distinction. With the first week of predictions, what we see is a failure to anticipate something that could not reasonably have been anticipated (two, or two-and-a-half, say, days of exceptionally high demand). In the second, all the network would have had to do was stay at the current, elevated level. It will be interesting to see how this is handled by the architectures we discuss next.

Finally, an additional idea you may have had is – what if we used temperature as a second input variable? As a matter of fact, training performance indeed improved, but no performance impact was observed on the validation and test sets. Still, you may find the code useful – it is easily extended to datasets with more predictors. Therefore, we reproduce it in the appendix.

Thanks for reading!

Appendix

# Data input code modified to accommodate two predictors

n_timesteps <- 7 * 24 * 2
n_forecast <- 7 * 24 * 2

vic_elec_get_year <- function(year, month = NULL) {
  vic_elec %>%
    filter(year(Date) == year, month(Date) == if (is.null(month)) month(Date) else month) %>%
    as_tibble() %>%
    select(Demand, Temperature)
}

elec_train <- vic_elec_get_year(2012) %>% as.matrix()
elec_valid <- vic_elec_get_year(2013) %>% as.matrix()
elec_test <- vic_elec_get_year(2014, 1) %>% as.matrix()

train_mean_demand <- mean(elec_train[ , 1])
train_sd_demand <- sd(elec_train[ , 1])

train_mean_temp <- mean(elec_train[ , 2])
train_sd_temp <- sd(elec_train[ , 2])

elec_dataset <- dataset(
  name = "elec_dataset",
  
  initialize = function(data, n_timesteps, n_forecast, sample_frac = 1) {
    
    demand <- (data[ , 1] - train_mean_demand) / train_sd_demand
    temp <- (data[ , 2] - train_mean_temp) / train_sd_temp
    self$x <- cbind(demand, temp) %>% torch_tensor()
    
    self$n_timesteps <- n_timesteps
    self$n_forecast <- n_forecast
    
    n <- nrow(self$x) - self$n_timesteps - self$n_forecast + 1
    self$starts <- sort(sample.int(
      n = n,
      size = n * sample_frac
    ))
    
  },
  
  .getitem = function(i) {
    
    start <- self$starts[i]
    end <- start + self$n_timesteps - 1
    pred_length <- self$n_forecast
    
    list(
      x = self$x[start:end, ],
      y = self$x[(end + 1):(end + pred_length), 1]
    )
    
  },
  
  .length = function() {
    length(self$starts)
  }
  
)

### rest identical to single-predictor code above

Photo by Monica Bourgeau on Unsplash

Categories
Offsites

Introductory time series forecasting with torch

This is the first post in a series introducing time-series forecasting with torch. It does assume some prior experience with torch and/or deep learning. But as far as time series are concerned, it starts right from the beginning, using recurrent neural networks (GRU or LSTM) to predict how something develops in time.

In this post, we build a network that uses a sequence of observations to predict a value for the very next point in time. What if we’d like to forecast a sequence of values, corresponding to, say, a week or a month of measurements?

One thing we could do is feed back into the system the previously forecasted value; this is something we’ll try at the end of this post. Subsequent posts will explore other options, some of them involving significantly more complex architectures. It will be interesting to compare their performances; but the essential goal is to introduce some torch “recipes” that you can apply to your own data.

We start by examining the dataset used. It is a low-dimensional, but pretty polyvalent and complex one.

Time-series inspection

The vic_elec dataset, available through package tsibbledata, provides three years of half-hourly electricity demand for Victoria, Australia, augmented by same-resolution temperature information and a daily holiday indicator.

library(tidyverse)
library(lubridate)

library(tsibble) # Tidy Temporal Data Frames and Tools
library(feasts) # Feature Extraction and Statistics for Time Series
library(tsibbledata) # Diverse Datasets for 'tsibble'

vic_elec %>% glimpse()
Rows: 52,608
Columns: 5
$ Time        <dttm> 2012-01-01 00:00:00, 2012-01-01 00:30:00, 2012-01-01 01:00:00,…
$ Demand      <dbl> 4382.825, 4263.366, 4048.966, 3877.563, 4036.230, 3865.597, 369…
$ Temperature <dbl> 21.40, 21.05, 20.70, 20.55, 20.40, 20.25, 20.10, 19.60, 19.10, …
$ Date        <date> 2012-01-01, 2012-01-01, 2012-01-01, 2012-01-01, 2012-01-01, 20…
$ Holiday     <lgl> TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRU…

Depending on what subset of variables is used, and whether and how data is temporally aggregated, these data may serve to illustrate a variety of different techniques. For example, in the third edition of Forecasting: Principles and Practice daily averages are used to teach quadratic regression with ARMA errors. In this first introductory post though, as well as in most of its successors, we’ll attempt to forecast Demand without relying on additional information, and we keep the original resolution.

To get an impression of how electricity demand varies over different timescales. Let’s inspect data for two months that nicely illustrate the U-shaped relationship between temperature and demand: January, 2014 and July, 2014.

First, here is July.

vic_elec_2014 <-  vic_elec %>%
  filter(year(Date) == 2014) %>%
  select(-c(Date, Holiday)) %>%
  mutate(Demand = scale(Demand), Temperature = scale(Temperature)) %>%
  pivot_longer(-Time, names_to = "variable") %>%
  update_tsibble(key = variable)

vic_elec_2014 %>% filter(month(Time) == 7) %>% 
  autoplot() + 
  scale_colour_manual(values = c("#08c5d1", "#00353f")) +
  theme_minimal()
Temperature and electricity demand (normalized). Victoria, Australia, 07/2014.

(#fig:unnamed-chunk-3)Temperature and electricity demand (normalized). Victoria, Australia, 07/2014.

It’s winter; temperature fluctuates below average, while electricity demand is above average (heating). There is strong variation over the course of the day; we see troughs in the demand curve corresponding to ridges in the temperature graph, and vice versa. While diurnal variation dominates, there also is variation over the days of the week. Between weeks though, we don’t see much difference.

Compare this with the data for January:

vic_elec_2014 %>% filter(month(Time) == 1) %>% 
  autoplot() + 
  scale_colour_manual(values = c("#08c5d1", "#00353f")) +
  theme_minimal()
Temperature and electricity demand (normalized). Victoria, Australia, 01/2014.

(#fig:unnamed-chunk-5)Temperature and electricity demand (normalized). Victoria, Australia, 01/2014.

We still see the strong circadian variation. We still see some day-of-week variation. But now it is high temperatures that cause elevated demand (cooling). Also, there are two periods of unusually high temperatures, accompanied by exceptional demand. We anticipate that in a univariate forecast, not taking into account temperature, this will be hard – or even, impossible – to forecast.

Let’s see a concise portrait of how Demand behaves using feasts::STL(). First, here is the decomposition for July:

vic_elec_2014 <-  vic_elec %>%
  filter(year(Date) == 2014) %>%
  select(-c(Date, Holiday))

cmp <- vic_elec_2014 %>% filter(month(Time) == 7) %>%
  model(STL(Demand)) %>% 
  components()

cmp %>% autoplot()
STL decomposition of electricity demand. Victoria, Australia, 07/2014.

(#fig:unnamed-chunk-7)STL decomposition of electricity demand. Victoria, Australia, 07/2014.

And here, for January:

STL decomposition of electricity demand. Victoria, Australia, 01/2014.

(#fig:unnamed-chunk-8)STL decomposition of electricity demand. Victoria, Australia, 01/2014.

Both nicely illustrate the strong circadian and weekly seasonalities (with diurnal variation substantially stronger in January). If we look closely, we can even see how the trend component is more influential in January than in July. This again hints at much stronger difficulties predicting the January than the July developments.

Now that we have an idea what awaits us, let’s begin by creating a torch dataset.

Data input

Here is what we intend to do. We want to start our journey into forecasting by using a sequence of observations to predict their immediate successor. In other words, the input (x) for each batch item is a vector, while the target (y) is a single value. The length of the input sequence, x, is parameterized as n_timesteps, the number of consecutive observations to extrapolate from.

The dataset will reflect this in its .getitem() method. When asked for the observations at index i, it will return tensors like so:

list(
      x = self$x[start:end],
      y = self$x[end+1]
)

where start:end is a vector of indices, of length n_timesteps, and end+1 is a single index.

Now, if the dataset just iterated over its input in order, advancing the index one at a time, these lines could simply read

list(
      x = self$x[i:(i + self$n_timesteps - 1)],
      y = self$x[self$n_timesteps + 1]
)

Since many sequences in the data are similar, we can reduce training time by making use of a fraction of the data in every epoch. This can be accomplished by (optionally) passing a sample_frac smaller than 1. In initialize(), a random set of start indices is prepared; .getitem() then just does what it normally does: look for the (x,y) pair at a given index.

Here is the complete dataset code:

elec_dataset <- dataset(
  name = "elec_dataset",
  
  initialize = function(x, n_timesteps, sample_frac = 1) {

    self$n_timesteps <- n_timesteps
    self$x <- torch_tensor((x - train_mean) / train_sd)
    
    n <- length(self$x) - self$n_timesteps 
    
    self$starts <- sort(sample.int(
      n = n,
      size = n * sample_frac
    ))

  },
  
  .getitem = function(i) {
    
    start <- self$starts[i]
    end <- start + self$n_timesteps - 1
    
    list(
      x = self$x[start:end],
      y = self$x[end + 1]
    )

  },
  
  .length = function() {
    length(self$starts) 
  }
)

You may have noticed that we normalize the data by globally defined train_mean and train_sd. We yet have to calculate those.

The way we split the data is straightforward. We use the whole of 2012 for training, and all of 2013 for validation. For testing, we take the “difficult” month of January, 2014. You are invited to compare testing results for July that same year, and compare performances.

vic_elec_get_year <- function(year, month = NULL) {
  vic_elec %>%
    filter(year(Date) == year, month(Date) == if (is.null(month)) month(Date) else month) %>%
    as_tibble() %>%
    select(Demand)
}

elec_train <- vic_elec_get_year(2012) %>% as.matrix()
elec_valid <- vic_elec_get_year(2013) %>% as.matrix()
elec_test <- vic_elec_get_year(2014, 1) %>% as.matrix() # or 2014, 7, alternatively

train_mean <- mean(elec_train)
train_sd <- sd(elec_train)

Now, to instantiate a dataset, we still need to pick sequence length. From prior inspection, a week seems like a sensible choice.

n_timesteps <- 7 * 24 * 2 # days * hours * half-hours

Now we can go ahead and create a dataset for the training data. Let’s say we’ll make use of 50% of the data in each epoch:

train_ds <- elec_dataset(elec_train, n_timesteps, sample_frac = 0.5)
length(train_ds)
 8615

Quick check: Are the shapes correct?

train_ds[1]
$x
torch_tensor
-0.4141
-0.5541
[...]       ### lines removed by me
 0.8204
 0.9399
... [the output was truncated (use n=-1 to disable)]
[ CPUFloatType{336,1} ]

$y
torch_tensor
-0.6771
[ CPUFloatType{1} ]

Yes: This is what we wanted to see. The input sequence has n_timesteps values in the first dimension, and a single one in the second, corresponding to the only feature present, Demand. As intended, the prediction tensor holds a single value, corresponding– as we know – to n_timesteps+1.

That takes care of a single input-output pair. As usual, batching is arranged for by torch’s dataloader class. We instantiate one for the training data, and immediately again verify the outcome:

batch_size <- 32
train_dl <- train_ds %>% dataloader(batch_size = batch_size, shuffle = TRUE)
length(train_dl)

b <- train_dl %>% dataloader_make_iter() %>% dataloader_next()
b
$x
torch_tensor
(1,.,.) = 
  0.4805
  0.3125
[...]       ### lines removed by me
 -1.1756
 -0.9981
... [the output was truncated (use n=-1 to disable)]
[ CPUFloatType{32,336,1} ]

$y
torch_tensor
 0.1890
 0.5405
[...]       ### lines removed by me
 2.4015
 0.7891
... [the output was truncated (use n=-1 to disable)]
[ CPUFloatType{32,1} ]

We see the added batch dimension in front, resulting in overall shape (batch_size, n_timesteps, num_features). This is the format expected by the model, or more precisely, by its initial RNN layer.

Before we go on, let’s quickly create datasets and dataloaders for validation and test data, as well.

valid_ds <- elec_dataset(elec_valid, n_timesteps, sample_frac = 0.5)
valid_dl <- valid_ds %>% dataloader(batch_size = batch_size)

test_ds <- elec_dataset(elec_test, n_timesteps)
test_dl <- test_ds %>% dataloader(batch_size = 1)

Model

The model consists of an RNN – of type GRU or LSTM, as per the user’s choice – and an output layer. The RNN does most of the work; the single-neuron linear layer that outputs the prediction compresses its vector input to a single value.

Here, first, is the model definition.

model <- nn_module(
  
  initialize = function(type, input_size, hidden_size, num_layers = 1, dropout = 0) {
    
    self$type <- type
    self$num_layers <- num_layers
    
    self$rnn <- if (self$type == "gru") {
      nn_gru(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    } else {
      nn_lstm(
        input_size = input_size,
        hidden_size = hidden_size,
        num_layers = num_layers,
        dropout = dropout,
        batch_first = TRUE
      )
    }
    
    self$output <- nn_linear(hidden_size, 1)
    
  },
  
  forward = function(x) {
    
    # list of [output, hidden]
    # we use the output, which is of size (batch_size, n_timesteps, hidden_size)
    x <- self$rnn(x)[[1]]
    
    # from the output, we only want the final timestep
    # shape now is (batch_size, hidden_size)
    x <- x[ , dim(x)[2], ]
    
    # feed this to a single output neuron
    # final shape then is (batch_size, 1)
    x %>% self$output() 
  }
  
)

Most importantly, this is what happens in forward().

  1. The RNN returns a list. The list holds two tensors, an output, and a synopsis of hidden states. We discard the state tensor, and keep the output only. The distinction between state and output, or rather, the way it is reflected in what a torch RNN returns, deserves to be inspected more closely. We’ll do that in a second.

    x <- self$rnn(x)[[1]]
    
  2. Of the output tensor, we’re interested in only the final time-step, though.

    x <- x[ , dim(x)[2], ]
    
  3. Only this one, thus, is passed to the output layer.

    x %>% self$output()
    
  4. Finally, the said output layer’s output is returned.

Now, a bit more on states vs. outputs. Consider Fig. 1, from Goodfellow, Bengio, and Courville (2016).

Source: Goodfellow et al., Deep learning. Chapter URL: https://www.deeplearningbook.org/contents/rnn.html.

(#fig:unnamed-chunk-22)Source: Goodfellow et al., Deep learning. Chapter URL: https://www.deeplearningbook.org/contents/rnn.html.

Let’s pretend there are three time steps only, corresponding to (t-1), (t), and (t+1). The input sequence, accordingly, is composed of (x_{t-1}), (x_{t}), and (x_{t+1}).

At each (t), a hidden state is generated, and so is an output. Normally, if our goal is to predict (y_{t+2}), that is, the very next observation, we want to take into account the complete input sequence. Put differently, we want to have run through the complete machinery of state updates. The logical thing to do would thus be to choose (o_{t+1}), for either direct return from forward() or for further processing.

Indeed, return (o_{t+1}) is what a Keras LSTM or GRU would do by default.1 Not so its torch counterparts. In torch, the output tensor comprises all of (o). This is why, in step two above, we select the single time step we’re interested in – namely, the last one.

In later posts, we will make use of more than the last time step. Sometimes, we’ll use the sequence of hidden states (the (h)s) instead of the outputs (the (o)s). So you may feel like asking, what if we used (h_{t+1}) here instead of (o_{t+1})? The answer is: With a GRU, this would not make a difference, as those two are identical. With LSTM though, it would, as LSTM keeps a second, namely, the “cell”, state2.

On to initialize(). For ease of experimentation, we instantiate either a GRU or an LSTM based on user input. Two things are worth noting:

  • We pass batch_first = TRUE when creating the RNNs. This is required with torch RNNs when we want to consistently have batch items stacked in the first dimension. And we do want that; it is arguably less confusing than a change of dimension semantics for one sub-type of module.

  • num_layers can be used to build a stacked RNN, corresponding to what you’d get in Keras when chaining two GRUs/LSTMs (the first one created with return_sequences = TRUE). This parameter, too, we’ve included for quick experimentation.

Let’s instantiate a model for training. It will be a single-layer GRU with thirty-two units.

# training RNNs on the GPU currently prints a warning that may clutter 
# the console
# see https://github.com/mlverse/torch/issues/461
# alternatively, use 
# device <- "cpu"
device <- torch_device(if (cuda_is_available()) "cuda" else "cpu")

net <- model("gru", 1, 32)
net <- net$to(device = device)

Training

After all those RNN specifics, the training process is completely standard.

optimizer <- optim_adam(net$parameters, lr = 0.001)

num_epochs <- 30

train_batch <- function(b) {
  
  optimizer$zero_grad()
  output <- net(b$x$to(device = device))
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$backward()
  optimizer$step()
  
  loss$item()
}

valid_batch <- function(b) {
  
  output <- net(b$x$to(device = device))
  target <- b$y$to(device = device)
  
  loss <- nnf_mse_loss(output, target)
  loss$item()
  
}

for (epoch in 1:num_epochs) {
  
  net$train()
  train_loss <- c()
  
  coro::loop(for (b in train_dl) {
    loss <-train_batch(b)
    train_loss <- c(train_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, training: loss: %3.5f n", epoch, mean(train_loss)))
  
  net$eval()
  valid_loss <- c()
  
  coro::loop(for (b in valid_dl) {
    loss <- valid_batch(b)
    valid_loss <- c(valid_loss, loss)
  })
  
  cat(sprintf("nEpoch %d, validation: loss: %3.5f n", epoch, mean(valid_loss)))
}
Epoch 1, training: loss: 0.21908 

Epoch 1, validation: loss: 0.05125 

Epoch 2, training: loss: 0.03245 

Epoch 2, validation: loss: 0.03391 

Epoch 3, training: loss: 0.02346 

Epoch 3, validation: loss: 0.02321 

Epoch 4, training: loss: 0.01823 

Epoch 4, validation: loss: 0.01838 

Epoch 5, training: loss: 0.01522 

Epoch 5, validation: loss: 0.01560 

Epoch 6, training: loss: 0.01315 

Epoch 6, validation: loss: 0.01374 

Epoch 7, training: loss: 0.01205 

Epoch 7, validation: loss: 0.01200 

Epoch 8, training: loss: 0.01155 

Epoch 8, validation: loss: 0.01157 

Epoch 9, training: loss: 0.01118 

Epoch 9, validation: loss: 0.01096 

Epoch 10, training: loss: 0.01070 

Epoch 10, validation: loss: 0.01132 

Epoch 11, training: loss: 0.01003 

Epoch 11, validation: loss: 0.01150 

Epoch 12, training: loss: 0.00943 

Epoch 12, validation: loss: 0.01106 

Epoch 13, training: loss: 0.00922 

Epoch 13, validation: loss: 0.01069 

Epoch 14, training: loss: 0.00862 

Epoch 14, validation: loss: 0.01125 

Epoch 15, training: loss: 0.00842 

Epoch 15, validation: loss: 0.01095 

Epoch 16, training: loss: 0.00820 

Epoch 16, validation: loss: 0.00975 

Epoch 17, training: loss: 0.00802 

Epoch 17, validation: loss: 0.01120 

Epoch 18, training: loss: 0.00781 

Epoch 18, validation: loss: 0.00990 

Epoch 19, training: loss: 0.00757 

Epoch 19, validation: loss: 0.01017 

Epoch 20, training: loss: 0.00735 

Epoch 20, validation: loss: 0.00932 

Epoch 21, training: loss: 0.00723 

Epoch 21, validation: loss: 0.00901 

Epoch 22, training: loss: 0.00708 

Epoch 22, validation: loss: 0.00890 

Epoch 23, training: loss: 0.00676 

Epoch 23, validation: loss: 0.00914 

Epoch 24, training: loss: 0.00666 

Epoch 24, validation: loss: 0.00922 

Epoch 25, training: loss: 0.00644 

Epoch 25, validation: loss: 0.00869 

Epoch 26, training: loss: 0.00620 

Epoch 26, validation: loss: 0.00902 

Epoch 27, training: loss: 0.00588 

Epoch 27, validation: loss: 0.00896 

Epoch 28, training: loss: 0.00563 

Epoch 28, validation: loss: 0.00886 

Epoch 29, training: loss: 0.00547 

Epoch 29, validation: loss: 0.00895 

Epoch 30, training: loss: 0.00523 

Epoch 30, validation: loss: 0.00935 

Loss decreases quickly, and we don’t seem to be overfitting on the validation set.

Numbers are pretty abstract, though. So, we’ll use the test set to see how the forecast actually looks.

Evaluation

Here is the forecast for January, 2014, thirty minutes at a time.

net$eval()

preds <- rep(NA, n_timesteps)

coro::loop(for (b in test_dl) {
  output <- net(b$x$to(device = device))
  preds <- c(preds, output %>% as.numeric())
})

vic_elec_jan_2014 <-  vic_elec %>%
  filter(year(Date) == 2014, month(Date) == 1) %>%
  select(Demand)

preds_ts <- vic_elec_jan_2014 %>%
  add_column(forecast = preds * train_sd + train_mean) %>%
  pivot_longer(-Time) %>%
  update_tsibble(key = name)

preds_ts %>%
  autoplot() +
  scale_colour_manual(values = c("#08c5d1", "#00353f")) +
  theme_minimal()
One-step-ahead predictions for January, 2014.

(#fig:unnamed-chunk-26)One-step-ahead predictions for January, 2014.

Overall, the forecast is excellent, but it is interesting to see how the forecast “regularizes” the most extreme peaks. This kind of “regression to the mean” will be seen much more strongly in later setups, when we try to forecast further into the future.

Can we use our current architecture for multi-step prediction? We can.

One thing we can do is feed back the current prediction, that is, append it to the input sequence as soon as it is available. Effectively thus, for each batch item, we obtain a sequence of predictions in a loop.

We’ll try to forecast 336 time steps, that is, a complete week.

n_forecast <- 2 * 24 * 7

test_preds <- vector(mode = "list", length = length(test_dl))

i <- 1

coro::loop(for (b in test_dl) {
  
  input <- b$x
  output <- net(input$to(device = device))
  preds <- as.numeric(output)
  
  for(j in 2:n_forecast) {
    input <- torch_cat(list(input[ , 2:length(input), ], output$view(c(1, 1, 1))), dim = 2)
    output <- net(input$to(device = device))
    preds <- c(preds, as.numeric(output))
  }
  
  test_preds[[i]] <- preds
  i <<- i + 1
  
})

For visualization, let’s pick three non-overlapping sequences.

test_pred1 <- test_preds[[1]]
test_pred1 <- c(rep(NA, n_timesteps), test_pred1, rep(NA, nrow(vic_elec_jan_2014) - n_timesteps - n_forecast))

test_pred2 <- test_preds[[408]]
test_pred2 <- c(rep(NA, n_timesteps + 407), test_pred2, rep(NA, nrow(vic_elec_jan_2014) - 407 - n_timesteps - n_forecast))

test_pred3 <- test_preds[[817]]
test_pred3 <- c(rep(NA, nrow(vic_elec_jan_2014) - n_forecast), test_pred3)


preds_ts <- vic_elec %>%
  filter(year(Date) == 2014, month(Date) == 1) %>%
  select(Demand) %>%
  add_column(
    iterative_ex_1 = test_pred1 * train_sd + train_mean,
    iterative_ex_2 = test_pred2 * train_sd + train_mean,
    iterative_ex_3 = test_pred3 * train_sd + train_mean) %>%
  pivot_longer(-Time) %>%
  update_tsibble(key = name)

preds_ts %>%
  autoplot() +
  scale_colour_manual(values = c("#08c5d1", "#00353f", "#ffbf66", "#d46f4d")) +
  theme_minimal()
Multi-step predictions for January, 2014, obtained in a loop.

(#fig:unnamed-chunk-29)Multi-step predictions for January, 2014, obtained in a loop.

Even with this very basic forecasting technique, the diurnal rhythm is preserved, albeit in a strongly smoothed form. There even is an apparent day-of-week periodicity in the forecast. We do see, however, very strong regression to the mean, even in loop instances where the network was “primed” with a higher input sequence.

Conclusion

Hopefully this post provided a useful introduction to time series forecasting with torch. Evidently, we picked a challenging time series – challenging, that is, for at least two reasons:

  • To correctly factor in the trend, external information is needed: external information in form of a temperature forecast, which, “in reality”, would be easily obtainable.

  • In addition to the highly important trend component, the data are characterized by multiple levels..

Categories
Offsites

A New Lens on Understanding Generalization in Deep Learning

Understanding generalization is one of the fundamental unsolved problems in deep learning. Why does optimizing a model on a finite set of training data lead to good performance on a held-out test set? This problem has been studied extensively in machine learning, with a rich history going back more than 50 years. There are now many mathematical tools that help researchers understand generalization in certain models. Unfortunately, most of these existing theories fail when applied to modern deep networks — they are both vacuous and non-predictive in realistic settings. This gap between theory and practice is largest for overparameterized models, which in theory have the capacity to overfit their train sets, but often do not in practice.

In “The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers”, accepted at ICLR 2021, we present a new framework for approaching this problem by connecting generalization to the field of online optimization. In a typical setting, a model trains on a finite set of samples, which are reused for multiple epochs. But in online optimization, the model has access to an infinite stream of samples, and can be iteratively updated while processing this stream. In this work, we find that models that train quickly on infinite data are the same models that generalize well if they are instead trained on finite data. This connection brings new perspectives on design choices in practice, and lays a roadmap for understanding generalization from a theoretical perspective.

The Deep Bootstrap Framework
The main idea of the Deep Bootstrap framework is to compare the real world, where there is finite training data, to an “ideal world”, where there is infinite data. We define these as:

  • Real World (N, T): Train a model on N train samples from a distribution, for T minibatch stochastic gradient descent (SGD) steps, re-using the same N samples in multiple epochs, as usual. This corresponds to running SGD on the empirical loss (loss on training data), and is the standard training procedure in supervised learning.
  • Ideal World (T): Train the same model for T steps, but use fresh samples from the distribution in each SGD step. That is, we run the exact same training code (same optimizer, learning-rates, batch-size, etc.), but sample a fresh train set in each epoch instead of reusing samples. In this ideal world setting, with an effectively infinite “train set”, there is no difference between train error and test error.
Test soft-error for ideal world and real world during SGD iterations for ResNet-18 architecture. We see that the two errors are similar.

A priori, one might expect the real and ideal worlds may have nothing to do with each other, since in the real world the model sees a finite number of examples from the distribution while in the ideal world the model sees the whole distribution. But in practice, we found that the real and ideal models actually have similar test error.

In order to quantify this observation, we simulated an ideal world setting by creating a new dataset, which we call CIFAR-5m. We trained a generative model on CIFAR-10, which we then used to generate ~6 million images. The scale of the dataset was chosen to ensure that it is “virtually infinite” from the model’s perspective, so that the model never resamples the same data. That is, in the ideal world, the model sees an entirely fresh set of samples.

Samples from CIFAR-5m

The figure below presents the test error of several models, comparing their performance when trained on CIFAR-5m data in the real world setting (i.e., re-used data) and the ideal world (“fresh” data). The solid blue line shows a ResNet model in the real world, trained on 50K samples for 100 epochs with standard CIFAR-10 hyperparameters. The dashed blue line shows the corresponding model in the ideal world, trained on 5 million samples in a single pass. Surprisingly, these worlds have very similar test error — the model in some sense “doesn’t care” whether it sees re-used samples or fresh ones.

The real world model is trained on 50K samples for 100 epochs, and the ideal world model is trained on 5M samples for a single epoch. The lines show the test error vs. the number of SGD steps.

This also holds for other architectures, e.g., a Multi-Layer-Perceptron (red), a Vision Transformer (green), and across many other settings of architecture, optimizer, data distribution, and sample size. These experiments suggest a new perspective on generalization: models that optimize quickly (on infinite data), generalize well (on finite data). For example, the ResNet model generalizes better than the MLP model on finite data, but this is “because” it optimizes faster even on infinite data.

Understanding Generalization from Optimization Behavior
The key observation is that real world and ideal world models remain close, in test error, for all timesteps, until the real world converges (< 1% train error). Thus, one can study models in the real world by studying their corresponding behavior in the ideal world.

This means that the generalization of the model can be understood in terms of its optimization performance under two frameworks:

  1. Online Optimization: How fast the ideal world test error decreases
  2. Offline Optimization: How fast the real world train error converges

Thus, to study generalization, we can equivalently study the two terms above, which can be conceptually simpler, since they only involve optimization concerns. Based on this observation, good models and training procedures are those that (1) optimize quickly in the ideal world and (2) do not optimize too quickly in the real world.

All design choices in deep learning can be viewed through their effect on these two terms. For example, some advances like convolutions, skip-connections, and pretraining help primarily by accelerating ideal world optimization, while other advances like regularization and data-augmentation help primarily by decelerating real world optimization.

Applying the Deep Bootstrap Framework
Researchers can use the Deep Bootstrap framework to study and guide design choices in deep learning. The principle is: whenever one makes a change that affects generalization in the real world (the architecture, learning-rate, etc.), one should consider its effect on (1) the ideal world optimization of test error (faster is better) and (2) the real world optimization of train error (slower is better).

For example, pre-training is often used in practice to help generalization of models in small-data regimes. However, the reason that pre-training helps remains poorly understood. One can study this using the Deep Bootstrap framework by looking at the effect of pre-training on terms (1) and (2) above. We find that the primary effect of pre-training is to improve the ideal world optimization (1) — pre-training turns the network into a “fast learner” for online optimization. The improved generalization of pretrained models is thus almost exactly captured by their improved optimization in the ideal world. The figure below shows this for Vision-Transformers (ViT) trained on CIFAR-10, comparing training from scratch vs. pre-training on ImageNet.

Effect of pre-training — pre-trained ViTs optimize faster in the ideal world.

One can also study data-augmentation using this framework. Data-augmentation in the ideal world corresponds to augmenting each fresh sample once, as opposed to augmenting the same sample multiple times. This framework implies that good data-augmentations are those that (1) do not significantly harm ideal world optimization (i.e., augmented samples don’t look too “out of distribution”) or (2) inhibit real world optimization speed (so the real world takes longer to fit its train set).

The main benefit of data-augmentation is through the second term, prolonging the real world optimization time. As for the first term, some aggressive data augmentations (mixup/cutout) can actually harm the ideal world, but this effect is dwarfed by the second term.

Concluding Thoughts
The Deep Bootstrap framework provides a new lens on generalization and empirical phenomena in deep learning. We are excited to see it applied to understand other aspects of deep learning in the future. It is especially interesting that generalization can be characterized via purely optimization considerations, which is in contrast to many prevailing approaches in theory. Crucially, we consider both online and offline optimization, which are individually insufficient, but that together determine generalization.

The Deep Bootstrap framework can also shed light on why deep learning is fairly robust to many design choices: many kinds of architectures, loss functions, optimizers, normalizations, and activation functions can generalize well. This framework suggests a unifying principle: that essentially any choice that works well in the online optimization setting will also generalize well in the offline setting.

Finally, modern neural networks can be either overparameterized (e.g., large networks trained on small data tasks) or underparmeterized (e.g., OpenAI’s GPT-3, Google’s T5, or Facebook’s ResNeXt WSL). The Deep Bootstrap framework implies that online optimization is a crucial factor to success in both regimes.

Acknowledgements
We are thankful to our co-author, Behnam Neyshabur, for his great contributions to the paper and valuable feedback on the blog. We thank Boaz Barak, Chenyang Yuan, and Chiyuan Zhang for helpful comments on the blog and paper.

Categories
Offsites

Accelerating Neural Networks on Mobile and Web with Sparse Inference

On-device inference of neural networks enables a variety of real-time applications, like pose estimation and background blur, in a low-latency and privacy-conscious way. Using ML inference frameworks like TensorFlow Lite with XNNPACK ML acceleration library, engineers optimize their models to run on a variety of devices by finding a sweet spot between model size, inference speed and the quality of the predictions.

One way to optimize a model is through use of sparse neural networks [1, 2, 3], which have a significant fraction of their weights set to zero. In general, this is a desirable quality as it not only reduces the model size via compression, but also makes it possible to skip a significant fraction of multiply-add operations, thereby speeding up inference. Further, it is possible to increase the number of parameters in a model and then sparsify it to match the quality of the original model, while still benefiting from the accelerated inference. However, the use of this technique remains limited in production largely due to a lack of tools to sparsify popular convolutional architectures as well as insufficient support for running these operations on-device.

Today we announce the release of a set of new features for the XNNPACK acceleration library and TensorFlow Lite that enable efficient inference of sparse networks, along with guidelines on how to sparsify neural networks, with the goal of helping researchers develop their own sparse on-device models. Developed in collaboration with DeepMind, these tools power a new generation of live perception experiences, including hand tracking in MediaPipe and background features in Google Meet, accelerating inference speed from 1.2 to 2.4 times, while reducing the model size by half. In this post, we provide a technical overview of sparse neural networks — from inducing sparsity during training to on-device deployment — and offer some ideas on how researchers might create their own sparse models.

Comparison of the processing time for the dense (left) and sparse (right) models of the same quality for Google Meet background features. For readability, the processing time shown is the moving average across 100 frames.

Sparsifying a Neural Network
Many modern deep learning architectures, like MobileNet and EfficientNetLite, are primarily composed of depthwise convolutions with a small spatial kernel and 1×1 convolutions that linearly combine features from the input image. While such architectures have a number of potential targets for sparsification, including the full 2D convolutions that frequently occur at the beginning of many networks or the depthwise convolutions, it is the 1×1 convolutions that are the most expensive operators as measured by inference time. Because they account for over 65% of the total compute, they are an optimal target for sparsification.

Architecture Inference Time
MobileNet 85%
MobileNetV2 71%
MobileNetV3 71%
EfficientNet-Lite   66%
Comparison of inference time dedicated to 1×1 convolutions in % for modern mobile architectures.

In modern on-device inference engines, like XNNPACK, the implementation of 1×1 convolutions as well as other operations in the deep learning models rely on the HWC tensor layout, in which the tensor dimensions correspond to the height, width, and channel (e.g., red, green or blue) of the input image. This tensor configuration allows the inference engine to process the channels corresponding to each spatial location (i.e., each pixel of an image) in parallel. However, this ordering of the tensor is not a good fit for sparse inference because it sets the channel as the innermost dimension of the tensor and makes it more computationally expensive to access.

Our updates to XNNPACK enable it to detect if a model is sparse. If so, it switches from its standard dense inference mode to sparse inference mode, in which it employs a CHW (channel, height, width) tensor layout. This reordering of the tensor allows for an accelerated implementation of the sparse 1×1 convolution kernel for two reasons: 1) entire spatial slices of the tensor can be skipped when the corresponding channel weight is zero following a single condition check, instead of a per-pixel test; and 2) when the channel weight is non-zero, the computation can be made more efficient by loading neighbouring pixels into the same memory unit. This enables us to process multiple pixels simultaneously, while also performing each operation in parallel across several threads. Together these changes result in a speed-up of 1.8x to 2.3x when at least 80% of the weights are zero.

In order to avoid converting back and forth between the CHW tensor layout that is optimal for sparse inference and the standard HWC tensor layout after each operation, XNNPACK provides efficient implementations of several CNN operators in CHW layout.

Guidelines for Training Sparse Neural Networks
To create a sparse neural network, the guidelines included in this release suggest one start with a dense version and then gradually set a fraction of its weights to zero during training. This process is called pruning. Of the many available techniques for pruning, we recommend using magnitude pruning (available in the TF Model Optimization Toolkit) or the recently introduced RigL method. With a modest increase in training time, both of these can successfully sparsify deep learning models without degrading their quality. The resulting sparse models can be stored efficiently in a compressed format that reduces the size by a factor of two compared to their dense equivalent.

The quality of sparse networks is influenced by several hyperparameters, including training time, learning rate and schedules for pruning. The TF Pruning API provides an excellent example of how to select these, as well as some tips for training such models. We recommend running hyperparameter searches to find the sweet spot for your application.

Applications
We demonstrate that it is possible to sparsify classification tasks, dense segmentation (e.g., Meet background blur) and regression problems (MediaPipe Hands), which provides tangible benefits to users. For example, in the case of Google Meet, sparsification lowered the inference time of the model by 30%, which provided access to higher quality models for more users.

Model size comparisons for the dense and sparse models in Mb. The models have been stored in 16- and 32-bit floating-point formats.

The approach to sparsity described here works best with architectures based on inverted residual blocks, such as MobileNetV2, MobileNetV3 and EfficientNetLite. The degree of sparsity in a network influences both inference speed and quality. Starting from a dense network of a fixed capacity, we found modest performance gains even at 30% sparsity. With increased sparsity, the quality of the model remains relatively close to the dense baseline until reaching 70% sparsity, beyond which there is a more pronounced drop in accuracy. However, one can compensate for the reduced accuracy at 70% sparsity by increasing the size of the base network by 20%, which results in faster inference times without degrading the quality of the model. No further changes are required to run the sparsified models, because XNNPACK can recognize and automatically enable sparse inference.

Ablation studies of different sparsity levels with respect to inference time (the smaller the better) and the quality measured by the Intersection over Union (IoU) for predicted segmentation mask.

Sparsity as Automatic Alternative to Distillation
Background blur in Google Meet uses a segmentation model based on a modified MobileNetV3 backbone with attention blocks. We were able to speed up the model by 30% by applying a 70% sparsification, while preserving the quality of the foreground mask. We examined the predictions of the sparse and dense models on images from 17 geographic subregions, finding no significant difference, and released the details in the associated model card.

Similarly, MediaPipe Hands predicts hand landmarks in real-time on mobile and the web using a model based on the EfficientNetLite backbone. This backbone model was manually distilled from the large dense model, which is a computationally expensive, iterative process. Using the sparse version of the dense model instead of distilled one, we were able to maintain the same inference speed but without the labor intensive process of distilling from a dense model. Compared with the dense model the sparse model improved the inference by a factor of two, achieving the identical landmark quality as the distilled model. In a sense, sparsification can be thought of as an automatic approach to unstructured model distillation, which can improve model performance without extensive manual effort. We evaluated the sparse model on the geodiverse dataset and made the model card publicly available.

Comparison of execution time for the dense (left), distilled (middle) and sparse (right) models of the same quality. Processing time of the dense model is 2x larger than sparse or distilled models. The distilled model is taken from the official MediPipe solution. The dense and sparse web demos are publicly available.

Future work
We find sparsification to be a simple yet powerful technique for improving CPU inference of neural networks. Sparse inference allows engineers to run larger models without incurring a significant performance or size overhead and offers a promising new direction for research. We are continuing to extend XNNPACK with wider support for operations in CHW layout and are exploring how it might be combined with other optimization techniques like quantization. We are excited to see what you might build with this technology!

Acknowledgments
Special thanks to all who worked on this project: Karthik Raveendran, Erich Elsen, Tingbo Hou‎, Trevor Gale, Siargey Pisarchyk, Yury Kartynnik, Yunlu Li, Utku Evci, Matsvei Zhdanovich, Sebastian Jansson, Stéphane Hulaud, Michael Hays, Juhyun Lee, Fan Zhang, Chuo-Ling Chang, Gregory Karpiak, Tyler Mullen, Jiuqiang Tang, Ming Guang Yong, Igor Kibalchich, and Matthias Grundmann.

Categories
Offsites

How to Start a Startup – Stanford 정리

대기업에서 스타트업으로 다시 돌아가면서, 예전에 인상깊게 본 How to Start a Startup 강의를 정리해보고자 합니다. 이 강의는 총 20개로 구성되어 있고, 2014년에 스탠포드에서 진행이 되었습니다. Y Combinator 라는 유명한 액셀러레이터의 대표인 샘 알트만이 진행하였고, 다양한 스타트업 (대부분 혹은.. 모두 Y Combinator가 투자한)에서 연사들이 각 주제별로 강의를 합니다.

모든 강의를 하나하나 요약하고 정리하는 것이 아닌, ‘제품’, ‘사용자’ 와 같이 대분류에 맞춰서 묶을 수 있는 내용들을 모으고 내용 또한 블릿 포인트(bullet point)로 정리합니다. 그리고 몇가지 용어들에 대해서는 조금 더 살펴보고 따로 정리하는 것을 목표로 (e.g. CLV, Cohort Analysis 등) 하였습니다.

General

  • Great Idea → Great Product → Great Company
  • 왜 창업을 하고 싶은가.
    • 최고의 이유
      • 해당 아이디어는 내가 아니면 안 된다
      • 세상이 나를 필요로 한다
  • 스타트업을 시작하는 것은 애를 키운다는 것과 비슷하다고 할 수 있다.

image.png

출처: How to Start a Startup, Lecture Note 1

Product : 제품

Idea

좋은 스타트업 아이디어를 떠올리는 방법은 한걸음 뒤로 물러서서 보는 것.

  • 의식적이 아닌, 무의식적으로 떠올릴 수 있어야 한다.
    1. 중요한 것들을 열심히 배우라
      1. 기술을 배워라
      2. 최신 기술들을 지켜보기
    2. 흥미로운 것들을 해봐라
      1. 기업가 정신은 하나의 도메인 전문가가 된다는 것
    3. (존경하는) 친구들과 같이 해봐라

사용자 & 고객

  1. 해결해야하는 문제에 대해 정확히 파악해야 한다.
    • ‘문제’ 는 한 문장으로 표현할 수 있어야 한다.
    • 어떤 산업군에 속하는가, 산업규모는 어떤가?
      해당 산업에 대해서 구체적으로 살펴볼 수 있어야 한다. (2~3 개월)
    • 제품을 만들 때 모든 관점에서 고객의 입장이 되어보야아 한다.
      • 해당 산업의 전문가가 되어야 한다.
  2. 목표 고객군을 설정해야 한다.
  3. 코드 작성 전에 사용자 경험을 고려한 스토리보드 작성

image.png

출처: How to Start a Startup, Lecture Note 7
  • 소수의 사용자가 좋아하는 것에 집중해야 한다.
    • 자연스럽게 유저가 늘어날 것
    • 제품 런칭 전에 해야할 일은? 딱 10명에서 100명을 위한 기능을 만들어야 한다.
  • 창업자가 직접 고객들을 만나야 한다
  • 첫 고객에게 집중하라.
  • 새로운 고객은 데이트를 하는 것과 같고,
    • 첫 인상이 중요하다. 그 느낌을 계속 가지고 이야기할 것이기 때문
    • 첫 번째 상호작용을 할 때, 사람들은 인내심이 훨씬 적다.
    • 그렇기 때문에 첫 인상을 잘 만드는 것은 제품에 아주 중요하다.
      e.g.) Vimeo, Wufoo, Heroku, Chocolat, hurl, MailChimp 케이스, stripe
  • 기존 고객은 결혼한 배우자와 같다.
    • 성공적으로 잘 사는 관계는 잘 싸운다. (가장 큰 요소)
    • Money – Cost / Billing
    • Kids – Users’ Clients
    • Sex – Performance
    • Time – Roadmap
    • Others – Others

image.png

출처: How to Start a Startup, Lecture Note 1
  • SSD: Support Driven Development
    • 고품질의 소프트웨어를 개발하는 방법
    • 모든 사람이 고객 지원을 하도록 하는 것 → 개발자와 디자이너 모두에게 피드백이 골고루 돌아갈 수 있다.
    • 제품을 만든 사람이 직접하기 때문에 최고의 고객지원을 할 수 있다.
    • 대화거부는 최악의 행동이며 스타트업에서 많이 하는 실수 중 하나이다.
  • Jared Spool, 팀원들이 고객에게 직접 노출되는 시간의 양과 디자인이 좋아지는 정도가 정확히 비례한다. (고객과 실시간으로 이야기를 해야 한다.)
  • 최소 6주에 한번은 그런 시간이 있어야 하고, 그 시간은 2시간 이상이어야 한다.
  • 감사편지 보내기 – 팀원들이 겸손하려고 했기 때문에 가능한 일 (팀의 조직력을 높이고 팀이 신경쓰는 일을 하게하는 일종의 의식)

  • 제일 돈이 되는 사용자들에게 집중하라 → 그 고객들만 잘 관리하면 나머지는 따라온다.
  • 고객을 얻는 방법?
    1. 시작은 지인, 온라인 커뮤니티, 로컬 커뮤니티, 메일, 언론 등..
    2. 진짜 고객을 만날 수 있는 곳으로 가야 한다
  • 고객들에게 피드백을 받아라.
    1. 피드백이 오는 것보다는 직접 전화를 걸어라, 찾아가라
    2. 설문: 정말 좋거나, 싫은 경우에만 피드백이 올 것이다.
    3. 고객의 재방문율을 측정하라.
    4. 고객에게 돈을 내게 할 수 있다면, 정말 훌륭한 피드백을 받을 수 있을 것이다.
  • 더 많은 유저를 위해서는?
    • 한가지 초점만 정해놓고, 일주일 내내 집중해야 한다.
    • 한 채널씩 이해해야 한다.
    • 가장 중요한 부분은 창의력
    • 아무도 안 하는 한가지를 찾아서 극단적으로 진행해야 한다.
  • 이미 유사한 제품을 사용하고 있는 고객을 끌어오는 방법
    • 사용하고 있는 서비스를 전환하는 것은 비용이 든다. 확실한 장점이나 차별성이 있어야 한다. 50가지 자잘한 기능보다는 1, 2 가지의 차별점이 좋다.

Metrics

  • Metrics: Focus on growth
    • Total Registrations
    • Active users
    • Activity Levels
    • Cohort Retention
    • Revenue
    • Net Promoter Score
      • 이 제품이나 서비스를 동료나 친구들에게 추천할 의향이 얼마나 되시나요?
  • Growth : 전환율과 이탈율의 상호작용
    • 전환율을 1% 높이는 것과 이탈율을 1% 줄이는 것이 성장에 미치는 영향은 똑같다. 보통은 후자가 더 쉽고 비용도 적게 들어간다.

그 외

  • 아이디어, 고객, 산업군에 대해서 알았다면 이제 제품을 만들어야 한다.
    1. MVP: Minimum Viable Product, 최소생존제품
    2. 무엇을 하는 제품인지 명확히 정리해야 한다.
      (우리 제품은 이런거야 하고 명확하게 말할 수 있어야 한다.)
  • 사람들이 좋아하는 제품이란, 해당 제품에 대해서 열광적인 고객층이 있고, 그 고객층이 우리 회사의 제품 뿐아니라 회사 자체도 성공하길 바라는 것.
  • 시장을 장악하는 3가지 방법
    • 최고의 가격 : 유통
    • 최고의 제품 : R&D
    • 최고의 종합 솔루션 : 고객 친화
      유일하게 누구나 어떤 단계의 기업에서건 쓸 수 있는 방법이다.

QnA 모음

Q. 다양한 고객, 모두가 사랑하는 제품은 어떻게 만들 수 있을까요?

⇒ 초기에는 가장 열성적인 고객에게 집중, 그 고객들에게 맞추다보면 언젠가 일반적인 가치를 발견할 수 있을 것, 기본이 되는 기능들을 만들고 난 후에 그것을 돋보이게 하라

Q. 제품을 만드는 것과 그 외의 일 간의 균형을 맞추는 방법

⇒ 제품에 집중하면서 한쪽에서는 고객과 이야기를 해야하고, 이런 분담은 어느정도 필요하다. 중요한 것은 순환적인 피드백 고리이다.

Q. 제품에 대해 팀 내에서 의견이 서로 다른 경우 의사결정을 진행하는 방법

⇒ 고객 지원을 통해서 해결 (문의가 많은 기능에 대한 기능 순으로 해결)
무조건 고객들이 하라는대로 하는 것이 아닌, 왜 고객들이 그런 요청을 하는지 그 원천적 이유를 찾아서 해결하는 것. 각자의 버전을 만들고 대응해보는 것도 좋다.

Q. Pinterest의 비전이 초창기와 달라졌는가?
⇒ 사람들의 수집품에서 예상하지 못 했던 놀라운 것들을 찾아낼 수 있다는 사실을 나중에 알게 되었다. (사람들의 제품사용 양상이 다른 방향을 보여준다.)
초기에는 누군가 제품을 사용해준 다는 것에 흥분 했다. 재밌는 점은 회사가 성장할수록 포부도 같이 커진다는 점이다. 그래서 항상 Gap이 있다. 우리가 있는 곳과 있어야 할 곳. 객관적으로 우리는 많이 달려왔지만.. 이 Gap은 계속해서 벌어지고 있다.


Execution : 실행

  • 실행에 대한 2가지 질문
    1. 무엇을 할지 정할 수 있는가?
    2. 그 일을 마무리 할 수 있는가?
      • Focus (선택과 집중)
        • 가장 중요한 2~3가지 일만 골라서 하는 것
        • 커뮤니케이션이 잘 진행 되어야 한다.
          • 매주 방향을 공유하고, 디테일한 목표 수치를 향해 달릴 수 있도록.
        • 정확한 성과지표를 파악하고, 이 지표가 지속적으로 성장할 수 있도록.
      • Intensity (빡세게 일하기)
        • 스타트업은 워라밸이 가능한 곳이 아니다.
        • 끊임없는 운영 리듬 & 퀄리티에 대한 집착
        • 모든 방면에서 빠르게
  • 아무리 큰 일이라도 작은 일으로 나눠서 진행할 수 있다.
    • 일을 작은 프로젝트로 나눠서 진행하라.
  • 사람에 대해서는 직관에 의존해도 된다.
  • 스타트업을 성공시키기 위한 지식은 스타트업을 위한 지식이 아니다.
    • 고객에 대한 전문가가 되어야 한다.
  • 스타트업에서는 요령피우는 것이 먹히지 않는다.
  • 스타트업은 모두 매우 빡세다.
  • 스타트업이 성공한다는 것에 대해서는 예측이 불가능하다.
    • 운동선수와 수학자처럼 예측이 불가능하다.
    • 창업가가 얼마나 강인하고 야망이 있는가.
  • 피보팅
    1. 회사가 성장하지 않을 때
    2. 제품을 사용자가 사용하지 않을 때
    3. 논리적으로 비즈니스가 말이 안 될때
  • “좋은 계획을 오늘 죽어라 실천하는 것이, 내일에 대한 완벽한 계획을 가진 것보다 낫다.”
  • “물건을 부수는 것은 상관 없으니 빨리 움직여라!”

DOORDASH (배달앱) 케이스

  • 아무것도 준비되어 있지 않는 상황에서, 바로 랜딩페이지로 서비스 런칭
    • 초기에는 아이디어를 시험해보고, 사업을 시작하고, 사람들이 원하는 것인지 확인하는게 중요
  • “확장성이 없는 일을 일부로 해라”
    • 이 일은 본인의 사업에 있어 전문가가 되게 해준다. 직접 개개인 별로 피드백 메일도 전달.. 등등
  • 초기에는 일단 시작을 하고, 제품이 시장에 맞는지 확인해야 한다.
  • 정리
    1. 가설 검증
    2. 런칭을 빠르게
    3. 확장성이 없는 일을 한다
      수요가 확인 되면 확장을 할 수 있기 때문이다

Teespring (이커머스 플랫폼) 케이스

스타트업이 가지고 있는 가장 원초적인 강점: 확장성 없는 일을 할 수 있는 것

  • 첫 고객을 모으고
    고객을 모으는 데는 왕도가 없다. 가장 힘든 일일 것이다. 모맨텀을 만들기 까지가 가장 힘들다. 여기서 시간 대비 효율을 따지는 것은 무의미하다. 제품을 무료로 주지 말아라. (제품의 가치를 해치는 일이다., 그래서 지속가능하지 않은 일이 된다.)
  • 고객을 챔피언으로 만드는 것
    입소문을 낼 수 있도록, 기억에 남을 만한 경험을 선사하는 것 (고객과 대화를 하는 방법),
    실제 사용자에게 듣는 것보다 제품을 좋게 만드는 방법은 없다.
    소셜미디어와 미디어를 확인하라.
    중요한 것은 문제를 제대로 고쳐나가는 거이다. (가장 불만이 많던 고객이 가장 영향력이 있는 챔피언이 되어주는 경우가 있다.)
  • 시장에 맞는 제품을 찾는 것
    처음 런칭한 제품은 성장할 수 있는 수준의 제품이 아니어도 된다. 속도가 중요.
    경헙으로 얻은 인사이트: 오직 다음 규모의 고객에 대해서만 생각하라
    확장성이 없는 일을 최대한 오랜기간 해야 한다.

Growth : 성장

  • 성장동력을 유지하는 것 (스타트업 운영의 핵심)
    • 항상 이기는 팀을 만들어 내는 것
    • 배포에 대한 주기를 정립 (새로운 Features)
    • 지표를 공유하는 것
  • 매출은 모든 것은 고친다.
  • 페이스북 케이스 ‘성장모임’
    • 회사의 성장 동력으로 작용

image.png

출처: How to Start a Startup, Lecture Note 4
  • 지속가능한 성장이 중요하다.
    1. Sticky :기존 사용자가 계속 방문하게 하는 것
      • 좋은 경험이 중요하다.
      • CLV (고객주기), Cohort 분석으로 알 수 있다.
      • 오랜기간이 지나도 계속 사용하는 고객 → Core 고객들
    2. Viral : 고객이 직접 주변사람에게 권하는 것
      • 좋은 경험이 중요하다. 그것과 함께 입소문을 낼 수 있는 장치가 필요하다.
        1. 소문을 낼 수 있는 것을 알려준다.
        2. 제도적인 장치 → 친구를 초대하면 양쪽에 크래딧 제공
    3. Paid : 매출을 통해서 돈을 벌고 계속 성장
      • CLV > CAC (고객 획득비용) , 돈을 쓰고 더 많은 돈을 얻을 수 있어야 한다.
      • 들인 돈을 회수할 수 있는 기간이 중요하다. (3개월 정도)
  • 사업할 때 전체 시장크기를 볼 수 있어야 한다.
  • 성장에서 가장 중요한 것은 무엇인가?
    ⇒ 좋은 제품 → 고객 유지 (성장의 핵심)
  • X축과 평행하게 가면, 시장 크기에 맞는 제품을 잘 만들어낸 것이다.
  • Retention이 0 으로 가면 제품이 시장에 맞는지부터 확인을 해야 한다.
  • 좋은 Retention 은 몇 프로인가?
    ⇒ 사업 분야마다 성공을 위한 재방문 수렴치는 다르다.
  • 스타트업에는 성장팀이라는 것이 있어서는 안 된다. 그 팀 자체가 성장팀을 포함해야 한다.
  • 일하는 사람들이 지금 회사에 중요한 것을 알기는 어렵다.
  • “마법의 순간”
    • 사용자들이 ‘아하’를 경험하는 순간
    • 예시)
      • 페이스북 → 가입 후 친구의 사진을 보는 순간 (소셜미디어임을 확인하는 순간)
      • 왓츠앱 → 친구, 이베이 → 물건 리스트
    • 제품의 마법의 순간이 언제인지 생각해보고, 사용자가 그것을 최대한 빨리 느낄 수 있도록 해라
  • 성장은 설계하는 것이 아니라 지켜보는 것이다?
  • 우리가 초점을 맞춰야하는 고객들은 경계선에 있는 사람들이다. 성장할 때는 이미 잘 사용하고 있는 고객에 신경을 쓸 필요가 없다. 성장에 있어서 가장 중요한 점이다.
  • 잘 만들고, 고객을 데려올 수 있어야 한다. (마케팅)
  • 유입경로
    1. Virality : 전파성을 3가지로 나눠 보는 것.
      • Payload : 한번의 바이럴 마케팅으로 만들 수 있는 도달의 수
      • 전환율(CR) : 전환이 얼마나 일어나는가
      • 빈도 : 얼마나 자주 도달 할 수 있는가
      • Import → Send → How many People → Click → Sign up → Import …
        • K factor로 전파성을 판단
    2. SEO : 검색엔진
      • 키워드 : 어떤 키워드로 경쟁을 할 것인가 정해야 한다.
      • PageRank

페이스북 케이스

페이스북 성장팀에서 했던 일

  1. 가입하고 2주 이내 친구 10명을 찾게하는 것
  2. 국제시장 진출 → 언제든지 확장이 가능한 제품 (느리더라도 제대로)
    • 우선 순위의 언어에 먼저 집중

QnA 모음

Q. 이메일 마케팅

⇒ 이메일은 25세 이하는 거의 사용하지 않는다. 메일, 문자, 앱 푸쉬는 동작 방식 전부 비슷, 스팸에 들어가면 안되므로, 우등생? 처럼 메시지를 전달하는 것이 중요하다 중요한 것은 사람들에게 전달이 되어야 하는 것이다.
이 알림은 어떤 경로를 통해 보낼 것인가가 중요하고, 그 다음은 참여를 독려하는 내용에 신경써라.


Business : 비즈니스

image.png

출처: How to Start a Startup, Lecture Note 5
  • 항상 독점을 목표로 하고 경쟁은 피해야 한다.
  • 사업을 가치있게 만드는 것은 무엇인가?
    ⇒ X 만큼 가치를 창출하고, Y 만큼 그 안에서 이득을 얻는다. (X, Y는 독립 변수)
  • 세상에는 ‘완전경쟁시장’과 ‘독접사업’ 두 가지 뿐이다.
  • 보통 독점기업은 규제를 피하기 위해서 거짓말을 하고 있고, 완전경쟁시장에서는 1등을 하고 있다고 말하기 위해 독점인 것처럼 말을 한다.
  • 교집합 시장이 진짜인지, 말이 되는지, 가치가 있는지 항상 따져보아야 한다.
  • 어떻게 독점시점을 만들어 낼 것인가?
    • 작은 시장을 노려라. 그 후 그 시장을 구심점으로 확장해라.
      • 아주 작은 시장들은 저평가가 되어 있다.
  • 독점 기업의 특성
    • 자신만의 기술을 가지고 있다.
      • 불행한 회사는 닮았으며, 행복한 회사는 각각 다르다.
      • 핵심적인 부분에 대해서 혁신적인 개선점을 가지고 있어야 한다.
    • 소프트웨어는 한계비용이 0 이다!
      • 고정비용은 크지만 한계비용이 작아서 규모의 경제를 갖출 수 있는 경우
    • 네트워크 효과는 일반적으로 시간이 지나면서 확장되는 것.
  • 그 분야의 마지막 회사가 되어라
  • 가치평가에서 가장 중요한 부분은 지속가능성이다.
  • 왜 이 사업이 오랜기간 지속될 것인가를 고민해보는 일..!
  • 경쟁은 그 분야에 대해서 당신을 발전하게 만든다. 하지만 정말 중요한 것이 무엇인가에 대한 큰 질문을 하지 못 하면 더 큰 것을 잃는다.

QnA 모음

Q. 아이디어가 독점적인 사업이 될지 아닐지 구분하는 방법

⇒ 실제 시장에 집중해야 한다.

위대한 기업은 다른 기업 들과 다르게 한 단계 더 뛰어넙는 진보가 있었다고 본다.
다른 사람 혹은 심지어 고객의 의견까지도 받지 않고 가는 경우도 있다.


Investment : 투자 유치

  1. 사업을 한 문장으로 설명할 수 있어야 한다.
  2. 창업가는 결단력이 있어야 한다. 무슨 일을 하건 일이 진행되도록 해라.
  3. 최대한 돈 없이 가라. (Bootstrap)
    • 투자를 안 받고 가는 것도 충분히 가능하다.
  4. “성공의 비결은 너무 잘해서 다른 사람들이 무시할 수 없게 하는 것”
  5. 투자보다 실제로 돈을 벌고 있는 것이 더 어렵다.
  • 돈과 리스크와의 관계
  • 리스크의 양파이론: 긴 목록의 리스크 리스트가 있을 것이고, 투자의 과정은 투자를 통해 이 리스크를 한 단계씩 제거해 나가는 것이다. 마일스톤을 달성해 나갈 때 마다 리스크를 제거하고, 사업을 진행시키는 것.
  • 투자자들에게 NDA (비밀 서약서) 를 써달라고 하지 마라.
  • 기록을 하라.
  • 좋은 회사로 부터 시드펀딩 → 시리즈 A.. 이런 가능성은 계속 올라가게 된다.
    • ⇒ 좋은 투자자는 누구인가?
  • 투자 시 협상은 어떻게 하는 것이 좋은가?
  • 시드펀딩에서 어디까지 지분을 주는 것이 좋은가?
    • ⇒ 20~30%, 30 이상은 주주 쪽으로 문제가 될 여지가 있고,.. 지분이 떨어지는 것에 따라서 동기가 떨어지게 되는데.. 틀이 중요하다. 시드에서는 10~15%, … 외부투자자들과의 관계가 복잡해서 투자를 하지 않는 경우도 많다.
  • 최고의 투자는?
    • ⇒ Google, AirBnB → 3명의 창업자 모두가 비슷하게 훌륭하기 때문
  • 모든 회사는 CEO가 있습니다. 회사를 시작하면 여러분만큼 잘하거나 더 나은 공동창업자를 찾아야 한다. 그것만 해내도 성공할 확률이 천문학적으로 늘어난다.
  • 마크 주커버그는 혼자서 이끄는 예외적인 케이스이다.

투자자와 이야기하는 법

image.png

출처: How to Start a Startup, Lecture Note 19 – 2
  1. 30초 홍보 : 여러분 회사에 대해 처음 소개하는 것
    • 3문장이면 충분하다.
    • 첫 문장 – 회사가 하는 일을 소개 (직관적으로 소개, 엄마 테스트 추천)
    • 다음 문장 – 시장의 크기 (Botton up analysis)
    • 마지막 문장 – 성장률 (빠르게 움직이는 회사임을 보여주라)
  2. 2분 홍보 : 여러분 회사에 관심있는 사람들을 대상으로 함 (10분 30분 혹은 1시간을 준비하는데, 2분이면 충분하다)
    • Unique Insight – “아하” 순간, 이 것을 첫 두문장으로 말할 수 있어야 한다.
    • How you make money – 사업 모델, 어떻게 돈을 버는지 혹은 벌 것인지 명확하게 이야기하라
    • Team – 1. 팀이 이룬 업적을 자랑 (학위나 상장 X), 2. 창업자의 수 + 기간 + 풀타임
    • The Big Ask ($$$) – 자금 요청, 진지한 태도로 임해야 한다.
  3. When to Fundraise
    • 투자자들은 성장률 기반으로 투자하고 싶어한다.
    • 여러분이 강하면서 약한 단계 – 자금 요청을 할 시기
    • 투자자가 갑이 되는 상황으로 가면 안 된다 – “여러분의 자금 없이는 저희는 아무것도 못합니다” 이렇게 하면 안 된다.
  4. 투자자와 미팅을 잡는 법
    • 이상적: 다른 경영자가 여러분 대신에 회사를 소개해주는 것 (신뢰가는 소개)
    • 여러가지 일을 동시에 생각하라
      • 투자자들과의 미팅 셋팅을 한 주내에 다 진행해야 한다
    • 자금 마련 전담 맴버가 있어야 한다
    • 미팅이 끝난 후
      • 사후 관리
      • 투자자들을 면밀히 조사하라
      • 끝낼 때를 제대로 알라
      • 회사를 세우라! (자금 마련이 목표가 아니다)

QnA 모음

Q. 어떤 팀, 회사에 투자를 하나요?

⇒ 처음 만나고 1분 정도 이야기하는 동안 정리가 된다. 이 사람이 리더인지, 자신의 제품에 대해서 집중하고 있는지 (질문: 사업을 하게 된 계기), 그 다음으로 보는 것이 커뮤니케이션 능력 → 리더쉽과 훌륭한 커뮤니케이션 능력 이 2가지를 갖추고 있어야 한다.

⇒ 일반적인 2가지.

  1. VC 투자 활동은 극히 예외적인 경우만 다루는 게임이다.
    4000 개 → 200개만 투자 → 그중 15%가 97%의 수입을 가져다 줌

  2. 강점이 큰 회사에 투자할 것인가, 약점이 없는 회사에 투자할 것인가
    체크 리스트 만으로는 그 팀이 가지고 있는 강점을 제대로 파악할 수 없다.
    결점이 있는 회사를 제외 시키면 15% 안에 회사에 드는 회사를 얻기 어렵다.

Q. 초기 자본이 많이 필요한 스타트업에 대해서는 어떻게 하는가?

⇒ 양파 리스크이론을 다시 언급하면, 리스크를 없앨 수 있는 더 구체적인 계획이 필요할 것이다.

Q. 안 좋은 투자자는 무엇인가?

⇒ 네트워크가 부족하거나, 도움을 받을 수 있는 것이 없는 경우, 투자자를 고르는 것은 결혼 상대를 고르는 것이나 마찬가지이다. 약 15~20년 동안 서로를 의지하고 기대면서 같이 나아가는 것이기 때문.

한번 창업가는 영원한 창업가이다.

투자자를 만났을 때, 이 사람이 존경할 만 한가, 배울 점이 많은 가를 고려해보아라.

피투자사와의 관계는 신뢰를 기반으로 해야 한다.

VC의 가장 큰 제약사항은 결국 큰 기회비용이다. 한 분야에서의 최고를 투자하려고 한다.

Q. 제품이 없는 팀이 투자를 받을 방법은?

⇒ 팀이 중요하다. 기본적으로도 팀을 보고 투자하기 때문.

Q. 투자철학을 하나의 문장으로 만드는 것이 필요한가?

⇒ 한 문장으로 정리할 수 있을 정도로 명확한 투자철학을 가지고 있어야 한다. (엘레베이터 피치)

Q. 적합한 시장을 찾는 것 vs 시장을 만들어가는 것

⇒ 굉장히 어려운 문제이다. 투자 철학을 검증하는데 있어, 이 방향이 과연 시장의 존재유무를 확인하는 데에 도움이 되는가이다. 여러분은 현존하지 않는 시장이 여러분만이 알고 있는 근거에 따른 역발상 때문에 창조 가능하다는 주장을 명료하게 펼칠 수 있어야 한다.


Culture : 조직, 기업문화

  • 창립자들이 하는 일이 회사의 문화다.
  • 믿음은 생각이 되고, 생각은 말이 되고, 말은 행동이 되고, 행동은 습관이 되고, 습관은 가치가 되고, 가치는 운명이 된다. – 간디
  • 이것들이 왜 중요한가?
    ⇒ First Principles (의사 결정의 첫 번째 기준), Alignment, Stability (안정감), Trust, Exclusion (하지 말아야할 것은 아는 것이 더 중요하다), Retention
  • Zappos의, 첫 번째 핵심가치는 서비스에 “와우” 요소를 넣는 것, 또 다른 핵심가치는 겸손
  • 성과가 좋은 팀의 특정
    • Patrick Lencioni 의 피라미드 – 1. 신뢰, 2. Conflict, 3. Commitment, 4. Accountability, 4. Results

image.png

출처: How to Start a Startup, Lecture Note 10
  • 인터뷰 과정에서 문화를 고려해야 한다.
    • 좋은 문화를 만드는 데 성패가 갈리는 부분은 습관적으로 할 수 있는가 없는가 이다.
  • 문화가 일을 해내는 방식이라고 한다면 2가지 요소가 있다.
    1. 행동양식 (변하는 것), 2. 변하지 않는 것이 필요하다. (핵심가치)
  • 여러분만의 핵심가지치 3~4개는 있어야 한다.
  • 새로운 사람을 한 명도 고용하기 전에 핵심가치를 정했던 회사! → 첫 번째 개발자를 뽑는데, 걸린 시간은 5~6개월 → 이 사람이 회사의 DNA를 결정하기 때문이다. 다양성은 존중하나, 가치관은 비슷한 사람들이어야 한다.
  • 회사의 사명
    • ⇒ ‘소속감’을 주고 공통체를 만들어가는 일
  • AirBnB의 핵심가치
    1. 사명을 위해 분투하는 것
      • 여기 하는 일에 믿음이 있는가?
      • 소명이 있는 사람을 찾는다
    2. 연쇄 창업가가 되어야 한다는 것 (창조적)

이것들은 회사의 가치와 원칙으로 변하게 된다.

  • 문화의 문제점
    1. 문화에 대한 글은 찾기 어렵다.
    2. 정량화하기 어렵다.
    3. 장기적으로만 효과가 있다.
  • 문화는 마치 미래에 투자하는 것과 같다. 결국 장기간 버틸 회사를 만드는데 필요한 것
  1. 지향점을 확실하게 해야 한다.
    • 이 가치들을 기준으로 고용/해고를 해야 한다.
    • 여기에 엔지니어가 들어가서 뽑는 것은 좋지 않다. 실력 위주로 보기 때문
  2. 전반적인 사내문화
  3. 초기 인력 구성
  4. 그 이상으로 규모가 커져감에 따라서 발생하는 변화와 적응

QnA 모음

Q. 문화란 무엇일까? → 기업의 문화는 무엇이 되어야 하는가?

⇒ Set of Values?

Q. 기업 문화란 무엇일까?

⇒ 핵심가치, 행동 혹은 행위, 사명감 (목표)

Q. AirBnB 시나이로

⇒ 너무 잘나서 불편하게 할 정도의 팀을 만드는 것이 중요하다. (훌륭한 공동창업자)
제품을 만들고 나면, 회사를 만들어야 한다. → 우리는 오래살 수 있는 회사를 만들고 싶었다. 길게 가는 회사들의 공통점 → 분명한 임무를 가지고 있고, 명확한 가치를 가치며 협업할 수 있다는 것.

Q. 어떻게 집주인들이 AirBnB의 문화를 따르게 할 수 있는가?

⇒ 집주인들은 문화와 맞지 많아도 된다고 생각했지만, 아니였다. (문제가 생기는 등..), 그 이후로는 ‘슈퍼집주인’ 프로그램을 통해서 문화를 따르는 집주인들을 더 대우해준다.

Q. 회사를 만들면서 가장 중요하게 생각했던 요소는?

⇒ 누구를 채용하는가? 채용된 사람들이 무엇을 중시하는지, 우리가 매일 무슨 일을 하는가 또 왜 하는가?, 우리가 소통하기로 선택한 것들, 마지막으로 찬양할 것은 무엇인가?

⇒ 내부 투명성을 더 강조, 모든 직원들이 회사가 하는 바를 지지하고 믿을 수 있도록 하기 위함 (정보를 원활히 접근할 수 있고 상태를 알 수 있다면 도움이 될 것)

⇒ 사내 문화 정립은 다양한 문제를 풀 수 있음, 사람들이 늘어나면서 직접적으로 영향을 끼치는 영향도는 줄어들 수 밖에 없음.
초기에 사람을 10명을 데려오는 것은, 이 사람들이 데려올 90명의 사람들에 대한 영향력까지 고려를 해야하기 때문에 굉장히 조심해야 하는 일이다.

Q. 초기 채용을 하고 올바른 문화를 퍼트리기 위해 한 행동은?

⇒ 언젠가 이루고 싶은 목표를 직원들에게 계속해서 상기시킴, 왜냐하면 누군가에게 문제가 주어지면, 그 사람은 직면한 문제가 세상의 전부라고 생각하게 되기 쉽기 떄문. 많은 시간을 들여서 채용을 한 다음에 입사 후 30일간의 경험을 개선하기 위해 노력한다. (예를 들어, 이름을 아는 동료직원은 있는지? 자신의 매니저가 누군지? 팀원들과 만나고 있는지? 회사에 전반적인 구조는 아는지? 최우선 목표들은 아는지? 이런 프로그램들을 계속해서 발전 시키고 평가함)

⇒ 1. 직원들이 바쁘게 진짜 일을 하는 것. 이렇게 해야만이 실제 문제들을 찾아내고, 얼마나 진척이 됐는지를 알 수 있다. 강하게 적응시키려고 한다. 2. 최대한 빨리 피드백을 주려고 한다. 특히 사내 문화 적응 관련 피드백은 더 빠르게 하려고 한다. (Stripe의 문화 중 하나는 글을 통해서 소통을 하려고 한다.)

Q. Stripe는 어떻게 투명성을 확장시켰는지 궁금하다.

⇒ 스타트업은 정치적인 문제들에 휩싸이지 않은 조직이라고 정의를 했다. 대기업에서는 여러가지 일들이 얽혀있으면서.. 제품에는 최선의 방향이 회사차원에서는 문제가 될 때가 있을 것이다. 하지만 모든 사람들이 한 방향으로 나아가는 스타트업에서는 모든 정보를 공개할 수 있다. Stripe는 초기에 발송되는 모든 이메일에 전직원을 참조시켰다. 일어나는 일들을 미리 알고 있다면, 미팅을 따로 가질 필요가 없다고 생각했다. 하지만 확장에 문제가 있었던 것은 사실이다.

⇒ 첫째는 툴을 바꾼 것이고, 둘째는 확장에 맞춰서 문화를 발전시킨 것이다.
툴은 모든 이메일 공유 → 이제는 매주 취합한 형태로 정보를 공유 (덱을 만들거나..)
문화 이야기는 엄청난 양의 정부가 내부 공개가 되어있고, 이에 따른 사내 규범들이 규정되어 있다.


Team : 동료 & 채용

채용

  • 작은 팀으로 얼마나 많은 일을 하는지에 대해 스스로 자랑스러워 해야 한다. 한계에 부딪칠 때까지 초기에는 채용을 하지 않는 방향이 좋다.
  • AirBnB 케이스
    • 채용 눈높이를 엄청나게 높이고, 천천히 채용하면서 모두가 회사의 일에 대한 사명감을 가지게 함
  • 최고의 사람들을 얻는 법
    • 똑똑한 사람들은 로켓에 올라타야 한다는 것을 안다. (훌륭햔 제품의 필요성)
    • 채용에 사용하는 시간: 0% or 25% (하지 않거나, 최대로 쓰거나)
    • 스타트업에서는 중간 실력이면 안 된다. 회사를 망하게 할 수 있다. (이 사람 한명한테 우리 회사의 미래를 맡길 수 있을까?)
    • 초기에는 주변 사람들을 영입하는 방식
    • 채용시 보는 3가지
      1. 똑똑한가?
      2. 일을 해내는가?
      3. 더 많은 시간을 같이 보내고 싶은가?
      4. (추천) 인터뷰 보다는 프로젝트를 같이 해보라
        1. (인터뷰를 할시) 무엇을 해봤는지 프로젝트에 대해서 집중적으로 물어보라
        2. 레퍼런스 체크를 철저하게 진행하라.
    • 그 외 중요한 점들
      • 커뮤니케이션 스킬
      • 어느정도 위함한 것을 좋아하는 사람
      • 스타트업에 대한 집착이 있는 사람
      • 마크 주커버그의 기준
        • 함께 시간을 보내기 즐거운 사람
        • 역할이 뒤집혀도 보고하기 편한사람
    • 투자자에게는 협상시 최대를 얻을 수 있도록 하고, 직원에게는 후하게 하라 (지분 등)
  • 직원들이 행복하고 존중받는 느낌이 들도록 해야한다.
    • 지분 분배의 중요성
    • 회사에 일어나는 좋은 일의 공은 모두 팀원들에게 돌리고, 나쁜 일에 대한 모든 책임은 책임을 져야 한다.
    • 동기 부여의 핵심
      • 자율성 보장
      • 성장한다는 느낌
      • 일을 하는 명료한 목적
  • 해고를 빠르게 해야 한다.

QnA 모음

Q. 초기맴버를 사내문화 관점으로 접근할때 중요하게 본 요소는?

⇒ 같이 일하고 싶으면서 또 재능있는 사람들,
사내문화는 건설한다고 생각하지만.. 내가 보기에는 정원을 가꾸는 일이다.
초기에는 창업자와 비슷한 사람들을 찾으려고 했다. (아주 별난 사람들이기도 함)
우리는 많은 분야에 관심을 가지고 있으면서 한 분야에서는 최고의 전문가인 이런 창의적이고 별난 사람들이 대단한 제품을 만들고 협력에도 뛰어남을 보았다.

우리는 위대한 무언가를 만들고 싶어 하는 사람들이다. 초기 환경을 고려하면 순수한 이유만을 가지고 합류했다.
채용이 이뤄지는 장소, 뛰어난 사람들은 다른 무언가를 하고 있을 확률이 높고 정말 다양한 장소에서 만날 수 있다. 우리는 그런 사람들을 찾아더녀야 한다.

⇒ 신규채용은 장기간 동안 지인의 지인들을 장기간 설득하는 과정이였다.
아직 알려지지 않은, 저평가되고 있는 실력자들
엘레베이터 피치를 하듯, 사람들에게도 이런 과정을 지속해야 한다.

⇒ 첫 10명의 경우, 아주 진실되고 정직했다는 것. 다른 사람들이 같이 일하고 싶은 사람으로서 주변에 믿음을 주고, 문제 접근에 대해 지적으로 솔직한 사람들
특정분야를 파는데 2년을 쏟은 누군가와 일을 하는 것이 당연히 훨씬 더 흥미로운 일, 사소한 디테일이라고 신경을 쓰는 사람들, 그리고 일을 끝마칠 수 있는 사람들

Q. 어떻게 뛰어난 사람을 알아보는 방법은??

⇒ 같이 일해보기 전까지는 100% 확신할 수가 없다.
재능은 2가지 부류로 나뉜다.

  1. 일을 하는데 필요한 재능들을 미리 알 수 있는 경우
  2. 그렇지 않은 경우 → 이 경우가 어렵고, 이때에는 누군가와 말하기 전에, 먼저 필요로 하는 분야에서 세계 최고수준이란 무엇을 의미하는지 생각

그 분야에서 세계적인 권위를 가진 사람들과 이야기하면서 그들은 무슨 요소들을 살피는지를 물어보는 것을 습관화하였다. 여기서 무슨 질문을 해야하는지 또한 알 수 있었다.
인터뷰에서의 질문들은 이 사람이 와서 일하기에 적합한가에 대한 답을 줄 수 있어야 한다.
(예를 들어, 문제를 해결하기 좋아하는 사람들에게 구글이 내는 기발한 문제들)

왜 이 아이디어가 좋은 아이디어인지 솔직하게 말하되, 어떤 점들이 어려울지 끔찍할 만큼 디테일들을 늘어놓는 것이 필요하다. (아이폰을 위한 채용 때에는 무슨 일을 하게 될지도 말을 안 했다고 한다. 3년간 가족을 볼 수 없겠지만 일이 끝나면 당신의 아이들의 아이들까지 당신이 만든 걸 기억하게 될 것이다.)

주위 사람들의 평을 받는 것도 중요하다. 경험이 있는 사람들에게 의견을 구하는 것이기 때문. (예를 들어, 인터뷰 때 우리는 모두 조나단을 압니다. 몇주 뒤에 그와 이야기를 하려고 합니다. 그에게 당신이 가장 잘하는 것, 가장 자랑스러워 하는 것, 당신이 나아지려고 하는 부분을 물어본다면 뭐라고 대답했을 것 같나요??)

그 다음에는 가볍게 느껴질 수 있는 질문을 조금 더 게량적으로 느끼게 만들 수 있는 질문을 하고 장기간에 걸쳐 측정을 진행 (예를 들어, 이 사람은 이 부분에서 평가하기에 같이 일했던 사람들 중 상위 1%입니까? 아니면 5%입니까? 아니면 10%입니까?) 상대평가를 강제하면 더 객관적인 평가를 받을 수 있다. 그냥 괜찮다는 말은 도움이 덜 될 수 있다.

⇒ 여러분이 원하는 방식대로 인터뷰를 이끌어 갈 수 있는 자신감이 필요하다. 보통 잘 모르면 알려진 방법들을 따라하게 되는데, 이것보다는 스스로 방법을 알아내는 것이 더 좋은 효과를 준다. (예들 들어, 엔지니어 → 코딩 테스트가 아닌 옆에서 코딩을 하게 하고 그 것을 지켜보는 것, 비즈니스 업무 → 프로젝트 위주로 이야기, 기존 프로젝트를 어떻게 발전시킬지, 어떤 새로운 프로젝트를 하고 싶은지 이야기)

⇒ 첫 10명의 경우, 최대한 일을 많이 해보고 뽑는 것이 필요하다. 모두와 적어도 최소 1주일은 일해보았다. 그리고 한가지 짚고 넘어갈 점은 사람들은 직접 경험하기 전까지는 첫 10명 채용과 사내문화 문제의 중요성을 깨닫지 못한다는 점.

Q. 회사가 10명으로 1000명 규모로 성장함에 따라 채용과 팀관리 정책에 대한 변화는??

⇒ 팀 관리 측면에서는 각각의 팀들이 더 큰 조직에 속한 한계 내에서 최대한 독립적이라고 느끼면서 민첩한 대응이 가능하게 하는 것. 시간에 걸쳐 회사를 여러 스타트업으로 이뤄진 스타트업으로 느끼게 만드는 것. (규격화된 프로세스들 아래 있는 거대한 회사가 아닌..)

한 가지 목표는 각각의 팀이 성과를 이루는데 필요한 자원에 대한 통제권을 가지게 하는 것, 제일 중요한 일이 무엇인지, 어떻게 측정해야 할지 알게 하는 것. 이것들이 이뤄지면 팀 관리가 어느 정도 가능해진다.

각각의 그룹 내에서 해결이 가능하게 하고 싶다. 문제를 어렵게 만들기는 하지만, 이것이 제품을 만드는데 있어 Pinterest가 가지고 있는 철학의 중심가치이다. 여러 분야의 사람들을 모아 놓으면 각자 다른 흥미들을 가지고 있다. 그들을 하나의 프로젝트로 묶고 걸림돌들을 없애주어 마음껏 능력을 펼치게 해주는 것.

채용은 회사 규모가 커짐에 따라서.. 네트워크를 통해서 더 많은 사람을 모을 수 있게 된다. 15 번째 직원이 스타트업과 대기업을 다 경험하면서.. 이런 경험들이 도움이 많이 되었다.

⇒ 변화에 따라서 시간의 길이가 급격하게 변하게 된다. 초기에는 1달 로드맵을 보고 있었다면, 후에는 1년후 나중에는 5년후를 보게 된다. 우리는 미리 계획하고 대비해야 한다.
초기에는 당장의 생산성을 중심으로 사람을 구하게 될 것이다. 그 이후에는 장기적인 관점으로 사람을 채용해야 한다.
시스템을 통해서 문제를 푸는 방법을 고민해야 한다.

Q. 어떻게 사람들에게 스타트업 합류를 하라고 설득할 수 있나요?

⇒ 불확실성이야말로 스타트업이 사람들에게 울림을 줄 수 있는 이유라고 생각한다. 성공이 확실하다면 지루하지 않을까요? 그리고 또 하나의 중요한 동기는 개인 성장 측면이다.

⇒ 무엇이 어려울 것인지, 당신의 최선의 계획은 무엇인지 말해보라. 그리고 그 사람의 역할이 왜 핵심적인지 말해줘라. 반대하는 점은 이 모든 것들을 눈가림 하는 것이다. 예를 들어, 이 문제를 정말 풀고 싶은지 알려면 다른 어떤 회사들에 지원했는지 물어보라. 보통은.. 문제에 집중하는 것이 아니라 괜찮은 회사를 가고 싶은 것이면 유명한 기업들의 리스트가 나올 것이다. 그들은 목적을 이루기 위해서가 아니라 경험을 위해서 합류한 사람들이기 때문이다.

Stripe의 경우는 초기의 4명의 Stripe 사용자들을 채용했다. 다른 방법으로는 구할 수 없었던 인재들이었고, 자신이 좋아하는 제품에서 일하는 것이기에 혜택을 제공했을 것이다.

Q. 사람을 관리하는 방법에 대해서 조금 더 상세하게 알고 싶다.

⇒ 최대 2주에 1번씩은 만나서 1대1 이야기를 해봐라. 토의사항은 매니저가 아니라 직원들이 정할 수 있어야 한다. 정말 신뢰가 쌓였을 경우에는 한달에 1번 정도로 늘릴 수 있을 것이다.

Q. 임원을 해고 또는 강등을 할 때, 어떤 식으로 당사자와 대화하고 어떤 식으로 주변에 설명하는가?

⇒ 누군가를 해고할 때 가장 중요한 것은 솔직해지는 것이다. 감정적이나 감상적은 맞는 방법이 아니다. 채용에서의 실패가 있었다는 것을 인정하고 문제점을 찾아야 한다. (해결의 좋은 시작점)
여러분은 누군가의 직업을 뺐을 수도 있고, 또 그래야만 합니다. 하지만 누군가의 자존심까지 뺏어서는 안 됩니다. (당신의 말이 그 사람의 평판이 될 것, 회사의 문제도 확실하게 인지해야 할 수 있어야 한다.)

Q. 당신에게 반목하던 사람을 자기 편으로 만드는 방법?

⇒ 리더로서 더 나은 방향을 제시할 수 있어야 한다. 말 그대로 당신의 방식이 더 나아야 합니다.

Q. 다른 사람의 입장에서 생각하는 팁

⇒ 일상에서도 어렵지만, 비즈니스에서는 더 어렵다.
아직 절차를 갖춰놓지 않았다면, 잠시 멈춰서 생각을 하세요. 리더가 되기 위한 중요한 자질은 잠시 멈출 줄 알아야한다는 겁니다. 중요한 일이 있는데 아직 생각을 깊이 생각해보지 못 했다면.. 솔직하게 이야기를 해라. “중요한 문제라고 생각하고 다양한 관점을 모두 고려해서 답을 하고 싶다.”
*김치 문제: 작은 감정적인 문제로 숲 전체를 태우는 일 (깊숙히 묻을수록 숙성되는 것??)


Founder: CEO & 공동창업자

image.png

출처: How to Start a Startup, Lecture Note 13
  • CEO의 일
    1. 비전 수립
    2. 투자 유치
    3. 전도?
    4. 채용 & 관리
    5. 실행에 대한 기준을 세우는 것
  • 실상 창업자는 사방팔방에서 나오는 문제를 떠안는 사람
  • 내가 위대한 창업가인지 어떻게 알 수 있을까?
      • 혼자서 창업보다는, 2~3인의 공동창업이 낫다 (굉장히 다양한 능력이 요구되는데, 2~3명이 더 다양하게 대응을 할 수 있다)
      • 신뢰의 중요성
    1. 위치
      • 위대한 창업자는 반드시 문제와 과업을 해결해 줄 인적 네트워크를 찾기 때문
        • 실리콘밸리가 모든 산업에 적합한 곳은 아니다
    2. 역발상
      • 똑똑한 사람이 이것을 보고 똘끼가 있다고 생각할까? 를 기준으로 삼으면 좋다.
          • 왜 똑똑한 사람들이 나의 의견에 동의하지 않는가 도 고려해야 한다
          • 내가 알지만 다른 사람들이 모르는 것은 무엇인가
    3. 일을 직접 vs 위임
      • 간단하게 둘다 해야 한다. (상황에 따라)
    4. 유연 vs 지속성 (Persistent)
      • 역시 둘다 상황에 따라
      • 기업처럼 투자철학이 있어야 한다. 그래야 이 기준에 따라서 선택을 할 수 있을 것이다.
    5. 자신감 vs 주의
      • 신념을 고수함과 동시에 다른 사람들의 반론도 받을 수 있어야 한다.
        (자신감을 유지하되 위험요소를 충분히 이해하라)
    6. 내성적 vs 외향적
      • 역시 둘다, 위대한 창업자는 이 경계를 자유롭게 넘나들 수 있다.
    7. Vision vs Data
      • 데이터 역시 당신이 설계하는 비전 안에서 의미가 있는 것이다.
      • Data 가 방향을 틀 수 있지만, 명확한 비전은 필요하다.
    8. Take Risks vs 위험 최소화
      • 사업가는 언제나 위험을 계산하고 과감하게 배팅할 수 있어야 한다.
      • 위험을 감수할 때, 지능적인 위험 감소를 추구해야 한다.
        • 위험은 최소화하되, 효과는 최대화할 수 있는 방안을 항상 강구해야 한다.
    9. Short Term vs Long Term
      • 당연하게도, 둘다 고려해야 한다.
  • 사업은 절벽에서 일단 뛰어내린 다음, 비행기를 만들어서 나르는 것이다.
  • 공동창업자
    • 스타트업이 망하는 가장 큰 망하는 이유로 공동창업자 간의 갈등
    • 오래알지 못하거나 단순하게 공동창업자를 구하는 것은 재앙이다
      • 대학에서 만나면 좋지만, 그러지 못한 경우 회사에서 좋은 사람들 확보
      • 오래알던 사람과 창업하는 것이 최선
    • ‘거침없는 지략가형’
      • 한 분야의 전문가 보다는 007 제임스 본드 같은 사람
      • 거칠지만 차분한 사람
    • 약 2~3 명이 이상적
    • Q. 공동창업자 간의 지분 분배
      ⇒ 일을 시작한지 얼마 안되었을 때 정리해야 한다. 서로 비슷한 것이 이상적
    • Q. 공동창업자 간의 관계가 깨질 경우?
      ⇒ 이에 대한 안정 장치가 필요하다 (조건부 지분분배)

Management: 경영

  • 회사를 설립하는 것은 제품을 잘 만드는 것만큼 어렵다. 기본적으로 사람은 비이성적이기 때문.
  • 회사를 설립하는 것은 “엔진”을 만드는 것과 같다. 아주 고성능의 문제가 없을 그런 기계를 만들 수 있어야 한다.
  • 매니저의 아웃풋 = 조직의 생산량 극대화 + 주변 팀의 영향력
  • 문제에 대한 분류가 필요하다.
    감기의 경우, 시간이 지나면 자연스럽게 나아지는 병이므로, 노력을 많이 투자할 필요가 없다.
  • Editing, 편집자가 창업자에 가장 적합하다.
    • 모든 팀원들을 위해 업무를 “명확하게”하고 “단순화”하는 일
    • 단순화를 시킨만큼 생산성이 올라갈 것이다.
  • 명확하게 만들기 위한 질문을 던져라.
  • 자원을 분배하라.
    • 여러분과 일하는 사람들 대부분이 자기 고유의 계회을 제시해야 한다. (Bottom-up)
    • 빨간 잉크의 양을 체크하라.
  • 조직의 일관된 목소리를 유지하라.

    • Economist, 글을 보면 한 사람이 쓴 것처럼 느껴질 것이다.
  • 위임하기
    • 위임의 문제는 결국 여러분(창업자)가 모든 일에 대한 책임을 진다는 점
    • 위임과 책임을 동시에 잡는 법
      • 과업 숙련도 (task-relevant maturity) 일을 많이 해본 사람에게 더 위임을 하는..
        • 경영자는 하나의 관리 방식만을 고수해서는 안 된다. 직원들에게 각가 맞는 방식을 사용해야 한다.
      • 결정에 대한 자신감 x 예상되는 결과 영향력 (2 x 2)
        • 확신이 적고, 영향력 또한 적다면 완벽하게 위임하라.
        • 확신이 크고, 영향이 큰 일은 직접 제대로 하라.

image.png

출처: How to Start a Startup, Lecture Note 14
  • 팀을 구성하기
    • 포와 탄약에 대한 비유, 채용되는 사람들은 대부분 탄약이고 그것을 움직이는 대포와 같은 소수의 사람들이 있다.
      한 번에 쏠 수 있는 탄약의 수는 대포의 수에 의해서 결정된다.
      대포같은 사람이란, 특정 아이디어를 구상단계에서부터 실제 상품을 고객에게 전달하고 사람들을 결집시킬 수 있는 사람이다. 문화적인 기량이 상당히 필요하다.
    • 대포를 늘리기 위해서는, 모두에게 결국 부러질때까지 점진적으로 책임의 볌위를 늘려나가는 것이 필요하다. 실패의 시점을 기억하고 그 수준으로 책임을 부여하면 된다.
    • 수평적인 관계에서 주변 동료들이 많이 찾는 사람이 있다면, 그 사람은 주변 사람들을 도와주는 사람일 것이다. 즉, 대포에 가까운 사람일 것이다.
  • Scaling, 언제 어떻게 확장을 할 것인가
    • 각각 회사마다 성장곡선이 다르다.
  • Insist on Focus, 한 가지 일에만 집중하게 하는 것
    • Peter 의 방식, 사람은 눈에 보이는 쉽게 해결할 수 있는 일을 먼저 처리하기 때문 → 누구도 문제를 제대로 풀기 위해서 시간의 100%을 사용하지 않는다.
  • Metrics & Transparency
    • Dashboard를 만들기를 추천한다.
      • 첫 대쉬보드는 창립자가 만들어라.
      • 이 대쉬보드에는 무엇이 중요한지 모두가 알 수 있도록 직관적이고 명확해야 한다.
    • 투명성
      • 회사의 모든 직원들은 회사내 벌어지는 모든 일을 알 수 있어야 한다.
      • 이사회의 결정이 나는 발표자료를 모든 직원들에게 공유
      • 모든 미팅에 대해서 전체 공유
      • 회의실 벽이 모두 유리로 되어있다.
      • 스티브잡스 Next → 투명 임금제도
    • Metrics
      • 한가지 요소에만 집중하지 말고, 트레이드오프가 되는 요소까지 같이 측정해야 한다. + 책임을 지는 사람의 수준
  • 예측이 불가능한 현상에 대한 분석이 필요하다. → 새로운 시장을 개척할 수 있는 기회
  • Details Matter
    • “모든 디테일을 잡는다면 100만달러짜리 사업을 시작하거나 100만불의 수익을 창출하거나 100만명의 사용자를 잡기위해 노력할 필요가 없다.”
    • 조직전체가 모든 일을 제대로 한다면, 결국 최고 수준의 팀을 가지게 될 것이다.
    • 직원들이 매일같이 일하고 살다시피하는 사무실 환경은 기업의 문화와 사람들이 결정하는 방식과 직원들이 투입하는 노력의 정도를 결정할 것이다. 이러한 디테일을 다른 사람에게 맡기지 말고 스스로 해라.
  • One Management Concept : 결정적인 결정을 할 때는, 그 결정에 대해서 바라보는 모든 사람들의 시각을 이해할 필요가 있다. 즉, 회사 전체의 시각에서 문제를 바라볼 수 있어야 한다.
    1. Demotions
      • 해고 vs 강등
        • 해고보다는 강등을 포함한 옵션을 주는 것이 개인에게도, 결정권자 입장에서도, 회사입장에서도 더 나을 것이다.
        • 강등 후, 사람들의 신임을 얻을 수 있을 것인가 또 당사자가 동기부여를 잃어버리지는 않을까
        • 이것은 고소득을 올리는 직책의 직원이 자신의 임무를 다하지 못했을 때 일어날 수 있는 일을 정의한다.
    2. Raises
      • 우수한 직원이 임금 인상을 요구한 경우
        • 직원 입장에서는 이러한 요구를 하기까지 굉장히 많은 단계를 거쳤을 것
        • 임금 인상을 요구하지 않는 직원들도 고려를 해야 한다.
        • 절차(원칙)는 중요하다. → 사내 문화를 보호할 수 있는 수단
    3. Sam Altman blog post
      • 스톡옵션을 행사하는 방법에 대한 제안 (행사가능 기간 10년)
        • 현재: 퇴사 후 90일 내에 처리를 해야하는 상황 + 행사를 하려면 필요한 돈의 문제
        • 90일로 선정이 된 이유는 주가에 대한 불확실성으로 손실 계산이 불가능했기 때문이다.
        • Cultural Statements (2가지의 대안책들)
          1. 직원들에게 솔직해지기, 10년후에도 행사할 수 있는 조건
          2. 사실 그대로 말해주기, 스톡옵션이라는 권리가 주어질 것이나 회사에 남아있어서 상장까지 시킬 수 있어야 받을 수 있는 권리다 → 어떤 사람을 채용하고 싶은지 말하는 바가 있다.
    4. History’s greatest practioner
      • Toussant (투싼) 에제
        • 주변의 적과 싸워서 이겨야 했다
          1. 자국의 군대 입장
          2. 적의 입장
          3. 나라의 문화 입장
            • ⇒ 약탈을 하지 않음, 강간 X, 장교 간의 불륜 X (장기적인 문화를 고려했기 때문)
            • ⇒ 전쟁에서 이겼을 때, 적군의 능력이 있는 장수를 고용 (전문성과 더 높은 수준의 문화를 원했기 때문)
        • 노예주에 대한 처분
          1. 노예들의 입장 (노예주를 죽이자)
          2. 투생의 입장 (기존의 노예로서의 입장, 설탕경제에 대한 이해)
          3. 노예주들의 입장 (사업을 하는 방식)
            • ⇒ 노예제 폐지, 노예주는 땅을 그대로 소유하되 임금을 지불, 강제 노동 금지 (마찬가지로 더 높은 수준의 문화를 원했기 때문)

결론 : 여러분이 배울 수 있는 가장 중요한 일이자 CEO 로서 가장 어려운 일이 바로 스스로가 회사를 직원들과 파트너들과 관점에서 바라보도록 훈련시키는 일이다. 여러분과 이야기하고 있지 않고 한 공간에 있지 않은 사람들의 관점에서 말입니다.

QnA 모음

Q. 탄약을 언제 많이 뽑아야 하나요?

⇒ 엔지니어의 경우에는 10~20명 정도가 충분할 것 같고, 포가 준비되었을 때 탄약을 뽑는 것이 맞다고 본다. 디자이너의 경우에는 조금 다르다.
X (총 생산량) / Y (팀원의 수) → 이 값을 가지고 직무평가를 한다고 해야 한다.
이럴 경우 Y 는 늘어나지 않을 것이다.

Q. 위임과 책임 그리고 디테일에 대한 조화를 어떻게 이룰 것인가?

⇒ 디테일을 잡는 다는 철학은 기업 초기에 매우 중요하다. 기준을 잡는 일이 때문.
그래야 나중에 들어온 사람들도 이 기준에 맞춰서 일을 할 수 있게 될 것이다. 문화는 곧 결정을 내리게 하는 사고의 틀이다.


User Interview: 사용자 인터뷰

  • Emmett – Twitch CEO
  • 누구와 대화를 하는지, 또 무엇을 묻고 얻을지는 굉장히 중요하다.
    Twitch의 경우, 시청자와 방송제작자의 피드백은 완전히 다를 것이다.
  • 강의 중심의 노트 필기 앱 케이스
    1. 여러분이 만드는 것에 대해서 배우기 위해서는 누구와 말을 해야 할까요?
      • 예시
        • 실제 강의를 듣는 학생들
          • 학원을 안 가고 집에서 인강을 듣는 사람들
          • 각각 다른 과목을 듣는 사람들
          • 공부 방법 별로 분류해서 만난다
          • ⇒ 학생들은 돈을 잘 쓰지 않는다. 오히려 대학 IT 서비스 팀 혹은 부모들을 대상으로 판매를 계획하는 것이 더 맞는 방향일 수 있다.
        • 강의를 하는 선생/강사
        • 영상으로 편집하는 편집자
      • 뭔가 대단한 아이디어가 있다면, 생각할 수 있는 가장 넓은 그룹의 사용자들을 생각해보라.
    2. 인터뷰를 통해서 무엇을 만들지 정해보자.
      • 질문에 꼬리에 꼬리를 물면서 더 세부적으로, 파고든다.
      • 첫 인터뷰에서는 기능에서 최대한 멀어져서, 문제에만 집중을 해야 한다.
        • 다양한 사람들과 문제에 대해서 이야기를 하다보면 큰 장애물이 있는 부분을 알게 된다. 이 부분이 제품의 핵심이 될 수 있다.
      • 한 분야의 6~8명을 인터뷰하면 정보를 거의 얻었다고 볼 수 있다.
    3. 인터뷰를 바탕으로 기능을 생각해보자.
      • 이 기능이면 충분한가? 이것을 보고 사람들이 우리의 제품으로 전환을 할까요?
        1. 직접 프로그래밍을 해서 세상에 공개한다.
        2. 위의 방법은 시간이 걸리기 때문에, 프로토타입 기법을 활용한다.
          • 이때, “내가 이런 기능을 생각해봤어” 라는 식으로 접근하면 좋은 피드백을 얻을 수 없다.
          • 기능을 평가하기 위해 최소한으로 가져야 하는 방법으로.. 다른 제품에 붙여보고, 사람들이 사용하는지 확인해보는 것
          • Money Test는 실제로 사람들이 돈을 주고 이 제품을 살 것인지 말해준다.
  • Twitch 케이스
    • 몇 가지 피드백을 보면.. 이런 이슈들이 있음에도 해당 제품을 사용한다는 것은 굉장한 의미가 있다.
    • 다른 제품 유저들의 피드백을 보면 완전히 다른 양상의 피드백을 얻을 수 있다.
    • 방송제작자의 피드백, 경쟁제품을 사용하는 방송제작자의 피드백, 일반 사용자의 피드백
    • 게이밍 방송시장의 경우, 일반사용자가 대부분이고 더 큰 시장임을 의미한다.
    • 유저 인터뷰를 한 사람들을 대상으로 문제점을 파악하고, 제품을 만들어서 제안!
  • 데이터를 기반으로 판단하는 것은 좋으나, 제품의 방향을 보여주지는 못 한다.

QnA 모음

Q. 스타트업이 인터뷰를 할때 실수하는 것들은?

⇒ 제품을 보여주지 말라. 제품을 보여주는 것은 기능에 대해서 말해주는 것과 같다.
사람들의 머리속에 있는 것을 파악해야지, 새로운 것을 넣으면 안 된다.
실제로 인터뷰해야 하는 사람이 아닌 대화 가능한 사람을 하는 경우가 많다. 실제 사용자가 누구인지 알아내는 과정이 필요하다.

Q. 회사 내 다른 사람들을 설득하는 방법

⇒ 인터뷰를 녹음해라. 만약 여러분이 어떤 것을 만들어야 된다고 주장하고 싶으면, 그저 인터뷰를 재생해주면 된다.

Q. 인터뷰를 어떤 툴을 통해서 진행했는가?

⇒ 이메일보다는 Skype와 같은 툴에서 진행해야 한다. 가장 흥미로운 포인트들은 “흥미롭군요, 좀 더 말씀해주세요” 에서 옵니다. 의도하지 않았던 순간에서 핵심이 나온다. (상호적인 피드백이 중요한 이유)

Q. 글로벌 시장에서의 인터뷰는 (다른 언어의 사용자들)?

⇒ 한국 시장의 경우, 통역자를 구해서 인터뷰를 해봤으나 실제 사용자의 대표를 구하기 어려운 문제가 있다.

Q. 인터뷰 대상자를 구하기 위한 채널과 보상은?

⇒ Twitch의 경우, 회사 웹사이트 내의 메시지 시스템이였다. (채널), 돈을 지불하면서 대화를 할 필요는 없었다. 보통 문제를 직시하고 있는 사람들은 보상없이 자신이 원하는 바를 이이기 한다.

Q. 사이트 자체적인 유저 피드백 도구들이 있나요?

⇒ 중요한 두번째 종류의 유저 피드백이 있다. 우리는 문제를 발견하는 것에 집중했기 때문에 사이트가 없었다.

Q. 제한된 리소스 상황에서 하나의 고객군에 집중해야 한다면?

⇒ 우리는 경쟁 제품을 사용하는 사람들에게 집중했다. 이미 우리가 요구하는 행동에 관심이 있었고, 이런 요구를 만족하면 옮길 것이라고 생각했기 때문이다. 또 회사 상황상 빠른 성장을 해야하는 상황이였다.

Q. 게임 퍼블리셔는 어떻게 대하였는가?

⇒ 누구도 대화를 하려고 하지 않았다. 제품을 사용자들이 많이 쓰게되면서 자연스럽게 퍼블리셔에게 우리가 중요해졌고, 대화를 하게 되었다.
제품은 계속해서 변화하고 그 때에 맞는 사람들과 대화를 하는 것이 중요하다.

Q. 사용자 입장에서 좋은 피드백을 주는 방법

⇒ 생각하는 진짜 문제를 이야기해줬으면 좋겠다. 횡성수설 했으면 좋겠고.. 그냥 아무 말이나 해줬으면 좋겠다. 그 사람에 대한 컨텍스트를 알 수록 무엇을 원하는지 알 수가 있다.


Legal & Accounting: 재무기초

image.png

출처: How to Start a Startup, Lecture Note 18
  • 자금 마련, 직원 고용, 계약 체결
  • Delaware Corporation (델라웨어 회사법)
    • 내가 이 일을 개인으로써 하고 있는지, 독립된 법인체인 기업을 대신하여 하고 있는 것인지
  • 자본 배분
    • 지분
    • 공동창업자들간의 지분관계 → 모든 창업자들이 동등한 배분을 받았다
    • 과거가 아닌 미래에만 집중
  • 주식 배분
    • 83(b) Election
    • 서류에 서명하고 그 증서를 가지고 있어라
  • 주식의 귀속 (Vesting)
    • 실리콘밸리 표준 4년, 클리프 1년: 1년 후 25%를 가지고, 점진적으로 가짐
    • 이 제도를 사용하는 이유? → 창업자가 퇴사를 하는 경우, 오랫동안 일할 수 있는 동기부여의 필요
  • Fundaraising
    • 벨류에이션 캡
    • 예) 500만 달러 캡, 10만 달러 투자 → 회사의 가치가 2천만 달러, 한주당 25센트로 구입 가능
    • 미래에 주식이 희석될 수 있음을 알려라
  • Investor Requests
    • 이사직 : 왠만하면 거절하는 것이 좋다, 전략과 방향성을 제시해줄 수 있는 인재는 돈으로도 살 수 없다
    • 어드바이저: 도움이 되는 조언을 하는 경우가 드물다, 투자를 한 이상 도와주는 것은 당연한 일이다.
    • pro-rata 권리: 미래에 추가적인 주식을 매입함으로써, 회사 내의 지분을 유지할 수 있는 권리
    • 정보에 대한 권리: YC는 한달에 한번씩 투자자들에게 업데이트를 추천
  • Company Expenses
    • 사무실 대여, 직원 고용 등등
    • “내가 각 세부 사항을 이야기해야할 때, 부끄러울 항목이 하나라도 있는가?”
    • 각종 영수증은 챙겨야 한다
  • 창업자 고용
    • 창업자가 무급으로 일하는 것은 불법이다.
    • Payroll Service를 사용하라
    • 창업자가 퇴사하는 경우, 문제가 되는 경우가 존재
  • 직원 고용
    • 정규직과 계약직의 차이
    • 근로자 관련 보험, …
    • 이 역시, 스스로 업무를 보는 것보다는 서비스를 이용하라
  • 직원 해고
    • 가능한 빨리, 명확하게 진행하라
  • Legitimacy

Sales and Marketing: 영업과 마케팅

  • 영업 → 창업을 하면 창업자가 하게 될 것
    • 제품, 산업 도메인에 대한 이해필요

image.png

출처: How to Start a Startup, Lecture Note 19 – 1
  • Almighty Funnel – 1. Prospecting, 2. Conversations 3. Closing 4. Revenue / Promised Land

image.png

출처: http://egloos.zum.com/maniac-blogging/v/5197166
  • 각 단계별로 효과적이였던 전략
    1. Prospecting
      • 기술 수용 주기
        • 얼리어답터 = 잠재적 고객 (약 2.5%)
        • 이 말은 곧 약 2.5%의 고객들만이 전화를 받고 고민할 것이라는 것
      • Top 3: Your network, conferences, cold emails
        • 컨퍼런스: 초기 고객들을 만날 수 있는 장소,
    2. Conversations
      • 전화를 받으면 그들이 말을 하게 하라!
        • 영업의 1%의 사람의 경우, 70%는 그들이 이야기하게 하고 30%정도를 이야기 한다. 특히 문제를 제대로 이해하기 위한 질문을 한다
      • 통화 후 사후관리
      • 이메일(응답 없음) → 이메일 x n
      • 시간은 스타트업의 자산이다 → 초기에 살만한 고객인지 아닌지를 빠르게 구별할 수 있어야 한다.
    3. Closing
      • 표준 계약 서식
      • 사소한 부분에 집착하면서 시간을 잃지 말라.
      • “제품은 마음에 드는데, 이 기능이 있으면 좋겠네요” → 기능을 추가해도 이 사람이 쓴다는 보장은 없다.
        1. 해당 기능을 추가하는 것으로 계약을 체결
        2. 다른 고객들의 이야기를 종합하여 기능 추가를 판단
      • Free Trials: 프리 트라이얼 이후에 구매를 요구하는 것은 다시 제품을 파는 것이나 마찬가지이다. 누군가 프리 트라이얼을 요구한다면, “저희는 주로 연간 단위로 계약하는데, 이번에만 처음 30일, 60일 이내에 제품이 마음에 들지 않으시면 취소하실 수 있습니다”
    4. Revenue / Promised Land
      • 5가지 비즈니스방법 – 자신의 사업이 어디에 속하는지 확인하라
        • 10$, 10,000k Customer : Marketing
        • 100$, 1,000k Customer : Marketing
        • 1,000$, 100k Customer : Marketing
        • 10,000$, 10k Customer : Inside Sales
        • 100,000$, 1k Customer : Field Sales

B2B: 기업용 소프트웨어

  • Aaron Levie, Box CEO
  • 항상 변화하는 기술적인 요소를 주목하라.
  • Box – 파일 공유에 집중,
    소비자들에게는 더 많은 기능을 제공하고, 기업용으로는 보안 등.. 요구사항을 충족하지는 못하고 있던 상황
  • 소비자 / 기업 간의 시장 규모 → 가치에 대한 등식이 다르다
    (소비자 돈을 최대한 적게 쓰려고 하고, 기업 입장에서는 돈보다는 효율과 효과에 집중)
  • On-Premise ↔ Cloud
    2명~ 30만명까지 다양한 기업을 지원할 수 있다는 것은, 진입할 수 있는 시장이 확대되는 것을 의미한다.
  • 기업에서 기술 혁신이 일어날 때, 딱 2번의 기회가 있을 것
    1. 원자재가 변화할 때 → 컴퓨팅 가격이 낮아지는 등
    2. 고객들이 기업의 제품에 대해서 새로운 경험을 필요로 할때 → 운송업에서의 우버
      ⇒ 지금이 단 하나의 산업군을 타겟으로 하는 수직적 소프트웨어 회사를 시작하기에 좋은 시간인지 보여준다. → 모든 분야에 적용할 수 있기 때문
  • 앞으로도 회사들은 더 똑똑하고, 효율적으로, 효과적으로 일하기 위해 나아갈 것이다.
  • 창업 관점에서의 조언들
    1. 기술의 변화를 찾아라. – 크고 근본적인 트렌드의 변화
      • 잘 살펴보면, 지금 적용되는 기술들은 이미 몇년 전에 시도했던 기술들일 것이다. (환경이 받춰주지 못했기 때문에)
    2. 의도적으로 작게 시작할 필요가 있다. – 이미 존재하는 제품들 사이에 끼어들 수 있는 쐐기 같은 제품이어야 한다.
    3. 불균형을 찾아야 한다. – 기존 업체들이 하지 못했거나, 하지 않은 일을 해야 한다.
    4. 아웃라이어를 찾아야 한다. – 제품의 얼리어답터를 활용하라.
    5. 고객의 말을 들어가 – 하지만 항상 이들이 원하는대로 해주지는 마라. 요구사항을 듣고 해석해서 정말 좋은 것을 만들 수 있어야 한다.
    6. 커스터마이징이 아닌, 모듈화를 해라
    7. 사용자에 집중하라 – 기업용 소프트웨어에 소비자 DNA을 넣어라.
    8. 바이럴 마케팅이 가능하게 하라. – 근본적으로는 제품이 중심에 있어야 한다.

Later-Stage Adivce: 후기 단계의 조언들

image.png

출처: How to Start a Startup, Lecture Note 20
  • 창업 후 12~24개월 후에 중요해지는 일들

Management

  • 약 25명의 직원이 있는 다음, 갑자기 구조의 부재를 느끼는 순간이 올 것
  • 해야할 것은 모든 직원들이 그들의 관리자가 누구인지 알게 하고, 직원마다 관리자가 한명이도록 하는 것. 마지막으로 모든 관리자들은 직접 보고해야할 대상을 아는 것.
  • 명확한 보고 체계가 중요
  • 관리구조를 혁신하려고 하지 마라. 혁신해야 할 것은 제품이다.
  • 훌륭한 제품을 만드는 것에서 훌륭한 회사를 만드는 일로 변경 된다.

    image.png

출처: How to Start a Startup, Lecture Note 20
  • 실패케이스
    1. 경력자 (시니어) 채용을 주저하는 것
    2. 영웅모드 (본보기)
      • 나는 휴가를 쓸 것이고, 직원을 더 뽑을 것이야. 앞으로 성장을 이 만큼 할 것이니 그것에 맞춰서 고용을 할 것이다.
    3. 나쁜 위임법
      • 나쁜 케이스 : 우리는 큰 일을 해야한다. 이것을 조사해주세요. 그럼 제가 결정하고 진행하면 됩니다.
      • 좋은 케이스: 우리는 큰 일을 해야 한다. 나는 당신을 신뢰하고 있다. 조사하고 어떻게 결정할지 알려주세요.
    4. 개인적인 정리
      • 개인의 생산성과 제품의 개발을 추적하는 일은 꼭 필요하다.
      • 추가로 단순히 어떤 일을 하고, 왜 그 일을 하는지 써 놓는 것도 중요하다. (‘어떻게’ 와 ‘왜’)
        • 이것이 회사의 규범이 될 것이다.
        • 왜 → 문화적 가치

HR

  • 명확한 구조 : 성과에 대한 피드백이 중요
  • 회사가 성장함에 따라서 보상 밴드가 필요해질 수 있다.
  • 지분 : 많은 주식을 직원들에게 나눠주라
    • 향후 10년간 3~5%를 회사의 직원들에게 나눠주어라
    • 개인적인 추천: 6년 Vesting
    • 옵션 관리 시스템의 필요성
  • 50명 이상의 직원일 때
    • 성추행, 다양성에 대한 교육
    • 번 아웃이 되지 않도록 관찰하기 → 이제 마라톤이 되기 때문에
    • 채용 절차
      • 채용하기 전에 내부 내정자를 내부 메일링 등을 통해서 공지
    • 직원 늘리기 프로그램
    • 팀의 다양성
    • 초기 직원들에 대한 관리
      • 일반적으로 회사가 직원들보다 빠르게 성장한다
      • 직접적으로, 솔직하게 이야기해보라 → “초기 직원들은 회사가 성장함에 따라서 무엇을 하고 싶을까”

Company Productivity

  • 초기에는 고려할 사항이 아니다.
  • 직원이 늘어나면서 생산성은 직원 수의 제곱으로 떨어진다.
  • 중요한 하나의 단어: Alignment
    • 모두 같은 페이지에 있고, 하나의 방향을 보게 하는 것
  • 방법 중 하나는 명확한 로드맵과 목표를 가지는 것
    • 무작위로 직원 중 3명에게 회사의 최상위 목표 3가지가 뭐냐고 물어보면.. 답을 할 수 있어야 한다
    • 만약 사람들이 결정의 뼈대(토대)를 알고 있다면, 같은 결정을 내릴 것이다.
  • 프로세스가 아닌 제품에 의해서 움직이고, 매일 딜리버리해라.
  • 커뮤니케이션 : 투명성과 리듬
    • 주간 관리회의
    • 매월 로드맵과 비전을 공유하는 올헨즈미팅
    • Offsite (워크샵)
  • 목표는 오랜 기간 가치를 만들어내는 회사를 만드는 것
    • 창업자들이 끌고가면서 하나의 제품에 혁신이 있을 수 있으나, 그 다음 것까지 혁신을 이룰 수 있어야 한다.

Mechanics

  • 회계, 재무 등
  • FF Stock (Founder’s Fund) in the B round
  • 지적재산권, 상표, 특허
    • 제품 출시 후, 11개월 후 정도가 적당하다. 임시특허
    • 상표권, 도메인 등
  • FP&A : 재무 모델
  • 세금 구조 짜기

Your Psychology

  • 갈수록 더 강도가 강해질 것이다.
  • 성공을 하게 된다면, 많은 haters가 생길 것이다. 그것을 무시해라.
  • 장기적인 관점을 가지는 것.
  • 지독한 번 아웃을 경험할 수 있다.
  • Focus
    • 인수합병에 관심을 가지지 말라. → 회사를 죽이는 방법이다
  • 스타트업은 창업자가 포기할때 망한다

Marketing & PR

  • 제품이 팔리기 시작하면, 그떄부터 조금씩 신경을 쓰라
  • 핵심 메시지는 창업자 스스로 찾아야 한다. → 회사가 어떤 메시지를 결정하는 일
  • 개인적으로 핵심적인 기자와 관계를 만들어라 (대행사를 교용하는 것보다 더 직접적으로 의견을 전달할 수 있다)

Deals

  • 좋은 제품을 만드는 것
  • 개인적인 관계를 발전 시키는 것
  • 경쟁 역학
  • 창업자서의 고집은 불편할 정도가 되어야 한다
  • 원하는 것이 있으면 요구하라
  • 스타트업이 겪는 그래프

QnA 모음

Q. 다양성에 대해서..

⇒ 원하는 것은 배경의 다양성이지, 비전의 다양성이 아니다. 배경의 통일은 획일화된 문화로 이기어지 때문이다.

Q. 개인적인 차원에서 생산성을 끌어올리는 방법

⇒ 3달에서 12달정도 시간 동안 해야하는 목표를 적은 종이를 만드는 것. + 매일보기
별도로 단기 리스트, 모든 사람들에 대한 리스트 (하는 일, 나눈 대화, 그외 정보들)

Q. 스타트업이 잘 실패하는 방법

⇒ 실패하고 있다면, 투자자들에게 말을 하고.. 자금이 바닥나지 않도록 해야한다. 빠르게 행동해야 한다. (직원들에게도, 투자자들에게도)

Q. YC 내 이민자 출신의 창업자 수

⇒ 41% 정도??

Q. 전문적인 CEO를 고용하기에 적절한 시기는?

⇒ Never, 창업자가 계속해서 운영을 하는 것, 좋은 제품을 만드는 관점으로는 꼭 그래야 한다

Q. YC가 스타트업을 선정하는 기준, 그리고 시간이 지나면서 변하는지?

⇒ 좋은 창업자와 좋은 아이디어. 기준은 변하지 않았다.

Q. 좋다고 생각하는 시장이 있지만, 아직 많이 알지 못하는 경우의 접근 방법

⇒ 1) 그냥 바로 들어가는 것, 하면서 배우라.

⇒ 2) 그 분야에 있는 회사에서 일하거나, 그 시장에서 1~2년간 무엇이라도 하는 것
후자를 약간 더 추천한다. 그러나 사용자에 대해 정말 제대로 배울 생각이 있다면 크게 상관 없다


끝으로

이번 기회에 다시 정리를 해보면서 내용들을 여러번 다시 보게되었습니다. 대략 7년이 지난 지금에도 적용이 되는 이야기가 대부분이라고 생각합니다. 각 강의에서 창업자들의 인사이트가 느껴지기도 하구요. 스타트업이 성장하고 커가는 방식은 다양할 수 있지만, ‘훌롱햔 제품을 만드는 것’ 이 가장 기본이 되는 방식일 것입니다.

언젠가는 훌륭한 제품 그리고 훌륭한 회사를 만들고, 위 강의처럼 인사이트를 공유해보고 싶네요.