hivemall-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From myui <...@git.apache.org>
Subject [GitHub] incubator-hivemall pull request #167: [HIVEMALL-220] Implement Cofactor
Date Fri, 19 Oct 2018 09:06:44 GMT
Github user myui commented on a diff in the pull request:

    https://github.com/apache/incubator-hivemall/pull/167#discussion_r226578854
  
    --- Diff: core/src/main/java/hivemall/mf/CofactorModel.java ---
    @@ -0,0 +1,715 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you 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
    + *
    + * Unless required by applicable law or agreed to in writing,
    + * software distributed under the License is distributed on an
    + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    + * KIND, either express or implied.  See the License for the
    + * specific language governing permissions and limitations
    + * under the License.
    + */
    +package hivemall.mf;
    +
    +import hivemall.annotations.VisibleForTesting;
    +import hivemall.fm.Feature;
    +import hivemall.utils.lang.Preconditions;
    +import hivemall.utils.math.MathUtils;
    +import it.unimi.dsi.fastutil.objects.Object2DoubleArrayMap;
    +import it.unimi.dsi.fastutil.objects.Object2DoubleMap;
    +import org.apache.commons.math3.linear.ArrayRealVector;
    +import org.apache.commons.math3.linear.Array2DRowRealMatrix;
    +import org.apache.commons.math3.linear.RealMatrix;
    +import org.apache.commons.math3.linear.RealVector;
    +import org.apache.commons.math3.linear.SingularValueDecomposition;
    +import org.apache.hadoop.hive.ql.metadata.HiveException;
    +
    +import javax.annotation.Nonnegative;
    +import javax.annotation.Nonnull;
    +import javax.annotation.Nullable;
    +import java.util.ArrayList;
    +import java.util.HashMap;
    +import java.util.List;
    +import java.util.Map;
    +import java.util.Random;
    +
    +
    +public class CofactorModel {
    +
    +    public enum RankInitScheme {
    +        random /* default */, gaussian;
    +
    +
    +        @Nonnegative
    +        private float maxInitValue;
    +        @Nonnegative
    +        private double initStdDev;
    +        @Nonnull
    +        public static CofactorModel.RankInitScheme resolve(@Nullable String opt) {
    +            if (opt == null) {
    +                return random;
    +            } else if ("gaussian".equalsIgnoreCase(opt)) {
    +                return gaussian;
    +            } else if ("random".equalsIgnoreCase(opt)) {
    +                return random;
    +            }
    +            return random;
    +        }
    +
    +        public void setMaxInitValue(float maxInitValue) {
    +            this.maxInitValue = maxInitValue;
    +        }
    +
    +        public void setInitStdDev(double initStdDev) {
    +            this.initStdDev = initStdDev;
    +        }
    +
    +
    +    }
    +
    +    @Nonnegative
    +    private final int factor;
    +
    +    // rank matrix initialization
    +    private final RankInitScheme initScheme;
    +
    +    @Nonnull
    +    private double globalBias;
    +
    +    // storing trainable latent factors and weights
    +    private final Map<String, double[]> theta;
    +    private final Map<String, double[]> beta;
    +    private final Object2DoubleMap<String> betaBias;
    +    private final Map<String, double[]> gamma;
    +    private final Object2DoubleMap<String> gammaBias;
    +
    +    private final Random[] randU, randI;
    +
    +    // hyperparameters
    +    private final float c0, c1;
    +    private final float lambdaTheta, lambdaBeta, lambdaGamma;
    +
    +    // solve
    +    private final RealMatrix B;
    +    private final RealVector A;
    +
    +    // error message strings
    +    private static final String ARRAY_NOT_SQUARE_ERR = "Array is not square";
    +    private static final String DIFFERENT_DIMS_ERR = "Matrix, vector or array do not
match in size";
    +
    +    public CofactorModel(@Nonnegative int factor, @Nonnull RankInitScheme initScheme,
    +                         float c0, float c1, float lambdaTheta, float lambdaBeta, float
lambdaGamma) {
    +
    +        // rank init scheme is gaussian
    +        // https://github.com/dawenl/cofactor/blob/master/src/cofacto.py#L98
    +        this.factor = factor;
    +        this.initScheme = initScheme;
    +        this.globalBias = 0.d;
    +        this.lambdaTheta = lambdaTheta;
    +        this.lambdaBeta = lambdaBeta;
    +        this.lambdaGamma = lambdaGamma;
    +
    +        this.theta = new HashMap<>();
    +        this.beta = new HashMap<>();
    +        this.betaBias = new Object2DoubleArrayMap<>();
    +        this.betaBias.defaultReturnValue(0.d);
    +        this.gamma = new HashMap<>();
    +        this.gammaBias = new Object2DoubleArrayMap<>();
    +        this.gammaBias.defaultReturnValue(0.d);
    +
    +        this.B = new Array2DRowRealMatrix(this.factor, this.factor);
    +        this.A = new ArrayRealVector(this.factor);
    +
    +        this.randU = newRandoms(factor, 31L);
    +        this.randI = newRandoms(factor, 41L);
    +
    +        Preconditions.checkArgument(c0 >= 0.f && c0 <= 1.f);
    +        Preconditions.checkArgument(c1 >= 0.f && c1 <= 1.f);
    +        this.c0 = c0;
    +        this.c1 = c1;
    +
    +    }
    +
    +    private void initFactorVector(String key, Map<String, double[]> weights) {
    +        if (weights.containsKey(key)) {
    +            return;
    +        }
    +        double[] v = new double[factor];
    +        switch (initScheme) {
    +            case random:
    +                uniformFill(v, randI[0], initScheme.maxInitValue);
    +                break;
    +            case gaussian:
    +                gaussianFill(v, randI, initScheme.initStdDev);
    +                break;
    +            default:
    +                throw new IllegalStateException(
    +                        "Unsupported rank initialization scheme: " + initScheme);
    +
    +        }
    +        weights.put(key, v);
    +    }
    +
    +    private static double[] getFactorVector(String key, Map<String, double[]> weights)
{
    +        return weights.get(key);
    +    }
    +
    +    private static void setFactorVector(String key, Map<String, double[]> weights,
RealVector factorVector) throws HiveException {
    +        double[] vec = weights.get(key);
    +        if (vec == null) {
    +            throw new HiveException();
    +        }
    +        copyData(vec, factorVector);
    +    }
    +
    +    private static double getBias(String key, Object2DoubleMap<String> biases)
{
    +        return biases.getDouble(key);
    +    }
    +
    +    private static void setBias(String key, Object2DoubleMap<String> biases, double
value) {
    +        biases.put(key, value);
    +    }
    +
    +    public void recordContext(String context, Boolean isItem) {
    +        if (isItem) {
    +            initFactorVector(context, beta);
    +            initFactorVector(context, gamma);
    +        } else {
    +            initFactorVector(context, theta);
    +        }
    +    }
    +
    +    public double[] getGammaVector(final String key) {
    +        return getFactorVector(key, gamma);
    +    }
    +
    +    public double getGammaBias(final String key) {
    +        return getBias(key, gammaBias);
    +    }
    +
    +    public void setGammaBias(final String key, final double value) {
    +        setBias(key, gammaBias, value);
    +    }
    +
    +    public double getGlobalBias() {
    +        return globalBias;
    +    }
    +
    +    public void setGlobalBias(final double value) {
    +        globalBias = value;
    +    }
    +
    +    public double[] getThetaVector(final String key) {
    +        return getFactorVector(key, theta);
    +    }
    +
    +    public double[] getBetaVector(final String key) {
    +        return getFactorVector(key, beta);
    +    }
    +
    +    public double getBetaBias(final String key) {
    +        return getBias(key, betaBias);
    +    }
    +
    +    public void setBetaBias(final String key, final double value) {
    +        setBias(key, betaBias, value);
    +    }
    +
    +    public Map<String, double[]> getTheta() {
    +        return theta;
    +    }
    +
    +    public Map<String, double[]> getBeta() {
    +        return beta;
    +    }
    +
    +    public Map<String, double[]> getGamma() {
    +        return gamma;
    +    }
    +
    +    public Object2DoubleMap<String> getBetaBiases() {
    +        return betaBias;
    +    }
    +
    +    public Object2DoubleMap<String> getGammaBiases() {
    +        return gammaBias;
    +    }
    +
    +    public void updateWithUsers(List<CofactorizationUDTF.TrainingSample> users)
throws HiveException {
    +        updateTheta(users);
    +    }
    +
    +    public void updateWithItems(List<CofactorizationUDTF.TrainingSample> items)
throws HiveException {
    +        updateBeta(items);
    +        updateGamma(items);
    +        updateBetaBias(items);
    +        updateGammaBias(items);
    +    }
    +
    +    /**
    +     * Update latent factors of the users in the provided mini-batch.
    +     */
    +    private void updateTheta(List<CofactorizationUDTF.TrainingSample> samples)
throws HiveException {
    +        // initialize item factors
    +        // items should only be trainable if the dataset contains a major entry for that
item (which it may not)
    +        // variable names follow cofacto.py
    +        double[][] BTBpR = calculateWTWpR(beta, factor, c0, lambdaTheta);
    +
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newThetaVec = calculateNewThetaVector(sample, beta, factor, B,
A, BTBpR, c0, c1);
    +            if (newThetaVec != null) {
    +                setFactorVector(sample.context, theta, newThetaVec);
    +            }
    +        }
    +    }
    +
    +    @VisibleForTesting
    +    protected static RealVector calculateNewThetaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, double[]> beta,
    +                                                        int numFactors, RealMatrix B,
