Exploring gating

gating.md

Gating is ??? a discrete, sparse choice of ... Limiting of information flow!? Why is it important? It can provide differentiable sparsity? Sparsity is the real goal?

Gating allows us to choose (at run time) which computations to apply. This means we can save ... (somewhat like attention).

Specifically I am interested in applying this to gating/heirarchical/... for image processing.

• Raisr

• MoE

• Spatially adaptive

• what is the best way to ensure that the the gating fn diversifies and the experts specialise?

• how can we learn which expert we should have selected?!? to make them neighbors in some sense?

• what is the best way to distribute shared vairables across different models? (as a way of )

Differentiable indexing

This idea revolves around the duality between linear functions and arrays. Instead of thinking of a matrices index as a look up table, we can think of them as inputs to a function. Which means that it could make sense to take derivatives with respect to indexes (if we assume they are reals). Or approximate with differences.

• What restrictions are there on the functions? Alternatives are;
  • piecewise linear approximations.
  • derivative of a 3 point parabola (that turns out to be the same thing?)
  • ?

Noise could really screw this over. Trade stability for computational efficiency (avg of iterations). The smaller the neighborhood used for the estimate, the lower the stability. Sounds like taylor expansions? Wait we want the sum/mean of local approximations to the gradient. How does that relate to integration?

Could learn/predict the gradient? dAdx = MA. Where M is some learned vector/array can can be applied to a neighborhood? Sounds a lot like a convolution??

Wait can you write integration as a matmul? So integration is just the linear combination (sum) of a bunch of 'linearisations' about points.

The interaction between higher order derivatives and their lower counter parts? Could take the higher order ones the 'atomic' and view them as generating the resulting function. It must get pretty complex how they interact with each other?

Heirarchical models

Settings.

Have;

• small number of labels (very expensive) + noisy contextual info (less expensive)

Need. Hierarchical labels. Which can be generated easily with some human input and the low level labels. E.g. Pinus radiata < Radiata < Introduced species Male < Hihi < Bird

Learn a mapping/grouping/clustering between labels. (aka the higher level patterns?)

Outrageously large nets

Problems with switching

• We only have a finite number of processors. And we want to keep the variables stored close to them. In fact we would prefer to have variables allocated to each processor. But, if we have to many parameters/too few processors. We need to move the parameters around quite often. This takes time and resources.
• How do you accumulate enough values for a batch in paths that are infrequently traversed? Store activations until you have enough?

How can we ever learn that we should have used another expert? Experts have 'opinions' about each other, they are neighbors somehow?

• A distance function between their parameters?
• Could even share some parameters?

moe.py

import tensorflow as tf
import numpy as np


class MixtureofExperts():
    def __init__(self, gating_fn, expert, shapes):
        # this is where we could construct the experts in a certain way
        # and pass that information to the gating fn
        self.experts = [expert(shape) for shape in shapes]
        self.gating_fn = gating_fn(self.experts)

    def __call__(self, x):
        return self.gating_fn(x)

################################################################################

class Expert():
    """
    Could have an internal state? E.g. rnns, or access to extrnal memory?
    Could share weights/messages between different experts?
    Could ?!?
    Could do one shot learning?
    """
    num = 0
    def __init__(self, experts):
        raise NotImplementedError

    def __call__(self, x):
        raise NotImplementedError


class FCLayer(Expert):
    def __init__(self, shape):
        num = str(Expert.num)
        with tf.variable_scope('Expert_'+num):
            Expert.num +=1
            self.W = tf.get_variable(shape=shape, name='W')
            self.b = tf.get_variable(shape=shape[-1], name='b')

    def __call__(self, x):
        return tf.nn.relu(tf.matmul(x, self.W) + self.b)

################################################################################

class Gating_fn():
    """
    How should we be choosing an expert?
    hasing, softmax, .. ??
    what domain specific info can we exploit?
    and what info about the experts can we exploit?
    ideally it is differentiable!
    """
    def __init__(self, experts):
        raise NotImplementedError

    def __call__(self, x):
        raise NotImplementedError


