<commit_before>/*
 * This file is part of the PSL software.
 * Copyright 2011 University of Maryland
 *
 * 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
 *
 * 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 edu.umd.cs.psl.application.learning.weight.maxmargin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import edu.umd.cs.psl.application.learning.weight.WeightLearningApplication;
import edu.umd.cs.psl.config.ConfigBundle;
import edu.umd.cs.psl.config.ConfigManager;
import edu.umd.cs.psl.database.Database;
import edu.umd.cs.psl.model.Model;
import edu.umd.cs.psl.model.atom.ObservedAtom;
import edu.umd.cs.psl.model.atom.RandomVariableAtom;
import edu.umd.cs.psl.model.kernel.CompatibilityKernel;
import edu.umd.cs.psl.model.kernel.GroundCompatibilityKernel;
import edu.umd.cs.psl.model.kernel.GroundKernel;
import edu.umd.cs.psl.model.parameters.NegativeWeight;
import edu.umd.cs.psl.model.parameters.PositiveWeight;

/**
 * Learns new weights for the {@link CompatibilityKernel CompatibilityKernels}
 * in a {@link Model} using max margin inference.
 * <p>
 * The algorithm is based on structural SVM with cutting plane optimization
 * The objective is to find a weight vector that minimizes an L2 regularizer 
 * subject to the constraint that the ground truth score is better than any 
 * other solution.
 * 
 * min ||w||^2 + C \xi
 * s.t. w * f(y) < min_x (w * f(x) - || x - y ||_1) + \xi
 * 
 * @author <NAME> <<EMAIL>>
 * @author <NAME> <<EMAIL>>
 */
public class MaxMargin extends WeightLearningApplication {
	
	private static final Logger log = LoggerFactory.getLogger(MaxMargin.class);
	
	/**
	 * Prefix of property keys used by this class.
	 * 
	 * @see ConfigManager
	 */
	public static final String CONFIG_PREFIX = "maxmargin";
		
	/**
	 * Key for double property, cutting plane tolerance
	 */
	public static final String CUTTING_PLANE_TOLERANCE_KEY = CONFIG_PREFIX + ".tolerance";
	/** Default value for CUTTING_PLANE_TOLERANCE_KEY */
	public static final double CUTTING_PLANE_TOLERANCE_DEFAULT = 1e-5;

	/**
	 * Key for double property, slack penalty C, where objective is ||w|| + C (slack)
	 */
	public static final String SLACK_PENALTY_KEY = CONFIG_PREFIX + ".slackpenalty";
	/** Default value for SLACK_PENALTY_KEY */
	public static final double SLACK_PENALTY_DEFAULT = 1;

	/**
	 * Key for positive integer, maximum iterations
	 */
	public static final String MAX_ITER_KEY = CONFIG_PREFIX + ".maxiter";
	/** Default value for MAX_ITER_KEY */
	public static final int MAX_ITER_DEFAULT = 500;
	
	/**
	 * Key for LossBalancingType enum property. Determines the type of loss
	 * balancing MaxMargin will use.
	 * 
	 * @see LossBalancingType
	 */
	public static final String BALANCE_LOSS_KEY = CONFIG_PREFIX + ".balanceloss";
	/** Default value for BALANCE_LOSS_KEY */
	public static final LossBalancingType BALANCE_LOSS_DEFAULT = LossBalancingType.NONE;
	
	/**
	 * Key for NormScalingType enum property. Determines type of norm scaling
	 * MaxMargin will use in its objective.
	 */
	public static final String SCALE_NORM_KEY = CONFIG_PREFIX + ".scalenorm";
	/** Default value for SCALE_NORM_KEY */
	public static final NormScalingType SCALE_NORM_DEFAULT = NormScalingType.NONE;
	
	/** Types of loss balancing MaxMargin can use during learning */
	public enum LossBalancingType {
		/** No loss balancing. All LossAugmentingGroundKernels weighted as -1.0. */
		NONE,
		/**
		 * Weights of LossAugmentingGroundKernels for true (false) ObservedAtoms
		 * are -2 * number of true (false) ObservedAtoms / total ObservedAtoms.
		 */
		CLASS_WEIGHTS,
		/**
		 * Weights of LossAugmentingGroundKernels for true (false) ObservedAtoms
		 * are -2 * number of false (true) ObservedAtoms / total ObservedAtoms.
		 */
		REVERSE_CLASS_WEIGHTS;
	}
	
