convolution.h

Go to the documentation of this file.

// nnet3/convolution.h

// Copyright      2017  Johns Hopkins University (author: Daniel Povey)

// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_NNET3_NNET_CONVOLUTION_H_
#define KALDI_NNET3_NNET_CONVOLUTION_H_

#include "base/kaldi-common.h"
#include "util/common-utils.h"
#include "itf/options-itf.h"
#include "matrix/matrix-lib.h"
#include "cudamatrix/cu-matrix-lib.h"
#include "nnet3/nnet-common.h"

#include <iostream>

namespace kaldi {
namespace nnet3 {



namespace time_height_convolution {

struct ConvolutionModel {
  int32 num_filters_in;   // number of input filters, e.g. 128.
  int32 num_filters_out;  // number of output filters, e.g. 256.
  int32 height_in;   // image height in, e.g. 40.
  int32 height_out;  // image height out, e.g. 40 (no subsampling or zero
                     // padding), 38 (with zero padding) (or for an example with
                     // 2x subsampling and no zero-padding: maybe 20).
  int32 height_subsample_out;  // subsampling factor for height.  In the 3
                               // examples given for height_out above, would be
                               // 1, 1 and 2 respectively.
  struct Offset {
    int32 time_offset;
    int32 height_offset;
    // give it a lexicographic ordering.
    inline bool operator < (const Offset &other) const {
      if (time_offset < other.time_offset) return true;
      else if (time_offset > other.time_offset) return false;
      else return height_offset < other.height_offset;
    }
    inline bool operator <= (const Offset &other) const {
      if (time_offset < other.time_offset) return true;
      else if (time_offset > other.time_offset) return false;
      else return height_offset <= other.height_offset;
    }
    inline bool operator == (const Offset &other) const {
      return time_offset == other.time_offset &&
          height_offset == other.height_offset;
    }
  };
  // For a 3x3 patch, the 'offsets' vector would be a list of 9 elements.  It's
  // always unique and sorted in lexicographic order.  See the extended comment
  // for struct ConvolutionModel for an explanation.
  std::vector<Offset> offsets;

  // This set, 'required_time_offsets', relates to zero-padding on the time
  // axis.  It should consist of a nonempty subset of the time-offset values
  // that have been seen in offsets[*].time_offset.  If there is no zero-padding
  // on the time (width) axis it would be that entire set.  If there is
  // zero-padding it would in most circumstances contain just the middle one,
  // e.g. of {0,1,2} we'd keep just {1}, or of {-3,0,3} we'd keep just {0}.  The
  // way to understand it is that all the time-offsets define dependencies in
  // the computation, but the list of 'required' offsets determines when a
  // computation can proceed when some of the dependencies are not present (any
  // non-required depenencies that were not present default to zero).
  std::set<int32> required_time_offsets;

  // This variable, which is derived from 'offsets', stores all the time offsets
  // that are present there, i.e. all the values of 'offsets[*].time_offset'
  std::set<int32> all_time_offsets;

  // This variable, which is derived from 'offsets', is the greatest common
  // divisor of the differences between the members of 'all_time_offsets';
  // e.g. if 'all_time_offsets' is {1,3,5} it would be 2.  It is used to figure
  // out what grid structure the input to the computation should have.  It is
  // set to zero if all_time_offsets.size() == 1.
  int32 time_offsets_modulus;


  // Computes the derived parameters 'all_time_offsets' and
  // 'time_offsets_modulus'.
  void ComputeDerived();

  // You'll notice that there is nothing here that explicitly specifies the
  // padding.  At this level, any padding on the height axis is implicit.  For
  // example, suppose there is a height-offset of -1, that implies we must be
  // padding at the bottom by at least 1, because the output height-index starts
  // from 0, and it would require the input at height -1, whereas the input
  // height-index starts from 0.  All padding is implicitly zero-padding.
  // Padding in the height dimension depends on (height_in, height_out,
  // height_subsample_out) and the 'height_offset' members of 'offsets'; padding
  // in the time dimension depends on 'required_time_offset'
  // vs. 'all_time_offsets'.