RealVector A, double[][] BTBpR, float c0, float c1) throws HiveException {
    +        // filter for trainable items
    +        List<Feature> trainableItems = filterTrainableFeatures(sample.features,
beta);
    +        // TODO: is this correct behaviour?
    +        if (trainableItems.isEmpty()) {
    +            return null;
    +        }
    +
    +        double[] a = calculateA(trainableItems, beta, numFactors, c1);
    +
    +        double[][] delta = calculateWTWSubset(trainableItems, beta, numFactors, c1 -
c0);
    +        double[][] b = addInPlace(delta, BTBpR);
    +
    +        // solve and update factors
    +        return solve(B, b, A, a);
    +    }
    +
    +    /**
    +     * Update latent factors of the items in the provided mini-batch.
    +     */
    +    private void updateBeta(List<CofactorizationUDTF.TrainingSample> samples) throws
HiveException {
    +        // precomputed matrix
    +        double[][] TTTpR = calculateWTWpR(theta, factor, c0, lambdaBeta);
    +
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newBetaVec = calculateNewBetaVector(sample, theta, gamma, gammaBias,
betaBias, factor, B, A, TTTpR, c0, c1);
    +            if (newBetaVec != null) {
    +                setFactorVector(sample.context, beta, newBetaVec);
    +            }
    +        }
    +    }
    +
    +    @VisibleForTesting
    +    protected static RealVector calculateNewBetaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, double[]> theta,
    +                                                       Map<String, double[]> gamma,
