regularizer.py

# @package optimizer
# Module caffe2.python.regularizer


from caffe2.python import core, utils
import numpy as np


class RegularizationBy(object):
    AFTER_OPTIMIZER = "after_optimizer"
    ON_LOSS = "on_loss"


class Regularizer(object):
    def __init__(self):
        self.kEpsilon = 1e-9

    """
    Adds regularization to train_net for given parameter. Its factor ahead of
    regularization is given when initialization.
    The param should be a BlobReference.
    """

    def __call__(self, net, param_init_net, param, grad=None, by=None):
        assert isinstance(param, core.BlobReference)
        by_enum = utils.EnumClassKeyVals(RegularizationBy)
        assert by in by_enum.values(), (
            "Regularizer of type {} is called with invalid by={}, "
            "not in {}".format(self.__class__, by, by_enum.values())
        )
        run_func = "_run_" + by
        assert hasattr(
            self, run_func
        ), "Regularizer of type {} does not implement function {}".format(
            self.__class__, run_func
        )
        return getattr(self, run_func)(net, param_init_net, param, grad)

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        return None

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        return None

    def _feature_grouping(self, param, net):
        # Possible alternative grouping method via summing over absolute values
        # Compute l2norm over feature weights
        # pow( sum_i { pow(theda_i, 2) } ,  0.5)
        param_mul = net.Mul([param, param], [net.NextScopedBlob("param_mul")])
        param_reduced = net.ReduceFrontSum(
            [param_mul], [net.NextScopedBlob("param_reduced")]
        )
        grouped_feature_weight_vec = net.Pow(
            [param_reduced],
            [net.NextScopedBlob("grouped_feature_weight_vec")],
            exponent=0.5,
        )

        return grouped_feature_weight_vec

    def _ensure_clipped(
        self,
        net,
        param,
        grad=None,
        min=None,
        max=None,
        open_range=False,
        left_open=False,
        right_open=False,
    ):
        min = (
            min + self.kEpsilon
            if min is not None and (open_range or left_open)
            else min
        )
        max = (
            max - self.kEpsilon
            if max is not None and (open_range or right_open)
            else max
        )
        input_blobs = (
            [param, grad.indices, grad.values]
            if isinstance(grad, core.GradientSlice)
            else [param]
        )
        net.EnsureClipped(input_blobs, [param], min=min, max=max)


class L1Norm(Regularizer):
    def __init__(self, reg_lambda):
        super(L1Norm, self).__init__()
        assert reg_lambda >= 0, "factor ahead of regularization should be 0 or positive"

        self.reg_lambda = reg_lambda

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        output_blob = net.NextScopedBlob(param + "_l1_regularization")
        net.LpNorm([param], [output_blob], p=1)
        net.Scale([output_blob], [output_blob], scale=self.reg_lambda)
        return output_blob

class LpNorm(Regularizer):
    def __init__(self, reg_lambda, p_value=0.5):
        """
        reg_lambda: parameter to scale regularization by

        p_value:    determines what type of Lp norm to calculate. If p > 0,
                    we will calculate Lp norm with the formula:
                    pow( sum_i { pow(theda_i, p) } ,  1/p)
        """
        super(LpNorm, self).__init__()
        assert reg_lambda > 0, "factor ahead of regularization should be greater than 0"
        assert p_value > 0, "p_value factor should be greater than 0"
        self.p_value = p_value
        self.reg_lambda = reg_lambda


    def _run_on_loss(self, net, param_init_net, param, grad=None):
        # TODO: the second dim (num of input nodes) of param is after feature preproc,
        # and does not correspond to the original num of dense features.
        # In the future, will want to create a util to reduce the input dim of param to
        # match the num of dense features.

        output_blob = net.NextScopedBlob(param + "_dense_feature_regularization")
        grouped_feature_weight_vec = self._feature_grouping(param, net)

        # Compute Lpnorm:
        # pow( sum_i { pow(theda_i, p) } ,  1/p)
        lp_vec_raised = net.Pow(
            [grouped_feature_weight_vec],
            [net.NextScopedBlob("lp_vec_raised")],
            exponent=self.p_value,
        )
        lp_vec_summed = net.ReduceFrontSum(
            [lp_vec_raised], [net.NextScopedBlob("lp_vec_summed")]
        )
        lp_norm = net.Pow(
            [lp_vec_summed],
            [net.NextScopedBlob("lp_vec")],
            exponent=(1 / self.p_value),
        )
        net.Scale([lp_norm], [output_blob], scale=self.reg_lambda)
        return output_blob


