Continuous encoding of categorical variables trick - Revision history

Vipul at 04:10, 6 October 2014

2014-10-06T04:10:49Z

← Older revision		Revision as of 04:10, 6 October 2014
Line 101:		Line 101:

	However, this reduction in the number of features is negligible: the number of features is often more than several thousand times the number of feature families.		However, this reduction in the number of features is negligible: the number of features is often more than several thousand times the number of feature families.

			==Interaction with feature subsampling==

			Sometimes, we want to run training algorithms on subsets of the features. For instance, we may wish to run the training algorithm on the 1000 densest features, with the rationale that a good model for just these features can be a good way of initializing a [[gradient descent]]-type algorithm on all features.

			However, we need to be careful of destroying some properties of the data matrix when subsampling. Specifically, suppose our subsample contains some but not all features from within a feature family. Then, the examples for which the active feature is within the subsample are active have more 1s in them than examples for which the active feature is outside the subsample.

			This problem can be remedied as follows: for each feature family for which we are subsampling some but not all features, add another feature that is set to 1 for any example where the active feature is outside the subsample. The good properties of the matrix are maintained and the machine learning algorithm should give more sensible results.

			If we are using example pair differences, then we need to worry only about examples where we picked the positive feature and not the negative feature, or the negative feature but not the positive feature. We simply use the new feature to balance out any uncanceled feature within the family.

Vipul: /* Linear algebra implications */

2014-10-06T03:58:14Z

Linear algebra implications

← Older revision		Revision as of 03:58, 6 October 2014
Line 93:		Line 93:

	(Original total number of features) - (Number of feature families) + 1		(Original total number of features) - (Number of feature families) + 1

			In the case that we are using example pair differences, the total number of features would become:

			(Original total number of features) - (Number of feature families)

			There is no need to introduce a bias feature because taking differences of examples already eliminates any bias.

	However, this reduction in the number of features is negligible: the number of features is often more than several thousand times the number of feature families.		However, this reduction in the number of features is negligible: the number of features is often more than several thousand times the number of feature families.

Vipul: /* What this means for encoding examples */

2014-10-06T03:54:48Z

What this means for encoding examples

← Older revision		Revision as of 03:54, 6 October 2014
Line 85:		Line 85:
	\| The categorical variable takes too many values, so that we get too many features and each feature occurs in too few examples for us to be able to extract signal. \|\| Solution (1): We discard the sparse features, and instead keep only either the dense feature families or the dense features in all families.<br>Solution (2): We use some form of [[collaborative filtering]] or other information to group features into larger feature clusters, which become denser features.		\| The categorical variable takes too many values, so that we get too many features and each feature occurs in too few examples for us to be able to extract signal. \|\| Solution (1): We discard the sparse features, and instead keep only either the dense feature families or the dense features in all families.<br>Solution (2): We use some form of [[collaborative filtering]] or other information to group features into larger feature clusters, which become denser features.
	\|}		\|}

			==Linear algebra implications==

			From a linear algebra perspective, there's a bit of waste in the encoding. This is because the features within a feature family are not affinely independent: we know that the sum of the feature values within a feature family for each example equals 1. In particular, if there is more than one feature family, the set of features is not ''linearly'' independent either. Moreover, in the example pair difference setting, the sum of feature values within each feature family is zero, so the features within each feature family are linearly dependent.

			This is not considered a major problem. We ''could'' resolve it by projecting the vector space for each feature family onto a space of dimension one less, and introducing one overall bias feature. The total number of features would then become:

			(Original total number of features) - (Number of feature families) + 1

			However, this reduction in the number of features is negligible: the number of features is often more than several thousand times the number of feature families.

Vipul: /* Direct encoding of examples */

2014-10-06T03:48:55Z

Direct encoding of examples

← Older revision		Revision as of 03:48, 6 October 2014
Line 64:		Line 64:
	* The total number of features in the continuous encoding is the sum of the sizes of the sets of values for each categorical feature.		* The total number of features in the continuous encoding is the sum of the sizes of the sets of values for each categorical feature.
	* For any particular example, the number of features with value 1 equals the number of feature ''families'', which in turn equals the number of ''categorical'' features. This is constant across examples, and less than the total number of features. In the toy example above, the numbers are 4 and 12 respectively, but on large and feature-rich datasets, the former number is rarely more than a thousand, while the latter number can be in the millions or even billions.		* For any particular example, the number of features with value 1 equals the number of feature ''families'', which in turn equals the number of ''categorical'' features. This is constant across examples, and less than the total number of features. In the toy example above, the numbers are 4 and 12 respectively, but on large and feature-rich datasets, the former number is rarely more than a thousand, while the latter number can be in the millions or even billions.
			* In particular, the [[data matrix]] has the property that all the row sums are equal to each other, and to the number of feature families (i.e., the number of categorical variables).

	===Encoding of example pair differences (used for ranking and recommendation algorithms)===		===Encoding of example pair differences (used for ranking and recommendation algorithms)===

