Methods and apparatus to determine weights for panelists in large scale problems
View Patent ↗Methods and apparatus to solve for a minimum variance solution for a constrained weight problem in a scalable and memory efficient manner are disclosed. An example method includes storing a constraint matrix and a population matrix into a memory, the constraint matrix representing demographics associated with a plurality of panelists in a population, the population matrix representing second demographics of the population; determining, by executing an instruction with a processor, a linear system based on a set of constraints including the constraint matrix and the population matrix; determining, by executing an instruction with the processor, a solution to the linear system by determining an inverse of a first matrix of the linear system, the determination of the inverse including breaking down the first matrix into blocks, dimensions of the blocks being no larger than dimensions of the constraint matrix and outputting a set of weights based on the inverse of the linear system, the set of weights satisfying the set of constraints.
1. A non-transitory computer readable storage medium comprising instructions which, when executed, cause a machine to at least:
store a constraint matrix and a population matrix into a memory, the constraint matrix representing demographics associated with a plurality of panelists in a population, the population matrix representing second demographics of the population;
determine a linear system based on a set of constraints including the constraint matrix and the population matrix;
determine a solution to the linear system by determining an inverse of a first matrix of the linear system, the determination of the inverse including breaking down the first matrix into blocks, dimensions of the blocks being no larger than dimensions of the constraint matrix, the determination of the inverse including:
reducing the dimensions of a second element of a third matrix to a size less than or equal to the dimensions of the constraint matrix, the third matrix being an inversion of a second matrix, the second matrix being an inversion of the first matrix, the reduced second element being a third element;
storing the reduced third matrix in the memory;
replacing, in the stored third matrix, the second element with the third element in the second matrix; and
replacing a first element of the second matrix with the second matrix; and
output a resultant set of weights based on the solution, the resultant set of weights satisfying the set of constraints.
2. The computer readable storage medium of claim 1 , wherein the linear system is a predictor linear system, the instructions to cause the machine to:
determine a first solution to the predictor linear system;
determine a corrector linear system based on the first solution;
solve the corrector linear system based on the set of constraints to determine an adjusted solution; and
adjust an initial set of weights based on an inverse of a fourth matrix of the corrector linear system, wherein the resultant set of weights is further based on the adjusted initial set of weights.
3. The computer readable storage medium of claim 2 , wherein the instructions cause the machine to calculate a second solution to the corrector linear system multiple times until the adjusted initial set of weight converges to the resultant set of weights, the multiple calculations based on prior solutions to the corrector linear system.
4. The computer readable storage medium of claim 1 , wherein the instructions cause the machine to apply the resultant set of weights to data associated with the panelists.
5. The computer readable storage medium of claim 4 , wherein the instructions cause the machine to apply the resultant set of weights by:
receiving a media exposure event from a panelist from the plurality of panelists with a weight from the set of weights; and
crediting demographics of the panelist for the media exposure event based on the weight.
6. The computer readable storage medium of claim 1 , wherein the resultant set of weights is an optimal solution to an equality constraint, the equality constraint being an equation including the constraint matrix, the population matrix, and the set of weights.
7. The computer readable storage medium of claim 6 , wherein:
the set of constraints further includes at least one of a non-negative constraint, a bound constraint, and the equality constraint; and
the optimal solution is a non-negative solution with minimum variance.
8. The computer readable storage medium of claim 1 , wherein the instructions cause the machine to generate the inverse of the first matrix of the linear system by:
separating components of the first matrix into a first set of blocks;
inverting the first matrix using blockwise inversion to generate the second matrix;
separating the first element of the second matrix into a second set of blocks; and
inverting the second matrix using blockwise inversion to generate the third matrix, the second element of the third matrix having dimensions larger than the constraint matrix.
9. The computer readable storage medium of claim 8 , wherein the instructions cause the machine to reduce the dimensions of the second element using Sherman-Morrison formula.
10. The computer readable storage medium of claim 9 , wherein the instructions cause the machine to conserve the memory by eliminating a need to store the first linear system.
11. An apparatus for determining a plurality of weights for a plurality of panelists representative of a population, the apparatus comprising:
memory to store a constraint matrix and a population matrix into a memory, the constraint matrix representing demographics associated with a plurality of panelists in a population, the population matrix representing second demographics of the population;
a weight determiner to:
determine a linear system based on a set of constraints including the constraint matrix and the population matrix;
determine a solution to the linear system by determining an inverse of a first matrix of the linear system, the determination of the inverse including breaking down the first matrix into blocks, dimensions of the blocks being no larger than dimensions of the constraint matrix, the weight determiner to determine the inverse by:
reducing the dimensions of a second element of a third matrix to a size less than or equal to the dimensions of the constraint matrix, the third matrix being an inversion of a second matrix, the second matrix being an inversion of the first matrix, the reduced second element being a third element;
storing the reduced third matrix in the memory;
replacing, in the stored third matrix, the second element with the third element in the second matrix; and
replacing a first element of the second matrix with the second matrix; and
output a resultant set of weights based on the solution, the resultant set of weights satisfying the set of constraints.
12. The apparatus of claim 11 , wherein the linear system is a predictor linear system, the weight determiner to:
determine a first solution to the predictor linear system;
determine a corrector linear system based on the first solution;
solve the corrector linear system based on the set of constraints to determine an adjusted solution; and
adjust an initial set of weights based on an inverse of a fourth matrix of the corrector linear system, wherein the resultant set of weights is further based on the adjusted initial set of weights.
13. The apparatus of claim 12 , wherein a second solution to the corrector linear system is calculated multiple times until the adjusted initial set of weight converges to the resultant set of weights, the multiple calculations based on prior solutions to the corrector linear system.
14. The apparatus of claim 11 , wherein the weight determiner is to apply the resultant set of weights to data associated with the panelists.
15. The apparatus of claim 14 , wherein the weight determiner is to apply the resultant set of weights by:
receiving a media exposure event from a panelist from the plurality of panelists with a weight from the set of weights; and
crediting demographics of the panelist for the media exposure event based on the weight.
16. The apparatus of claim 11 , wherein the resultant set of weights is an optimal solution to an equality constraint, the equality constraint being an equation including the constraint matrix, the population matrix, and the set of weights.
17. The apparatus of claim 16 , wherein:
the set of constraints further includes at least one of a non-negative constraint, a bound constraint, and the equality constraint; and
the optimal solution is a non-negative solution with minimum variance.
18. The apparatus of claim 11 , wherein the weight determiner is to determine the inverse of the first matrix of the linear system by:
separating components of the first matrix into a first set of blocks;
inverting the first matrix using blockwise inversion to generate the second matrix;
separating the first element of the second matrix into a second set of blocks; and
inverting the second matrix using blockwise inversion to generate the third matrix, the second element of the third matrix having dimensions larger than the constraint matrix.
19. The apparatus of claim 18 , wherein the weight determiner is to reduce the dimensions of the second element using Sherman-Morrison formula.
20. A method for determining a plurality of weights for a plurality of panelists representative of a population, the method comprising:
storing a constraint matrix and a population matrix into a memory, the constraint matrix representing demographics associated with a plurality of panelists in a population, the population matrix representing second demographics of the population;
determining, by executing an instruction with a processor, a linear system based on a set of constraints including the constraint matrix and the population matrix;
determining, by executing an instruction with the processor, a solution to the linear system by determining an inverse of a first matrix of the linear system, the determination of the inverse including breaking down the first matrix into blocks, dimensions of the blocks being no larger than dimensions of the constraint matrix, the determination of the inverse including:
reducing the dimensions of a second element of a third matrix to a size less than or equal to the dimensions of the constraint matrix, the third matrix being an inversion of a second matrix, the second matrix being an inversion of the first matrix, the reduced second element being a third element;
storing the reduced third matrix in the memory;
replacing, in the stored third matrix, the second element with the third element in the second matrix; and
replacing a first element of the second matrix with the second matrix; and
outputting a resultant set of weights based on the solution, the resultant set of weights satisfying the set of constraints.