  // the InputDim() and OutputDim() really relate to its behavior in a
  // neural-net component, they are the input-dim and output-dim of the features
  // that the component has as input/output; physically, this is the column
  // dimension at the input and output of the component.  The time dimension
  // corresponds to the row-index of those features.
  int32 InputDim() const { return num_filters_in * height_in; }
  int32 OutputDim() const { return num_filters_out * height_out; }
  // number of rows in the parameter matrix
  int32 ParamRows() const { return num_filters_out; }
  // number of cols in the parameter matrix
  int32 ParamCols() const { return num_filters_in * static_cast<int32>(offsets.size()); }

  ConvolutionModel() { }

  bool operator == (const ConvolutionModel &other) const;

  /*
    Checks that this model makes sense, and returns true if so; if not, returns
    false (and if it's for certain less-obvious reasons, prints a warning first
     explaining why)..

   @param [in] check_heights_used  If true, part of the check is that all
         height-values at the input are used at some point (if they
         are not, this model is probably not what you intended).
   @param [in] allow_height_padding  If true, the checking code assumes that
         zero-padding on the height axis is permitted.
   @return  Returns true if the check passed, false otherwise.
  */
  bool Check(bool check_heights_used = true,
             bool allow_height_padding = true) const;

  // Returns an info-string that describes the model; it looks like
  // "num-filters-in=32, num-filters-out=64, height-in=40, height-out=40, ... ".
  // It's suitable for use in the 'info' output of the convolutional component.
  std::string Info() const;

  void Write(std::ostream &os, bool binary) const;
  void Read(std::istream &is, bool binary);
};


struct ConvolutionComputation {
  // num_filters_in and num_filters_out will be the same as in the model.
  int32 num_filters_in, num_filters_out;
  // height_out will be the same as in the model, but height_in may be
  // affected by reshaping (may be larger than the model's height_in).
  int32 height_in, height_out;
  // num_t_in and num_t_out are the number of rows in the input and output
  // matrices, but num_t_in may be affected by reshaping (may be smaller
  // than the model's num_t_in).
  // num_t_in will be >= num_times_out, and if it's greater it will be greater by a
  // small additive term, not by a multiplicative factor.
  int32 num_t_in, num_t_out;
  // num_images is the number of (n,x) pairs present in the input/output
  // indexes (although in most setups the x values will all be zero and
  // they will only vary in n).
  int32 num_images;

  // temp_rows and temp_cols define the size of a temporary matrix that the
  // computation uses.  temp_rows is the number of rows in that temporary
  // matrix; it will normally be equal to [multiplying from greatest to least
  // stride], (num_times_out * num_images), but it may be less in order to save
  // memory.  The execution code is in charge of looping over the data using
  // this matrix, in order to ensure that we cover all output rows.  If you are
  // just trying to understand the framework, assume that it's always equal to
  // num_times_out * num_images.

  // Note: if all of the steps[*].columns_are_contiguous values are true AND all
  // of the steps[*].columns.Dim() equal the input-num-cols (=num_filters_in *
  // height_in), then the temporary matrix is never needed and in that case,
  // temp_rows and temp_cols will both be zero.
  int32 temp_rows, temp_cols;

  // There may be a few steps in the computation (e.g. in a 3x3 convolution
  // without subsampling, there would be 3 steps), and the output is a summation
  // over contributions from each step.  each step has a different value
  // 'input_time_shift' (which is the number of input rows to discard at the
  // start of the input matrix, and won't be the same as the increment in 't',
  // if t_step_in in the ConvolutionComputationIo != 1.
  struct ConvolutionStep {
    // input_time_shift >= 0 is the number of initial time-indexes of the input
    // (i.e. the number of initial rows of the matrix) that we discard for this
    // step. We may discard some final time-indexes too, if needed so that the
    // total number of input time-indexes equals the total number of output
    // time-indexes.
    int32 input_time_shift;

    // params_start_col >= 0 says the start-column-index of the parameter matrix
    // where we start a sub-matrix to be used in this step (the num-cols of that
    // sub-matrix is given by columns.Dim() / height_out).
    int32 params_start_col;