class Random(Gating_fn):
    def __init__(self, experts, k=4):
        self.experts = experts
        self.k = k

    def __call__(self, x):
        # this doesnt work?!?
        def get_random_expert():  # use tf.case to pick and eval expert
            ID = tf.random_uniform([],maxval=len(self.experts),
                                   dtype=tf.int32)
            return tf.case([(tf.equal(ID, i), lambda: expert(x))
                            for i, expert in enumerate(self.experts[1:])],
                           default=lambda: self.experts[0](x))
        # this works out because we apply the experts to an entire batch?!
        return tf.add_n([get_random_expert() for _ in range(self.k)])


class Noisy_Top_K(Gating_fn):
    #
    num = 0
    def __init__(self, experts, size=784, k=4):
        num = str(Expert.num)
        self.experts = experts
        self.k = k
        self.shape = (size, len(experts))
        with tf.variable_scope('Gate_'+num):
            self.Wg = tf.get_variable(shape=self.shape, name='Wg')
            self.Wn = tf.get_variable(shape=self.shape, name='Wn')

    def __call__(self, x):
        # calculate weightings
        n = tf.matmul(x, self.Wn)
        g = tf.matmul(x, self.Wg)
        H = g + tf.random_normal(shape=g.get_shape()) * tf.nn.softplus(n)

        # get top k
        values, indicies = tf.nn.top_k(H, self.k)
        bools = tf.greater(H, tf.reshape(tf.reduce_min(values, axis=1), (50, 1)))
        prob = tf.nn.softmax(tf.select(bools, H, -1e8 * tf.ones_like(H)))

        # use top k for forward prop
        output = tf.zeros((50, 10))
        for i, expert in enumerate(self.experts):  # TODO with map or while?
            # pick out relevant rows from batch
            rows = tf.reduce_any(tf.equal(i, indicies), axis=1)
            batch = tf.gather(x, tf.where(rows))
            batch_shape = batch.get_shape().as_list()
            batch = tf.reshape(batch, (-1, batch_shape[-1])) # gather adds extra dim

            # apply expert, or not
            def f1(expert, batch, output):
                y = expert(batch) * tf.gather(prob, tf.where(rows))
                return tf.scatter_add(output, tf.where(rows), y)
            def f2(expert, batch, output):
                return output
            output = tf.cond(tf.greater(batch.get_shape()[0],1),
                             lambda: expert(batch),
                             lambda: tf.zeros(shape))
            # what is faster. gather mul scatter. or just zero-padded matmul?
        return output


class Hashing(Gating_fn):
    # locally sensitive hashing function that fills buckets evenly
    pass

class Concrete(Gating_fn):
    # doesnt actually help us here?
    # as we really need discrete output, but we get a differentiable distribution over binary variables.
    pass

class Reinforced(Gating_fn):
    pass

class Difference(Gating_fn):
    #
    pass

class Memory(Gating_fn):
    # remembers things about each expert.
        # can use this memory to provide derivatives?
        # but we can compress the memory with a net?
    pass

class ExperienceReplay(Gating_fn):  # kind of like imagination/consolidation
    # if we (/ the expert) do not do as well as we expected (need good priors here?!?).
    # then;
        # - replay using another expert?
        # - save pair for later replay?
    pass

class Neighbor(Gating_fn):
    # knows that the experts share ?!?! and therefore can provide some gradients
    # to neighbors?
    # sharing and specialisation seem like opposites?
    pass

class Capsule(Gating_fn):
    # TODO some research on Hintons thoughs on this. currently no relation
    def __init__(self, experts):
        self.experts = experts

    def __call__(self, x):
        # want super specialists. not only do they get used in specific contexts.
        # but also on a subset of the input
        # then multiple can be used to validate each other???
        ### pseudocode
        experts = pick_experts(x, state)  # pick experts given context
        for expert in experts:
            y = feed(expert, x)  # choose what the expert sees (reminds me of spatial transformers?!?)
            z = expert(y)  # apply expert
        return combine(z)  # combine expert opinions in a principled way.



if __name__ == "__main__":
    x = tf.placeholder(shape=(50,784), dtype=tf.float32)
    M = MixtureofExperts(Random, FCLayer, [(784,10) for i in range(6)])
    y = M(x)

    sess = tf.Session()
    sess.run(tf.global_variables_initializer())
    sess.run(y, feed_dict={x:np.random.random((50, 784))}).shape
    writer = tf.summary.FileWriter('/tmp/test', sess.graph)