class L0ApproxNorm(Regularizer):
    def __init__(self, reg_lambda, alpha=0.01, budget=0):
        """
        reg_lambda: parameter to scale regularization by

        alpha:      hyper parameter to tune that is only used in the calculation
                    of approximate L0 norm

        budget:     desired number of features. If the number of features is greater
                    than the budget amount, then the least important features will
                    be penalized. If there are fewer features than the desired
                    budget, no penalization will be applied. Optional parameter, if
                    0, then no budget is used
        """
        super(L0ApproxNorm, self).__init__()
        assert reg_lambda > 0, "factor ahead of regularization should be greater than 0"
        assert alpha > 0, "alpha factor must be a positive value greater than 0"
        assert budget >= 0, "budget factor must be greater than or equal to 0"
        self.reg_lambda = reg_lambda
        self.alpha = alpha
        self.budget = float(budget)  # budget must be float for future calculations

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        # TODO: the second dim (num of input nodes) of param is after feature preproc,
        # and does not correspond to the original num of dense features.
        # In the future, will want to create a util to reduce the input dim of param to
        # match the num of dense features.

        output_blob = net.NextScopedBlob(param + "_dense_feature_regularization")
        grouped_feature_weight_vec = self._feature_grouping(param, net)

        # compute approximate L0 norm
        # sum_i ( min ( abs (theta_i), alpha))) / alpha
        l0_abs = net.Abs([grouped_feature_weight_vec], [net.NextScopedBlob("l0_abs")])
        l0_min = net.Clip([l0_abs], [net.NextScopedBlob("l0_min")], max=self.alpha)
        l0_summed = net.ReduceFrontSum([l0_min], [net.NextScopedBlob("l0_summed")])
        l0_norm = net.Scale(
            [l0_summed], [net.NextScopedBlob("l0_norm")], scale=(1 / self.alpha)
        )

        # incorporate budget factor
        # regularization = reg_lambda * max(0, l0_norm - budget)
        if self.budget:
            budget_blob = net.ConstantFill([], "budget", shape=[1], value=self.budget)
            l0_sub_budget = net.Sub(
                [l0_norm, budget_blob], [net.NextScopedBlob("l0_budget")]
            )
            relu_l0_sub_budget = net.Relu(
                [l0_sub_budget], [net.NextScopedBlob("relu_l0_sub_budget")]
            )
            net.Scale([relu_l0_sub_budget], [output_blob], scale=self.reg_lambda)
        else:
            net.Scale([l0_norm], [output_blob], scale=self.reg_lambda)
        return output_blob

class L1NormTrimmed(Regularizer):
    """
    The Trimmed Lasso: Sparsity and Robustness. https://arxiv.org/abs/1708.04527
    """
    def __init__(self, reg_lambda, k):
        super(L1NormTrimmed, self).__init__()
        assert reg_lambda >= 0, "factor ahead of regularization should be 0 or positive"
        assert isinstance(k, int), "k should be an interger as expected #. after selection"
        assert k >= 1, "k should be larger than 1"

        self.reg_lambda = reg_lambda
        self.k = k

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        output_blob = net.NextScopedBlob(param + "_l1_trimmed_regularization")
        abs = net.Abs([param], [net.NextScopedBlob("abs")])
        sum_abs = net.SumElements([abs], [net.NextScopedBlob("sum_abs")], average=False)
        topk, _, _ = net.TopK([abs], [net.NextScopedBlob("topk"), net.NextScopedBlob("id"), net.NextScopedBlob("flat_id")], k=self.k)
        topk_sum = net.SumElements([topk], [net.NextScopedBlob("topk_sum")], average=False)
        net.Sub([sum_abs, topk_sum], [output_blob])
        net.Scale([output_blob], [output_blob], scale=self.reg_lambda)
        return output_blob


class L2Norm(Regularizer):
    def __init__(self, reg_lambda):
        super(L2Norm, self).__init__()
        assert reg_lambda >= 0, "factor ahead of regularization should be 0 or positive"

        self.reg_lambda = reg_lambda

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        output_blob = net.NextScopedBlob(param + "_l2_regularization")
        net.LpNorm([param], [output_blob], p=2)
        net.Scale([output_blob], [output_blob], scale=self.reg_lambda)
        return output_blob


class ElasticNet(Regularizer):
    def __init__(self, l1, l2):
        super(ElasticNet, self).__init__()
        self.l1 = l1
        self.l2 = l2

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        output_blob = net.NextScopedBlob(param + "_elastic_net_regularization")
        l2_blob = net.NextScopedBlob(param + "_l2_blob")
        l1_blob = net.NextScopedBlob(param + "_l1_blob")
        net.LpNorm([param], [l2_blob], p=2)
        net.LpNorm([param], [l1_blob], p=1)
        net.Scale([l2_blob], [l2_blob], scale=self.l2)
        net.Scale([l1_blob], [l1_blob], scale=self.l1)
        net.Add([l1_blob, l2_blob], [output_blob])
        return output_blob