    // height_map is the 'upstream' parameter from which 'columns' and
    // 'backward_columns' are derived; it compactly defines a column mapping
    // that is used when copying the input to a temporary matrix.
    // height_map.dim() * num_filters_in gives the num-cols in this temporary
    // matrix.  Each element of 'height_map' corresponds to a column range of
    // 'num_filters_in' columnn of the temporary matrix, and it says which
    // (same-sized) column-range of the input matrix is to be used as the source
    // for this data.  Its elements are in the range -1 <= height_map[i] <
    // num_filters_in, where -1's are used for blocks that have zero values.
    // height_map would be the same as 'columns' if num_filters_in == 1.
    std::vector<int32> height_map;

    // 'columns' is derived from 'pixel_map'.
    // columns.Dim() <= temp_cols is the num-columns of
    // a sub-matrix of the temporary matrix, that we
    // populate on this step.
    //
    // -1 <= columns[i] < height_in * num_filters_in
    // gives the dimension of the (reshaped) input to copy
    // If columns[i] == -1, it means write a zero.
    CuArray<int32> columns;

    // 'backward_columns' is derived from 'columns', it is used in
    // the backprop.  Each element of 'backward_columns' has the
    // same dim as the num-cols of the input matrix.  It's basically
    // the reverse map of 'columns', but split into multiple parts (and
    // padded with -1's as necessary) so that we can process elements
    // of the input which are copied multiple times to the temporary
    // matrix.
    std::vector<CuArray<int32> > backward_columns;

    // 'columns_are_contiguous' is derived from 'columns'; it's true if
    // 'columns' is a contiguous range of nonnegative integers, like '20, 21,
    // 22, ... '.
    bool columns_are_contiguous;
    // 'first_column' is derived from 'columns'; it equals columns[0].  It is
    // only of interest if 'columns_are_contiguous' is true (it enables an
    // optimization).
    int32 first_column;
  };
  std::vector<ConvolutionStep> steps;


  void Write(std::ostream &os, bool binary) const;
  void Read(std::istream &is, bool binary);

  // Computes derived variables in 'steps', i.e. 'columns', 'backward_columns',
  // columns_are_contiguous, and 'first_column'.
  void ComputeDerived();

  // check that this computation makes sense; crash if not.
  void Check() const;
};



struct ConvolutionComputationOptions {
  // max_memory_mb determines how many megabytes of memory we are willing to use
  // for the temporary matrix.  If it would exceed this amount, we do the
  // computation in batches.
  BaseFloat max_memory_mb;
  ConvolutionComputationOptions(): max_memory_mb(200.0) { }
};



// This struct represents the structure of the input and output of a
// convolutional computation (the input and output images; not the model itself,
// which is represented by ConvolutionModel).  We require that both the input
// and output indexes have a regular repeated structure, and if this is not the
// case then the input and output indexes will be padded with 'blank' indexes
// (indexes having a 't' vlaue of kNoTime) as needed to fit them into regular
// grids.  In addition 'blank' indexes may be added to reflect zero-padding on
// the input.
struct ConvolutionComputationIo {
  int32 num_images;  // 'num_images' is the number of distinct (n,x) values in
                     // the indexes.  Normally the x values would all be zero
                     // and the n values would go from 0 to num_images - 1, but
                     // this is not required.  We do enforce (via padding) that
                     // each (n,x) pair, i.e. each image, is associated with the
                     // same number of 't' values.

  // the following represents the set of 't' values on the input and output.
  // their meaning is obvious, but we should note that if there is just one
  // output or input index, we will set the step to zero when initially
  // creating this struct, and it may get set to other values later on, mostly
  // to avoid creating extra code paths.
  int32 start_t_in, t_step_in, num_t_in;
  int32 start_t_out, t_step_out, num_t_out;