	/** Types of norm scaling MaxMargin can use during learning */
	public enum NormScalingType {
		/** No norm scaling */
		NONE,
		/**
		 * Each weight is multiplied inside the objective norm by
		 * the number of GroundKernels sharing that weight (and a constant
		 * rescaling factor so that the norm has the same value as no scaling
		 * when all weights are 1.0)
		 */
		NUM_GROUNDINGS,
		/**
		 * Each weight is multiplied inside the objective norm by
		 * 1 / number of GroundKernels sharing that weight  (and a constant
		 * rescaling factor so that the norm has the same value as no scaling
		 * when all weights are 1.0)
		 */
		INVERSE_NUM_GROUNDINGS;
	}
	
	protected final double tolerance;
	protected final int maxIter;
	protected double slackPenalty;
	protected final LossBalancingType balanceLoss;
	protected final NormScalingType scaleNorm;
	
	protected PositiveMinNormProgram normProgram;
	
	public MaxMargin(Model model, Database rvDB, Database observedDB, ConfigBundle config) {
		super(model, rvDB, observedDB, config);
		tolerance = config.getDouble(CUTTING_PLANE_TOLERANCE_KEY, CUTTING_PLANE_TOLERANCE_DEFAULT);
		maxIter = config.getInt(MAX_ITER_KEY, MAX_ITER_DEFAULT);
		slackPenalty = config.getDouble(SLACK_PENALTY_KEY, SLACK_PENALTY_DEFAULT);
		balanceLoss = (LossBalancingType) config.getEnum(BALANCE_LOSS_KEY, BALANCE_LOSS_DEFAULT);
		scaleNorm = (NormScalingType) config.getEnum(SCALE_NORM_KEY, SCALE_NORM_DEFAULT);
	}
	