Object2DoubleMap<String> gammaBias,
    +                                                       Object2DoubleMap<String>
betaBias, int numFactors, RealMatrix B, RealVector A,
    +                                                       double[][] TTTpR, float c0, float
c1) throws HiveException {
    +        // filter for trainable users
    +        List<Feature> trainableUsers = filterTrainableFeatures(sample.features,
theta);
    +        // TODO: is this correct behaviour?
    +        if (trainableUsers.isEmpty()) {
    +            return null;
    +        }
    +
    +        List<Feature> trainableCooccurringItems = filterTrainableFeatures(sample.sppmi,
gamma);
    +        double[] RSD = calculateRSD(sample.context, trainableCooccurringItems, numFactors,
betaBias, gammaBias, gamma);
    +        double[] ApRSD = addInPlace(calculateA(trainableUsers, theta, numFactors, c1),
RSD, 1.f);
    +
    +        double[][] GTG = calculateWTWSubset(trainableCooccurringItems, gamma, numFactors,
1.f);
    +        double[][] delta = calculateWTWSubset(trainableUsers, theta, numFactors, c1 -
c0);
    +        // never add into the precomputed `TTTpR` array, only add into temporary arrays
like `delta` and `GTG`
    +        double[][] b = addInPlace(addInPlace(delta, GTG), TTTpR);
    +
    +        // solve and update factors
    +        return solve(B, b, A, ApRSD);
    +    }
    +
    +    /**
    +     * Update latent factors of the items in the provided mini-batch.
    +     */
    +    private void updateGamma(List<CofactorizationUDTF.TrainingSample> samples)