  // reorder_t_in will be 1 in normal cases (no downsampling), but it may have values
  // greater than 1 (e.g. 2 if we're downsampling by a factor of 2).
  // This doesn't affect the set of indexes on the input, but it affects how they
  // are ordered.
  //
  //   If reorder_t_in == 1 then order the indexes one block for all
  // indexes with t=t0=start_t_in; then one block for all
  // t=t1=(start_t_in+t_step_in); then one block for t=t2, t=t3, and so on.
  //
  //   If reorder_t_in is >1 (for example, 2), then the values for t0 and t1 would
  // be interspersed in a single block; then the values for t1 and t2 would
  // be interspersed in the next block; and so on.  Within these blocks,
  // it's the 't' values that have the smaller stride.  This ordering allows
  // a reshaping such that we can imagine that the input and output have the
  // same 't' increment; it's useful in subsampling convolutions..
  int32 reorder_t_in;

  void Write(std::ostream &os, bool binary) const;
  void Read(std::istream &is, bool binary);
};

void CheckModelAndIo(const ConvolutionModel &model,
                     const ConvolutionComputationIo &io,
                     bool allow_extra_input = false);


void CompileConvolutionComputation(
    const ConvolutionModel &model,
    const std::vector<Index> &input_indexes,
    const std::vector<Index> &output_indexes,
    const ConvolutionComputationOptions &opts,
    ConvolutionComputation *computation,
    std::vector<Index> *input_indexes_modified,
    std::vector<Index> *output_indexes_modified);


void ConvolveForward(
    const ConvolutionComputation &conv_comp,
    const CuMatrixBase<BaseFloat> &input,
    const CuMatrixBase<BaseFloat> &params,
    CuMatrixBase<BaseFloat> *output);


void ConvolveBackwardData(
    const ConvolutionComputation &conv_comp,
    const CuMatrixBase<BaseFloat> &params,
    const CuMatrixBase<BaseFloat> &output_deriv,
    CuMatrixBase<BaseFloat> *input_deriv);

void ConvolveBackwardParams(
    const ConvolutionComputation &conv_comp,
    const CuMatrixBase<BaseFloat> &input,
    const CuMatrixBase<BaseFloat> &output_deriv,
    BaseFloat alpha,
    CuMatrixBase<BaseFloat> *params_deriv);


void GetComputationIo(
    const std::vector<Index> &input_indexes,
    const std::vector<Index> &output_indexes,
    ConvolutionComputationIo *io);


void GetIndexesForComputation(
    const ConvolutionComputationIo &io,
    const std::vector<Index> &orig_input_indexes,
    const std::vector<Index> &orig_output_indexes,
    std::vector<Index> *input_indexes,
    std::vector<Index> *output_indexes);


void PadComputationInputTime(const ConvolutionModel &model,
                             ConvolutionComputationIo *io);


void PadModelHeight(const ConvolutionModel &model,
                    ConvolutionModel *model_padded);


void UnPadModelHeight(const ConvolutionComputationOptions &opts,
                      const ConvolutionModel &model,
                      const ConvolutionModel &model_padded,
                      ConvolutionComputation *computation);

void AppendInputFrames(const ConvolutionModel &model,
                       ConvolutionComputationIo *io,
                       ConvolutionModel *model_appended,
                       ConvolutionComputationIo *io_appended);


/*
  This function takes a model and a specification of the comptuation's
  IO, and generates the computation.  This is stage 4 of the compilation.
  It assumes that stages 1, 2 and 3 have already been done so that:

    - Any required padding of the time axis (stage 1) and the height axis
      (stage 2) have been done (so any desired input values are available).
    - The t_stride_in and t_stride_out of the io object have the same value
      (stage 3).

  At this point the compilation process is actually quite simple: for each
  time shift (where the number of time shifts equals num_t_in + 1 - num_t_out
  of 'io'), we do a computation that copies and maybe duplicates the input
  columns to a temporary matrix, and then does a matrix multiplication
  between that temporary matrix
 */
void MakeComputation(const ConvolutionModel &model,
                     ConvolutionComputationIo &io,
                     const ConvolutionComputationOptions &opts,
                     ConvolutionComputation *computation);


} // namespace time_height_convolution

} // namespace nnet3





} // namespace kaldi


#endif