Vipul: /* Encoding of example pair differences (used for ranking and recommendation algorithms) */

2014-10-06T03:47:39Z

Encoding of example pair differences (used for ranking and recommendation algorithms)

← Older revision		Revision as of 03:47, 6 October 2014
Line 68:		Line 68:

	For some ranking purposes, our training data includes ''pairs'' of examples, where the goal is to learn that the first example in the pair is more preferable than the second. One way of training these is to construct our training example by taking the difference of the vectors corresponding to the examples. Such examples will include the numbers 0, 1, and -1 in the example rows.		For some ranking purposes, our training data includes ''pairs'' of examples, where the goal is to learn that the first example in the pair is more preferable than the second. One way of training these is to construct our training example by taking the difference of the vectors corresponding to the examples. Such examples will include the numbers 0, 1, and -1 in the example rows.

			Note that, if we are using example pair differences, ''each row sum is zero''.

	===Variations to handle possible problems===		===Variations to handle possible problems===

Vipul: /* Variations to handle possible problems */

2014-10-06T03:08:46Z

Variations to handle possible problems

← Older revision		Revision as of 03:08, 6 October 2014
Line 79:		Line 79:
	\|-		\|-
	\| The categorical variable is multi-valued, i.e., for some examples, it can take multiple values. \|\| Solution (1): Put a value of 1 for the features corresponding to each of the values the categorical variable takes. Disadvantage: The number of 1s is no longer constant across examples. Also, sparsity is destroyed if some categorical variables can take a very large number of values for some examples.<br>Solution 2: Put a value of <math>1/k</math> on each of the features corresponding to each of the values the categorical variable takes, where <math>k</math> is the number of values. Disadvantage: The matrix is no longer a 0-1 matrix. Also, the sparsity problem is common with Solution (1).<br>Solution 3: Pick a random value from the values the categorical variable takes, and just use that. Disadvantage: We are throwing away potentially valuable information.		\| The categorical variable is multi-valued, i.e., for some examples, it can take multiple values. \|\| Solution (1): Put a value of 1 for the features corresponding to each of the values the categorical variable takes. Disadvantage: The number of 1s is no longer constant across examples. Also, sparsity is destroyed if some categorical variables can take a very large number of values for some examples.<br>Solution 2: Put a value of <math>1/k</math> on each of the features corresponding to each of the values the categorical variable takes, where <math>k</math> is the number of values. Disadvantage: The matrix is no longer a 0-1 matrix. Also, the sparsity problem is common with Solution (1).<br>Solution 3: Pick a random value from the values the categorical variable takes, and just use that. Disadvantage: We are throwing away potentially valuable information.
			\|-
			\| The categorical variable takes too many values, so that we get too many features and each feature occurs in too few examples for us to be able to extract signal. \|\| Solution (1): We discard the sparse features, and instead keep only either the dense feature families or the dense features in all families.<br>Solution (2): We use some form of [[collaborative filtering]] or other information to group features into larger feature clusters, which become denser features.
	\|}		\|}

Vipul at 03:00, 6 October 2014

2014-10-06T03:00:12Z

