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 Thu, 18 Oct 2018 07:59:41 GMT
Github user myui commented on a diff in the pull request:

    https://github.com/apache/incubator-hivemall/pull/167#discussion_r226202891
  
    --- Diff: core/src/main/java/hivemall/mf/CofactorModel.java ---
    @@ -0,0 +1,629 @@
    +/*
    + * 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.fm.Feature;
    +import hivemall.utils.math.MathUtils;
    +import hivemall.utils.math.MatrixUtils;
    +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 javax.annotation.Nonnegative;
    +import javax.annotation.Nonnull;
    +import javax.annotation.Nullable;
    +import java.util.*;
    +
    +public class CofactorModel {
    +
    +    public enum RankInitScheme {
    +        random /* default */, gaussian;
    +
    +        @Nonnegative
    +        protected float maxInitValue;
    +        @Nonnegative
    +        protected 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;
    +        }
    +
    +    }
    +
    +    private static final int EXPECTED_SIZE = 136861;
    +    @Nonnegative
    +    protected final int factor;
    +
    +    // rank matrix initialization
    +    protected final RankInitScheme initScheme;
    +
    +    @Nonnull
    +    private double globalBias;
    +
    +    // storing trainable latent factors and weights
    +    private Map<String, RealVector> theta;
    +    private Map<String, RealVector> beta;
    +    private Map<String, Double> betaBias;
    +    private Map<String, RealVector> gamma;
    +    private Map<String, Double> gammaBias;
    +
    +    // precomputed identity matrix
    +    private RealMatrix identity;
    +
    +    protected final Random[] randU, randI;
    +
    +    // hyperparameters
    +    private final float c0, c1;
    +    private final float lambdaTheta, lambdaBeta, lambdaGamma;
    +
    +    public CofactorModel(@Nonnegative int factor, @Nonnull RankInitScheme initScheme,
    +                         @Nonnull float c0, @Nonnull 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 HashMap<>();
    +        this.gamma = new HashMap<>();
    +        this.gammaBias = new HashMap<>();
    +
    +        this.randU = newRandoms(factor, 31L);
    +        this.randI = newRandoms(factor, 41L);
    +
    +        checkHyperparameterC(c0);
    +        checkHyperparameterC(c1);
    +        this.c0 = c0;
    +        this.c1 = c1;
    +
    +    }
    +
    +    private void initFactorVector(String key, Map<String, RealVector> weights)
{
    +        if (weights.containsKey(key)) {
    +            return;
    +        }
    +        RealVector v = new ArrayRealVector(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 RealVector getFactorVector(String key, Map<String, RealVector>
weights) {
    +        return weights.get(key);
    +    }
    +
    +    private static void setFactorVector(String key, Map<String, RealVector> weights,
RealVector factorVector) {
    +        assert weights.containsKey(key);
    +        weights.put(key, factorVector);
    +    }
    +
    +    private static double getBias(String key, Map<String, Double> biases) {
    +        if (!biases.containsKey(key)) {
    +            biases.put(key, 0.d);
    +        }
    +        return biases.get(key);
    +    }
    +
    +    private static void setBias(String key, Map<String, Double> biases, double
value) {
    +        biases.put(key, value);
    +    }
    +
    +    public void recordContext(Feature context, Boolean isParentAnItem) {
    +        String key = context.getFeature();
    +        if (isParentAnItem) {
    +            initFactorVector(key, beta);
    +            initFactorVector(key, gamma);
    +        } else {
    +            initFactorVector(key, theta);
    +        }
    +    }
    +
    +    public RealVector 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 RealVector getThetaVector(final String key) {
    +        return getFactorVector(key, theta);
    +    }
    +
    +    public RealVector 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, RealVector> getTheta() {
    +        return theta;
    +    }
    +
    +    public Map<String, RealVector> getBeta() {
    +        return beta;
    +    }
    +
    +    public Map<String, RealVector> getGamma() {
    +        return gamma;
    +    }
    +
    +    public Map<String, Double> getBetaBiases() {
    +        return betaBias;
    +    }
    +
    +    public Map<String, Double> getGammaBiases() {
    +        return gammaBias;
    +    }
    +
    +    public void updateWithUsers(List<CofactorizationUDTF.TrainingSample> users)
{
    +        updateTheta(users);
    +    }
    +
    +    public void updateWithItems(List<CofactorizationUDTF.TrainingSample> items)
{
    +        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)
{
    +        // 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
    +        RealMatrix BTBpR = calculateWTWpR(beta, factor, c0, identity, lambdaTheta);
    +
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newThetaVec = calculateNewThetaVector(sample, beta, factor, BTBpR,
c0, c1);
    +            if (newThetaVec != null) {
    +                setFactorVector(sample.context.getFeature(), theta, newThetaVec);
    +            }
    +        }
    +    }
    +
    +    protected static RealVector calculateNewThetaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, RealVector> beta,
    +                                                        int numFactors, RealMatrix BTBpR,
float c0, float c1) {
    +        // filter for trainable items
    +        List<Feature> trainableItems = filterTrainableFeatures(sample.features,
beta);
    +        // TODO: is this correct behaviour?
    +        if (trainableItems.isEmpty()) {
    +            return null;
    +        }
    +
    +        RealVector A = calculateA(trainableItems, beta, numFactors, c1);
    +
    +        RealMatrix delta = calculateWTWSubset(trainableItems, beta, numFactors, c1 -
c0);
    +        RealMatrix B = BTBpR.add(delta);
    +
    +        // solve and update factors
    +        RealVector newThetaVec = solve(B, A);
    +        return newThetaVec;
    +    }
    +
    +    /**
    +     * Update latent factors of the items in the provided mini-batch.
    +     */
    +    private void updateBeta(List<CofactorizationUDTF.TrainingSample> samples) {
    +        // precomputed matrix
    +        RealMatrix TTTpR = calculateWTWpR(theta, factor, c0, identity, lambdaBeta);
    +
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newBetaVec = calculateNewBetaVector(sample, theta, gamma, gammaBias,
betaBias, factor, TTTpR, c0, c1);
    +            if (newBetaVec != null) {
    +                setFactorVector(sample.context.getFeature(), beta, newBetaVec);
    +            }
    +        }
    +    }
    +
    +    protected static RealVector calculateNewBetaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, RealVector> theta,
    +                                                       Map<String, RealVector>