throws HiveException {
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newGammaVec = calculateNewGammaVector(sample, beta, gammaBias,
betaBias, factor, B, A, lambdaGamma);
    +            if (newGammaVec != null) {
    +                setFactorVector(sample.context, gamma, newGammaVec);
    +            }
    +        }
    +    }
    +
    +    @VisibleForTesting
    +    protected static RealVector calculateNewGammaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, double[]> beta,
    +                                                        Object2DoubleMap<String>
gammaBias, Object2DoubleMap<String> betaBias,
    +                                                        int numFactors, RealMatrix B,
RealVector A, float lambdaGamma) throws HiveException {
    +        // filter for trainable items
    +        List<Feature> trainableCooccurringItems = filterTrainableFeatures(sample.sppmi,
beta);
    +        // TODO: is this correct behaviour?
    +        if (trainableCooccurringItems.isEmpty()) {
    +            return null;
    +        }
    +
    +        double[][] b = regularize(calculateWTWSubset(trainableCooccurringItems, beta,
numFactors, 1.f), lambdaGamma);
    +        double[] rsd = calculateRSD(sample.context, trainableCooccurringItems, numFactors,
gammaBias, betaBias, beta);
    +
    +        // solve and update factors
    +        return solve(B, b, A, rsd);
    +    }
    +
    +    private static double[][] regularize(double[][] A, float lambda) {
    +        for (int i = 0; i < A.length; i++) {
    +            A[i][i] += lambda;
    +        }
    +        return A;
    +    }
    +
    +    private void updateBetaBias(List<CofactorizationUDTF.TrainingSample> samples)
{
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            Double newBetaBias = calculateNewBias(sample, beta, gamma, gammaBias);
    +            // TODO: is this correct behaviour?
    +            if (newBetaBias != null) {
    +                setBetaBias(sample.context, newBetaBias);
    +            }
    +        }
    +    }
    +
    +    public void updateGammaBias(List<CofactorizationUDTF.TrainingSample> samples)
{
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            Double newGammaBias = calculateNewBias(sample, gamma, beta, betaBias);
    +            // TODO: is this correct behaviour?
    +            if (newGammaBias != null) {
    +                setGammaBias(sample.context, newGammaBias);
    +            }
    +        }
    +    }
    +
    +    @VisibleForTesting
    +    protected static Double calculateNewBias(CofactorizationUDTF.TrainingSample sample,
Map<String, double[]> beta,
    +                                             Map<String, double[]> gamma, Object2DoubleMap<String>
biases) {
    +        // filter for trainable items
    +        List<Feature> trainableCooccurringItems = filterTrainableFeatures(sample.sppmi,
beta);
    +        if (trainableCooccurringItems.isEmpty()) {
    +            return null;
    +        }
    +
    +        double rsd = calculateBiasRSD(sample.context, trainableCooccurringItems, beta,
gamma, biases);
    +        return rsd / trainableCooccurringItems.size();
    +
    +    }
    +
    +    @VisibleForTesting
    +    protected static double calculateBiasRSD(String thisItem, List<Feature> trainableItems,
Map<String, double[]> beta,
    +                                             Map<String, double[]> gamma, Object2DoubleMap<String>
biases) {
    +        double result = 0.d, cooccurBias;
    +        double[] thisFactorVec = getFactorVector(thisItem, beta);
    +        double[] cooccurVec;
    +
    +        for (Feature cooccurrence : trainableItems) {
    +            String j = cooccurrence.getFeature();
    +            cooccurVec = getFactorVector(j, gamma);
    +            cooccurBias = getBias(j, biases);
    +            double value = cooccurrence.getValue() - dotProduct(thisFactorVec, cooccurVec)
- cooccurBias;
    +            result += value;
    +        }
    +        return result;
    +    }
    +
    +    @VisibleForTesting
    +    protected static double[] calculateRSD(String thisItem, List<Feature> trainableItems,
int numFactors,
    +                                           Object2DoubleMap<String> fixedBias,
Object2DoubleMap<String> changingBias,
    +                                           Map<String, double[]> weights) throws