class ElasticNetL1NormTrimmed(Regularizer):
    def __init__(self, l1, l2, k):
        super(ElasticNetL1NormTrimmed, self).__init__()
        self.l1 = l1
        self.l2 = l2
        self.k = k

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        output_blob = net.NextScopedBlob(param + "_elastic_net_l1_trimmed_regularization")
        l2_blob = net.NextScopedBlob(param + "_l2_blob")
        net.LpNorm([param], [l2_blob], p=2)
        net.Scale([l2_blob], [l2_blob], scale=self.l2)

        l1_blob = net.NextScopedBlob(param + "_l1_blob")
        abs = net.Abs([param], [net.NextScopedBlob("abs")])
        sum_abs = net.SumElements([abs], [net.NextScopedBlob("sum_abs")], average=False)
        topk, _, _ = net.TopK([abs], [net.NextScopedBlob("topk"), net.NextScopedBlob("id"), net.NextScopedBlob("flat_id")], k=self.k)
        topk_sum = net.SumElements([topk], [net.NextScopedBlob("topk_sum")], average=False)
        net.Sub([sum_abs, topk_sum], [l1_blob])
        net.Scale([l1_blob], [l1_blob], scale=self.l1)

        net.Add([l1_blob, l2_blob], [output_blob])
        return output_blob


class MaxNorm(Regularizer):
    def __init__(self, norm=1.0):
        super(MaxNorm, self).__init__()
        self.norm = norm

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        assert self.norm > 0, "norm should be bigger than 0."
        if isinstance(grad, core.GradientSlice):
            net.SparseNormalize(
                [param, grad.indices],
                [param],
                use_max_norm=True,
                norm=self.norm,
            )
        else:
            raise NotImplementedError("MaxNorm is not supported for dense parameters")


class ConstantNorm(Regularizer):
    def __init__(self, norm=1.0):
        super(ConstantNorm, self).__init__()
        self.norm = norm

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        assert self.norm > 0, "norm should be bigger than 0."
        if isinstance(grad, core.GradientSlice):
            net.SparseNormalize(
                [param, grad.indices],
                [param],
                use_max_norm=False,
                norm=self.norm,
            )
        else:
            raise NotImplementedError(
                "ConstantNorm is not supported for dense parameters"
            )


class SparseLpNorm(Regularizer):
    def __init__(self, p, reg_lambda):
        super(SparseLpNorm, self).__init__()
        assert p in (1.0, 2.0), "Sparse Lp regularization only implemented for p = 1.0 and p = 2.0."
        assert reg_lambda > 0, "factor ahead of regularization should be greater than 0."
        self.p = p
        self.reg_lambda = reg_lambda

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        if isinstance(grad, core.GradientSlice):
            net.SparseLpRegularizer(
                [param, grad.indices],
                [param],
                p=self.p,
                reg_lambda=self.reg_lambda,
            )
        else:
            raise NotImplementedError("SparseLpNorm is not supported for dense parameters")


class SparseL1Norm(SparseLpNorm):
    def __init__(self, reg_lambda):
        super(SparseL1Norm, self).__init__(p=1.0, reg_lambda=reg_lambda)


class SparseL2Norm(SparseLpNorm):
    def __init__(self, reg_lambda):
        super(SparseL2Norm, self).__init__(p=2.0, reg_lambda=reg_lambda)


class LogBarrier(Regularizer):
    """
    Wright, S., & Nocedal, J. (1999). Numerical optimization. Springer Science,
    35(67-68), 7. Chapter 19
    """

    def __init__(self, reg_lambda, discount_policy="inv", discount_options=None):
        """
        discount is a positive weight that is decreasing, and here it is implemented
        similar to the learning rate. It is specified by a learning rate policy and
        corresponding options
        """
        super(LogBarrier, self).__init__()
        assert reg_lambda > 0, "factor ahead of regularization should be 0 or positive"
        self.reg_lambda = reg_lambda
        self.discount_policy = discount_policy
        self.discount_options = discount_options or {"gamma": 1.0, "power": 1.0}

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        iteration = utils.BuildUniqueMutexIter(param_init_net, net)
        # Since we are most likely to do a minimization
        discount = net.NextScopedBlob(param + "_log_barrier_discount")
        net.LearningRate(
            [iteration],
            [discount],
            base_lr=-self.reg_lambda,
            policy=self.discount_policy,
            **self.discount_options
        )
        # TODO(xlwang): param might still be negative at the initialization time or
        # slightly negative due to the distributed training. Enforce it's non-negativity
        # for now (at least above machine epsilon)
        param_non_neg = net.NextScopedBlob(param + "_non_neg")
        net.Clip([param], [param_non_neg], min=self.kEpsilon)
        param_log = net.NextScopedBlob(param + "_log")
        net.Log([param_non_neg], [param_log])
        param_log_sum = net.NextScopedBlob(param + "_log_sum")
        net.SumElements([param_log], [param_log_sum])
        output_blob = net.NextScopedBlob(param + "_log_barrier")
        net.Mul([param_log_sum, discount], [output_blob], broadcast=1)
        return output_blob

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        self._ensure_clipped(net, param, grad, min=0, open_range=True)