gamma, Map<String, Double> gammaBias,
    +                                                       Map<String, Double> betaBias,
int numFactors, RealMatrix TTTpR, float c0, float c1) {
    +        // 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);
    +        RealVector RSD = calculateRSD(sample.context, trainableCooccurringItems, numFactors,
betaBias, gammaBias, gamma);
    +        RealVector ApRSD = calculateA(trainableUsers, theta, numFactors, c1).add(RSD);
    +
    +        RealMatrix GTG = calculateWTWSubset(trainableCooccurringItems, gamma, numFactors,
1.f);
    +        RealMatrix delta = calculateWTWSubset(trainableUsers, theta, numFactors, c1 -
c0);
    +        RealMatrix B = TTTpR.add(delta).add(GTG);
    +
    +        // solve and update factors
    +        RealVector newBetaVec = solve(B, ApRSD);
    +        return newBetaVec;
    +    }
    +
    +    /**
    +     * Update latent factors of the items in the provided mini-batch.
    +     */
    +    private void updateGamma(List<CofactorizationUDTF.TrainingSample> samples)
{
    +        for (CofactorizationUDTF.TrainingSample sample : samples) {
    +            RealVector newGammaVec = calculateNewGammaVector(sample, beta, gammaBias,
betaBias, factor, identity, lambdaGamma);
    +            if (newGammaVec != null) {
    +                setFactorVector(sample.context.getFeature(), gamma, newGammaVec);
    +            }
    +        }
    +    }
    +
    +    protected static RealVector calculateNewGammaVector(CofactorizationUDTF.TrainingSample
sample, Map<String, RealVector> beta,
    +                                                      Map<String, Double> gammaBias,
Map<String, Double> betaBias,
    +                                                      int numFactors, RealMatrix idMatrix,
float lambdaGamma) {
    +        // filter for trainable items
    +        List<Feature> trainableCooccurringItems = filterTrainableFeatures(sample.sppmi,
beta);
    +        // TODO: is this correct behaviour?
    +        if (trainableCooccurringItems.isEmpty()) {
    +            return null;
    +        }
    +
    +        RealMatrix B = calculateWTWSubset(trainableCooccurringItems, beta, numFactors,
1.f)
    +                .add(calculateR(idMatrix, lambdaGamma, numFactors));
    +        RealVector rsd = calculateRSD(sample.context, trainableCooccurringItems, numFactors,
gammaBias, betaBias, beta);
    +
    +        // solve and update factors
    +        RealVector newGammaVec = solve(B, rsd);
    +        return newGammaVec;
    +    }
    +
    +    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.getFeature(), 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.getFeature(), newGammaBias);
    +            }
    +        }
    +    }
    +
    +    protected static Double calculateNewBias(CofactorizationUDTF.TrainingSample sample,
Map<String, RealVector> beta,
    +                                               Map<String, RealVector> gamma, Map<String,
Double> 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();
    +
    +    }
    +
    +    protected static double calculateBiasRSD(Feature thisItem, List<Feature> trainableItems,
Map<String, RealVector> beta,
    +                                           Map<String, RealVector> gamma, Map<String,
Double> biases) {
    +        double result = 0.d, cooccurBias;
    +        String i = thisItem.getFeature();
    +        RealVector thisFactorVec = getFactorVector(i, beta), cooccurVec;
    +
    +        for (Feature cooccurrence : trainableItems) {
    +            String j = cooccurrence.getFeature();
    +            cooccurVec = getFactorVector(j, gamma);
    +            cooccurBias = getBias(j, biases);
    +            double value = cooccurrence.getValue() - thisFactorVec.dotProduct(cooccurVec)
- cooccurBias;
    +            result += value;
    +        }
    +        return result;
    +    }
    +
    +
    +    protected static RealVector calculateRSD(Feature thisItem, List<Feature> trainableItems,
int numFactors,
    +                                    Map<String, Double> fixedBias, Map<String,
Double> changingBias, Map<String, RealVector> weights) {
    +
    +        String i = thisItem.getFeature();
    +        double b = getBias(i, fixedBias);
    +
    +        RealVector accumulator = new ArrayRealVector(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);
    +            RealVector g = getFactorVector(j, weights);
    +            addInPlace(accumulator, g, scale);
    +        }
    +        return accumulator;
    +    }
    +
    +    /**
    +     * Calculate W' x W plus regularization matrix
    +     */
    +    protected static RealMatrix calculateWTWpR(Map<String, RealVector> W, int numFactors,
float c0, RealMatrix idMatrix, float lambda) {
    +        RealMatrix WTW = calculateWTW(W, numFactors, c0);
    +        RealMatrix R = calculateR(idMatrix, lambda, numFactors);
    +        return WTW.add(R);
    +    }
    +
    +    protected static RealMatrix calculateR(RealMatrix idMatrix, float lambda, int numFactors)
{
    +        if (idMatrix == null) {
    +            idMatrix = new Array2DRowRealMatrix(MatrixUtils.eye(numFactors));
    +        }
    +        return idMatrix.scalarMultiply(lambda);
    +    }
    +
    +    protected static List<Feature> filterTrainableFeatures(Feature[] features,
Map<String, RealVector> weights) {
    +        List<Feature> trainableFeatures = new ArrayList<>();
    +        String fName;
    +        for (Feature f : features) {
    +            fName = f.getFeature();
    +            if (isTrainable(fName, weights)) {
    +                trainableFeatures.add(f);
    +            }
    +        }
    +        return trainableFeatures;
    +    }
    +
    +    protected static RealVector solve(RealMatrix B, RealVector a) {
    +        // b * x = a
    +        // solves for x
    +        SingularValueDecomposition svd = new SingularValueDecomposition(B);
    +        return svd.getSolver().solve(a);
    +
    +    }
    +
    +    protected static RealMatrix calculateWTW(Map<String, RealVector> weights, int
numFactors, float constant) {
    +        RealMatrix WTW = new Array2DRowRealMatrix(numFactors, numFactors);
    +        int i = 0, j = 0;
    +        for (int f = 0; f < numFactors; f++) {
    +            for (int ff = 0; ff < numFactors; ff++) {
    +                double val = constant * dotFactorsAlongDims(weights, f, ff);
    +                WTW.setEntry(f, ff, val);
    +            }
    +        }
    +        return WTW;
    +    }
    +
    +    protected static RealMatrix calculateWTWSubset(List<Feature> subset, Map<String,
RealVector> weights, int numFactors, float constant) {
    +        // equivalent to `B_u.T.dot((c1 - c0) * B_u)` in cofacto.py
    +        RealMatrix delta = new Array2DRowRealMatrix(numFactors, numFactors);
    +        int i = 0, j = 0;
    --- End diff --
    
    ` int i = 0, j = 0;` never used. 
    
    This could be found in IDE warning. Please resolve all IDE warnings. 


---

Mime
View raw message