HiveException {
    +
    +        double b = getBias(thisItem, fixedBias);
    +
    +        double[] accumulator = new double[numFactors];
    +
    +        // m_ij is named the same as in cofacto.py
    +        for (Feature cooccurrence : trainableItems) {
    +            String j = cooccurrence.getFeature();
    +            double scale = cooccurrence.getValue() - b - getBias(j, changingBias);
    +            double[] g = getFactorVector(j, weights);
    +            addInPlace(accumulator, g, scale);
    +        }
    +        return accumulator;
    +    }
    +
    +    /**
    +     * Calculate W' x W plus regularization matrix
    +     */
    +    @VisibleForTesting
    +    protected static double[][] calculateWTWpR(Map<String, double[]> W, int numFactors,
float c0, float lambda) {
    +        double[][] WTW = calculateWTW(W, numFactors, c0);
    +        return regularize(WTW, lambda);
    +    }
    +
    +    private static void checkCondition(boolean condition, String errorMessage) throws
HiveException {
    +        if (!condition) {
    +            throw new HiveException(errorMessage);
    +        }
    +    }
    +
    +    @VisibleForTesting
    +    protected static double[][] addInPlace(@Nonnull double[][] A, @Nonnull double[][]
B) throws HiveException {
    +        checkCondition(A.length == A[0].length && A.length == B.length &&
B.length == B[0].length, ARRAY_NOT_SQUARE_ERR);
    +        for (int i = 0; i < A.length; i++) {
    +            for (int j = 0; j < A[0].length; j++) {
    +                A[i][j] += B[i][j];
    +            }
    +        }
    +        return A;
    +    }
    +
    +    @VisibleForTesting
    +    protected static List<Feature> filterTrainableFeatures(Feature[] features,
Map<String, double[]> weights) {
    +        List<Feature> trainableFeatures = new ArrayList<>();
    +        String fName;
    +        for (Feature f : features) {
    +            fName = f.getFeature();
    +            if (isTrainable(fName, weights)) {
    +                trainableFeatures.add(f);
    +            }
    +        }
    +        return trainableFeatures;
    +    }
    +
    +    @VisibleForTesting
    +    protected static RealVector solve(RealMatrix B, double[][] dataB, RealVector A, double[]
dataA) throws HiveException {
    +        // b * x = a
    +        // solves for x
    +        copyData(B, dataB);
    +        copyData(A, dataA);
    +        SingularValueDecomposition svd = new SingularValueDecomposition(B);
    +        return svd.getSolver().solve(A);
    +    }
    +
    +    private static void copyData(RealMatrix dst, double[][] src) throws HiveException
{
    +        checkCondition(dst.getRowDimension() == src.length && dst.getColumnDimension()
== src[0].length, DIFFERENT_DIMS_ERR);
    +        for (int i = 0, rows = dst.getRowDimension(); i < rows; i++) {
    +            for (int j = 0, cols = dst.getColumnDimension(); j < cols; j++) {
    +                dst.setEntry(i, j, src[i][j]);
    +            }
    +        }
    +    }
    +
    +    private static void copyData(RealVector dst, double[] src) throws HiveException {
    +        checkCondition(dst.getDimension() == src.length, DIFFERENT_DIMS_ERR);
    +        for (int i = 0; i < dst.getDimension(); i++) {
    +            dst.setEntry(i, src[i]);
    +        }
    +    }
    +
    +    private static void copyData(double[] dst, RealVector src) throws HiveException {
    --- End diff --
    
    add `@Nonnull` .. ditto


---

Mime
View raw message