class BoundedGradientProjection(Regularizer):
    """
    Wright, S., & Nocedal, J. (1999). Numerical optimization. Springer Science,
    35(67-68), 7. Chapter 16
    """

    def __init__(
        self, lb=None, ub=None, left_open=False, right_open=False, epsilon=None
    ):
        super(BoundedGradientProjection, self).__init__()
        lb = float(lb) if lb is not None else None
        ub = float(ub) if ub is not None else None
        epsilon = float(epsilon) if epsilon is not None else self.kEpsilon
        assert epsilon > 0, "Bounded Gradient Projection with invalid eps={eps}".format(
            eps=epsilon
        )
        assert (
            (lb is None)
            or (ub is None)
            or (
                lb + (epsilon if left_open else 0.)
                <= ub - (epsilon if right_open else 0.)
            )
        ), (
            "Bounded Gradient Projection with invalid "
            "{lp}ub={ub}, lb={lb}{rp}, eps={eps}".format(
                lb=lb,
                ub=ub,
                lp="(" if left_open else "[",
                rp=")" if right_open else "]",
                eps=epsilon,
            )
        )
        self.left_open = left_open
        self.right_open = right_open
        self.kEpsilon = epsilon
        self.lb = lb
        self.ub = ub

    def _run_after_optimizer(self, net, param_init_net, param, grad):
        self._ensure_clipped(
            net,
            param,
            grad,
            min=self.lb,
            max=self.ub,
            left_open=self.left_open,
            right_open=self.right_open,
        )


class GroupL1Norm(Regularizer):
    """
    Scardapane, Simone, et al. "Group sparse regularization for deep neural networks."
    Neurocomputing 241 (2017): 81-89.

    This regularizer computes l1 norm of a weight matrix based on groups.
    There are essentially three stages in the computation:
    1. Compute the l2 norm on all the members of each group
    2. Scale each l2 norm by the size of each group
    3. Compute the l1 norm of the scaled l2 norms
    """
    def __init__(self, reg_lambda, groups, stabilizing_val=0):
        """
        Args:
            reg_lambda: The weight of the regularization term.
            groups: A list of integers describing the size of each group.
                The length of the list is the number of groups.

        Optional Args:
            stabilizing_val: The computation of GroupL1Norm involves the Sqrt
                operator. When values are small, its gradient can be numerically
                unstable and causing gradient explosion. Adding this term to
                stabilize gradient calculation. Recommended value of this term is
                1e-8, but it depends on the specific scenarios. If the implementation
                of the gradient operator of Sqrt has taken into stability into
                consideration, this term won't be necessary.
        """
        super(GroupL1Norm, self).__init__()
        assert (
            (reg_lambda) >= 0
        ), "regularization weight should be 0 or positive"
        assert isinstance(groups, list), "groups needs to be a list"

        self.reg_lambda = (reg_lambda)
        self.groups = groups
        self.stabilizing_val = stabilizing_val

    def _run_on_loss(self, net, param_init_net, param, grad=None):
        """
        Args:
            param: The input blob to regularize. It should be a weight matrix
                blob with shape (output_dim, input_dim). input_dim should be
                equal to the sum of self.groups.

        Returns:
            group_l1_norm: The output blob after applying regularization.

        These are the steps of computation:
            1. square all elements
            2. sum by row
            3. lengthssum by group
            4. square_root all elements
            5. normalize each group based on group size
            6. compute l1 norm of each group
            7. scale the result with the regularization lambda
        """
        squared = net.Sqr(param)
        reduced_sum = net.ReduceSum(squared, axes=[0], keepdims=0)
        lengths_sum = net.LengthsSum(
            [
                reduced_sum,
                net.GivenTensorIntFill(
                    [], 1, shape=[len(self.groups)], values=self.groups
                ),
            ]
        )

        if self.stabilizing_val:
            net.Add(
                [lengths_sum, net.ConstantFill([], 1, value=self.stabilizing_val)],
                [lengths_sum],
                broadcast=1,
            )

        sqrt = net.Sqrt(lengths_sum)

        # Here we combine step 5 and step 7 into one operator call to
        # improve efficiency: values = np.sqrt(self.groups) * self.reg_lambda
        l2_scaled = net.Mul(
            [
                sqrt,
                net.GivenTensorFill(
                    [],
                    shape=[len(self.groups)],
                    values=np.sqrt(self.groups) * self.reg_lambda
                )
            ],
            ['normalized_l2_norm_scaled']
        )

        group_l1_norm = net.LpNorm(l2_scaled, ['group_l1_nrom'], p=1)

        return group_l1_norm