← Older revision		Revision as of 03:00, 6 October 2014
Line 69:		Line 69:
	For some ranking purposes, our training data includes ''pairs'' of examples, where the goal is to learn that the first example in the pair is more preferable than the second. One way of training these is to construct our training example by taking the difference of the vectors corresponding to the examples. Such examples will include the numbers 0, 1, and -1 in the example rows.		For some ranking purposes, our training data includes ''pairs'' of examples, where the goal is to learn that the first example in the pair is more preferable than the second. One way of training these is to construct our training example by taking the difference of the vectors corresponding to the examples. Such examples will include the numbers 0, 1, and -1 in the example rows.

	==~~Sparsity property~~==		===Variations to handle possible problems===

	~~With the continuous encoding as described here, each example will have as many 1s as the~~ number of		A number of problems can occur with the above approach. Some solutions are discussed below.
	~~==Variations==~~

	~~Note~~ that ~~this continuous encoding allows us to consider~~ the ~~following variations~~:		{\| class="sortable" border="1"
			! Problem !! Potential solutions
	* Examples where the value of the categorical variable is unknown~~: In this case~~, we just ~~choose 0 for all~~ the ~~features~~.		\|-
	* Examples where the categorical variable is multi-valued: ~~In this case, we choose~~ 1 for ~~all~~ the ~~possible~~ values.		\| The value of a categorical variable is unknown for an example. \|\| Solution (1): Simply mark all the binary features are zero. The problem with this solution is that it disturbs the mathematical structure of the problem: the number of 1s in each example row is no longer constant across examples.<br>Solution (2): Add an extra feature in each family, for "unknown feature value", and mark that feature as 1 for the examples where the value is unknown. This is a more robust solution than (1) in all respects.<br>Solution (3): If we have some prior for what value the categorical variable could have, use that prior to assign probabilistic values to the corresponding features. For instance, if 80% of item sales are for headphones and 20% are for USB flash drives, we could assign a weight of 0.8 to headphones and 0.2 to USB flash drives if the item sold is unknown. This has some advantages, but also some disadvantages, relative to approach (2). The disadvantages are that we need information to assign probabilities, the matrix need not remain sparse, and the entries are no longer just 0s and 1s. Moreover, we should consider it the job of the machine learning algorithm to learn the probable item values rather than trying to infer that when constructing the examples.
	* Examples where there is ~~probabilistically quantified uncertainty as~~ to the ~~value of~~ the categorical variable: ~~In this case~~, ~~we assign~~ value ~~equal to~~ the ~~probability of~~ the ~~given feature being the correct one~~.		\|-
			\| The categorical variable is multi-valued, i.e., for some examples, it can take multiple values. \|\| Solution (1): Put a value of 1 for the features corresponding to each of the values the categorical variable takes. Disadvantage: The number of 1s is no longer constant across examples. Also, sparsity is destroyed if some categorical variables can take a very large number of values for some examples.<br>Solution 2: Put a value of <math>1/k</math> on each of the features corresponding to each of the values the categorical variable takes, where <math>k</math> is the number of values. Disadvantage: The matrix is no longer a 0-1 matrix. Also, the sparsity problem is common with Solution (1).<br>Solution 3: Pick a random value from the values the categorical variable takes, and just use that. Disadvantage: We are throwing away potentially valuable information.
			\|}

Vipul: /* What this means for encoding examples */

2014-10-06T02:47:41Z

What this means for encoding examples

← Older revision		Revision as of 02:47, 6 October 2014
Line 52:		Line 52:
	If we are representing this as a matrix row, and the 12 features are used as columns in the order provided, the row becomes:		If we are representing this as a matrix row, and the 12 features are used as columns in the order provided, the row becomes:

	<math>[1 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \~~\\end{pmatrix}~~</math>		<math>[\ 1 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \ ]</math>

	Basically, the correspondence is:		Basically, the correspondence is:
Line 67:		Line 67:
	===Encoding of example pair differences (used for ranking and recommendation algorithms)===		===Encoding of example pair differences (used for ranking and recommendation algorithms)===

			For some ranking purposes, our training data includes ''pairs'' of examples, where the goal is to learn that the first example in the pair is more preferable than the second. One way of training these is to construct our training example by taking the difference of the vectors corresponding to the examples. Such examples will include the numbers 0, 1, and -1 in the example rows.

	==Sparsity property==		==Sparsity property==

Vipul: /* What this means for encoding examples */

2014-10-06T02:37:57Z

What this means for encoding examples

@@ Line 14: / Line 14: @@
 ==What this means for encoding examples==
 Consider a machine learning problem where each training example has a bunch of features that are categorical variables. For example, to each single item purchase from an e-commerce website, we may associate categorical variables such as:
@@ Line 49: / Line 51: @@
 If we are representing this as a matrix row, and the 12 features are used as columns in the order provided, the row becomes:
-<math>\begin{pmatrix} 1 & 0 & 0  & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\\end{pmatrix}</math>
+<math>[1 \  0 \  0  \  0  \  1 \  0 \  0 \  1 \  0 \  0 \  0 \  1 \\\end{pmatrix}</math>
 Note that this continuous encoding allows us to consider the following variations:

Vipul at 02:30, 6 October 2014

2014-10-06T02:30:20Z

← Older revision		Revision as of 02:30, 6 October 2014
Line 49:		Line 49:

	If we are representing this as a matrix row, and the 12 features are used as columns in the order provided, the row becomes:		If we are representing this as a matrix row, and the 12 features are used as columns in the order provided, the row becomes:
			<math>e^{2 \pi \sqrt{3}}</math>

	<math>\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\\end{pmatrix}</math>		<math>\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\\end{pmatrix}</math>