	@Override
	protected void initGroundModel()
			throws ClassNotFoundException, IllegalAccessException, InstantiationException {
		super.initGroundModel();
		
		/* Sets up the PositiveMinNormProgram (in this method for appropriate throws declarations) */
		normProgram = new PositiveMinNormProgram(kernels.size() + 1, config);
		
		/* Sets linear objective term */
		double [] coefficients = new double[kernels.size() + 1];
		coefficients[kernels.size()] = slackPenalty;
		normProgram.setLinearCoefficients(coefficients);
		
		/* Determines coefficients for the quadratic objective term */
		double [] quadCoeffs = new double[kernels.size()+1];
		if (NormScalingType.NONE.equals(scaleNorm)) {
			for (int i = 0; i < kernels.size(); i++)
				quadCoeffs[i] = 1.0;
		}
		else {
			/* Counts numbers of groundings to scale norm */
			int[] numGroundings = new int[kernels.size()];
			for (int i = 0; i < kernels.size(); i++) {
				Iterator<GroundKernel> itr = reasoner.getGroundKernels(kernels.get(i)).iterator();
				while(itr.hasNext()) {
					itr.next();
					numGroundings[i]++;
				}
			}
			
			if (NormScalingType.NUM_GROUNDINGS.equals(scaleNorm)) {
				for (int i = 0; i < kernels.size(); i++)
					quadCoeffs[i] = numGroundings[i];
			}
			else if (NormScalingType.INVERSE_NUM_GROUNDINGS.equals(scaleNorm)) {
				for (int i = 0; i < kernels.size(); i++)
					quadCoeffs[i] = (numGroundings[i] > 0.0) ? 1 / numGroundings[i] : 0.0;
			}
			else
				throw new IllegalStateException("Unrecognized NormScalingType.");
			
			/* 
			 * Rescales the coefficients so that the norm has the same value as no
			 * scaling when all weights are 1.0
			 */
			double coeffNorm = 0.0;
			for (double coeff : quadCoeffs)
				coeffNorm += coeff * coeff;
			coeffNorm = Math.sqrt(coeffNorm);
			double scalar = Math.sqrt(kernels.size()) / coeffNorm;
			for (int i = 0; i < kernels.size(); i++)
				quadCoeffs[i] *= scalar;
		}
		
		/* Sets quadratic objective term */<commit_msg>Fixed integer-division bug in MaxMargin.<commit_after>/*
 * This file is part of the PSL software.
 * Copyright 2011 University of Maryland
 *
 * 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
 *
 * 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 edu.umd.cs.psl.application.learning.weight.maxmargin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import edu.umd.cs.psl.application.learning.weight.WeightLearningApplication;
import edu.umd.cs.psl.config.ConfigBundle;
import edu.umd.cs.psl.config.ConfigManager;
import edu.umd.cs.psl.database.Database;
import edu.umd.cs.psl.model.Model;
import edu.umd.cs.psl.model.atom.ObservedAtom;
import edu.umd.cs.psl.model.atom.RandomVariableAtom;
import edu.umd.cs.psl.model.kernel.CompatibilityKernel;
import edu.umd.cs.psl.model.kernel.GroundCompatibilityKernel;
import edu.umd.cs.psl.model.kernel.GroundKernel;
import edu.umd.cs.psl.model.parameters.NegativeWeight;
import edu.umd.cs.psl.model.parameters.PositiveWeight;

/**
 * Learns new weights for the {@link CompatibilityKernel CompatibilityKernels}
 * in a {@link Model} using max margin inference.
 * <p>
 * The algorithm is based on structural SVM with cutting plane optimization
 * The objective is to find a weight vector that minimizes an L2 regularizer 
 * subject to the constraint that the ground truth score is better than any 
 * other solution.
 * 
 * min ||w||^2 + C \xi
 * s.t. w * f(y) < min_x (w * f(x) - || x - y ||_1) + \xi
 * 
 * @author <NAME> <<EMAIL>>
 * @author <NAME> <<EMAIL>>
 */
public class MaxMargin extends WeightLearningApplication {
	
	private static final Logger log = LoggerFactory.getLogger(MaxMargin.class);
	
	/**
	 * Prefix of property keys used by this class.
	 * 
	 * @see ConfigManager
	 */
	public static final String CONFIG_PREFIX = "maxmargin";
		
	/**
	 * Key for double property, cutting plane tolerance
	 */
	public static final String CUTTING_PLANE_TOLERANCE_KEY = CONFIG_PREFIX + ".tolerance";
	/** Default value for CUTTING_PLANE_TOLERANCE_KEY */
	public static final double CUTTING_PLANE_TOLERANCE_DEFAULT = 1e-3;

	/**
	 * Key for double property, slack penalty C, where objective is ||w|| + C (slack)
	 */
	public static final String SLACK_PENALTY_KEY = CONFIG_PREFIX + ".slackpenalty";
	/** Default value for SLACK_PENALTY_KEY */
	public static final double SLACK_PENALTY_DEFAULT = 1;

	/**
	 * Key for positive integer, maximum iterations
	 */
	public static final String MAX_ITER_KEY = CONFIG_PREFIX + ".maxiter";
	/** Default value for MAX_ITER_KEY */
	public static final int MAX_ITER_DEFAULT = 500;
	
	/**
	 * Key for LossBalancingType enum property. Determines the type of loss
	 * balancing MaxMargin will use.
	 * 
	 * @see LossBalancingType
	 */
	public static final String BALANCE_LOSS_KEY = CONFIG_PREFIX + ".balanceloss";
	/** Default value for BALANCE_LOSS_KEY */
	public static final LossBalancingType BALANCE_LOSS_DEFAULT = LossBalancingType.NONE;
	
	/**
	 * Key for NormScalingType enum property. Determines type of norm scaling
	 * MaxMargin will use in its objective.
	 */
	public static final String SCALE_NORM_KEY = CONFIG_PREFIX + ".scalenorm";
	/** Default value for SCALE_NORM_KEY */
	public static final NormScalingType SCALE_NORM_DEFAULT = NormScalingType.NONE;
	
	/** Types of loss balancing MaxMargin can use during learning */
	public enum LossBalancingType {
		/** No loss balancing. All LossAugmentingGroundKernels weighted as -1.0. */
		NONE,
		/**
		 * Weights of LossAugmentingGroundKernels for true (false) ObservedAtoms
		 * are -2 * number of true (false) ObservedAtoms / total ObservedAtoms.
		 */
		CLASS_WEIGHTS,
		/**
		 * Weights of LossAugmentingGroundKernels for true (false) ObservedAtoms
		 * are -2 * number of false (true) ObservedAtoms / total ObservedAtoms.
		 */
		REVERSE_CLASS_WEIGHTS;
	}
	
	/** Types of norm scaling MaxMargin can use during learning */
	public enum NormScalingType {
		/** No norm scaling */
		NONE,
		/**
		 * Each weight is multiplied inside the objective norm by
		 * the number of GroundKernels sharing that weight (and a constant
		 * rescaling factor so that the norm has the same value as no scaling
		 * when all weights are 1.0)
		 */
		NUM_GROUNDINGS,
		/**
		 * Each weight is multiplied inside the objective norm by
		 * 1 / number of GroundKernels sharing that weight  (and a constant
		 * rescaling factor so that the norm has the same value as no scaling
		 * when all weights are 1.0)
		 */
		INVERSE_NUM_GROUNDINGS;
	}
	
	protected final double tolerance;
	protected final int maxIter;
	protected double slackPenalty;
	protected final LossBalancingType balanceLoss;
	protected final NormScalingType scaleNorm;
	
	protected PositiveMinNormProgram normProgram;
	
	public MaxMargin(Model model, Database rvDB, Database observedDB, ConfigBundle config) {
		super(model, rvDB, observedDB, config);
		tolerance = config.getDouble(CUTTING_PLANE_TOLERANCE_KEY, CUTTING_PLANE_TOLERANCE_DEFAULT);
		maxIter = config.getInt(MAX_ITER_KEY, MAX_ITER_DEFAULT);
		slackPenalty = config.getDouble(SLACK_PENALTY_KEY, SLACK_PENALTY_DEFAULT);
		balanceLoss = (LossBalancingType) config.getEnum(BALANCE_LOSS_KEY, BALANCE_LOSS_DEFAULT);
		scaleNorm = (NormScalingType) config.getEnum(SCALE_NORM_KEY, SCALE_NORM_DEFAULT);
	}
	
	@Override
	protected void initGroundModel()
			throws ClassNotFoundException, IllegalAccessException, InstantiationException {
		super.initGroundModel();
		
		/* Sets up the PositiveMinNormProgram (in this method for appropriate throws declarations) */
		normProgram = new PositiveMinNormProgram(kernels.size() + 1, config);
		
		/* Sets linear objective term */
		double [] coefficients = new double[kernels.size() + 1];
		coefficients[kernels.size()] = slackPenalty;
		normProgram.setLinearCoefficients(coefficients);
		
		/* Determines coefficients for the quadratic objective term */
		double [] quadCoeffs = new double[kernels.size()+1];
		if (NormScalingType.NONE.equals(scaleNorm)) {
			for (int i = 0; i < kernels.size(); i++)
				quadCoeffs[i] = 1.0;
		}
		else {
			/* Counts numbers of groundings to scale norm */
			int[] numGroundings = new int[kernels.size()];
			for (int i = 0; i < kernels.size(); i++) {
				Iterator<GroundKernel> itr = reasoner.getGroundKernels(kernels.get(i)).iterator();
				while(itr.hasNext()) {
					itr.next();
					numGroundings[i]++;
				}
			}
			
			if (NormScalingType.NUM_GROUNDINGS.equals(scaleNorm)) {
				for (int i = 0; i < kernels.size(); i++)
					quadCoeffs[i] = numGroundings[i];
			}
			else if (NormScalingType.INVERSE_NUM_GROUNDINGS.equals(scaleNorm)) {
				for (int i = 0; i < kernels.size(); i++)
					quadCoeffs[i] = (numGroundings[i] > 0.0) ? 1.0 / numGroundings[i] : 0.0;
			}
			else
				throw new IllegalStateException("Unrecognized NormScalingType.");
			
			/* 
			 * Rescales the coefficients so that the norm has the same value as no
			 * scaling when all weights are 1.0
			 */
			double coeffNorm = 0.0;
			for (double coeff : quadCoeffs)
				coeffNorm += coeff * coeff;
			coeffNorm = Math.sqrt(coeffNorm);
			double scalar = Math.sqrt(kernels.size()) / coeffNorm;
			for (int i = 0; i < kernels.size(); i++)
				quadCoeffs[i] *= scalar;
		}
		
		/* Sets quadratic objective term */
{'fraction_non_alphanumeric': 0.09873450247318044, 'fraction_numerical': 0.006102653048114601, 'mean_word_length': 3.9738019169329073, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5221850', 'n_tokens_mistral': 5407, 'n_tokens_neox': 4808, 'n_words': 1486}