Determining probability that an object belongs to a topic using sample items selected from object and probability distribution profile of the topic
View Patent ↗An object potentially belongs to a number of topics. Each topic is characterized by a probability distribution profile of a number of representative items that belong to the topic. Sample items are selected from the object, less than a total number of items of the object. A probability that the object belongs to each topic is determined using the probability distribution profile characterizing each topic and the sample items selected from the object.
1. A method comprising:
receiving a plurality of topics to which an object potentially belongs, each topic characterized by a probability distribution profile of a plurality of representative items that belong to the topic;
selecting, by a processor of a computing device, a plurality of sample items from the object less than a total number of a plurality of items of the object;
determining, by the processor, a probability that the object belongs to each topic using the probability distribution profile characterizing each topic and the sample items selected from the object; and,
outputting at least the topics to which the object belongs with non-zero probability.
2. The method of claim 1 , further comprising:
where an absolute value of a difference between a value of one and a sum of the probabilities is greater than a first threshold, or where at least one of the probabilities has a negative value less than a second threshold,
concluding that the object potentially belongs to a new topic that is not currently part of the plurality of topics that have been received;
adding the new topic to the plurality of topics; and,
determining the probability that the object belongs to each topic, including the new topic.
3. The method of claim 1 , further comprising, after determining the probability that the object belongs to each topic:
where an absolute value of a difference between a value of one and a sum of the probabilities is greater than a first threshold, or where at least one of the probabilities has a negative value less than a second threshold,
increasing a counter, the counter corresponding to a number of times the absolute value is greater than the first threshold or at least one of the probabilities has a negative value less than the second threshold;
where the counter is less than a third threshold,
selecting new sample items from the items of the object to increase the number of the sample items used to determine the probability that the object belongs to each topic;
using the new items to redetermine the probability that the object belongs to each topic;
where the counter is equal to the third threshold,
concluding that the object potentially belongs to a new topic that is not currently part of the plurality of topics that have been received;
adding the new topic to the plurality of topics; and,
determining the probability that the object belongs to each topic, including the new topic.
4. The method of claim 1 , further comprising determining a sample size guaranteeing that the probability that the object belongs to each topic is determined with a desired accuracy,
wherein the sample items selected from the object are equal in number to the sample size.
5. The method of claim 1 , wherein the samples are uniformly and randomly selected from the object.
6. The method of claim 5 , further comprising constructing a sparse vector having a plurality of components, each component of the sparse vector corresponding to a given item, where a value of the component is equal to a frequency of the given item within the samples selected from the object if the given item is found within the samples, and is otherwise equal to zero,
wherein determining the probability that the object belongs to each topic comprises multiplying the sparse vector by a matrix of probabilities to yield a probability vector comprising the probability that the object belongs to each topic.
7. The method of claim 6 , wherein the matrix of probabilities is a first matrix of probabilities,
and wherein determining the probability that the object belongs to each topic comprises determining the first matrix of probabilities by:
constructing a second matrix of probabilities having a plurality of columns corresponding to the probability distribution profiles for the topics, the columns being linearly independent;
constructing a left-inverse of the second matrix of probabilities such that the second matrix of probabilities times the left-inverse of the second matrix of probabilities is equal to an identity matrix; and,
setting the first matrix of probabilities to the left-inverse of the second matrix of probabilities.
8. The method of claim 1 , wherein each of at least one given object of a plurality of given objects is determined as having non-zero probabilities for at least two of the topics.
9. A computing device comprising:
a processor;
a storage device to store data representing an object and data representing a plurality of topics to which the object potentially belongs, each topic characterized by a probability distribution profile of a plurality of representative items that belong to the topic; and,
software code executed by the processor to select a plurality of sample items from the object less than a total number of a plurality of items of the object, and to determine a probability that the object belongs to each topic using the probability distribution profile characterizing each topic and the sample items selected from the object.
10. The computing device of claim 9 , wherein the software code is further to:
where an absolute value of a difference between a value of one and a sum of the probabilities is greater than a first threshold, or where at least one of the probabilities has a negative value less than a second threshold,
conclude that the object potentially belongs to a new topic that is not currently part of the plurality of topics;
add the new topic to the plurality of topics; and,
redetermine the probability that the object belongs to each topic.
11. The computing device of claim 9 , wherein the software code is further to:
where an absolute value of a difference between a value of one and a sum of the probabilities is greater than a first threshold, or where at least one of the probabilities has a negative value less than a second threshold,
increase a counter, the counter corresponding to a number of times the absolute value is greater than the first threshold or at least one of the probabilities has a negative value less than the second threshold;
where the counter is less than a third threshold,
select new sample items from the items of the object to increase the number of the sample items used to determine the probability that the object belongs to each topic;
use the new items to redetermine the probability that the object belongs to each topic;
where the counter is equal to the third threshold,
conclude that the object potentially belongs to a new topic that is not currently part of the plurality of topics that have been received;
add the new topic to the plurality of topics; and,
determine the probability that the object belongs to each topic, including the new topic.
12. The computing device of claim 9 , wherein the software code is further to determine a sample size guaranteeing that the probability that the object belongs to each topic is determined with a desired accuracy,
wherein the sample items selected from the object are equal in number to the sample size.
13. The computing device of claim 9 , wherein the samples are uniformly and randomly selected from the object.
14. The computing device of claim 9 , wherein each of at least one given object of a plurality of given objects is determined as having non-zero probabilities for at least two of the topics.
15. A non-transitory computer-readable medium having computer code stored thereon, wherein execution of the computer code by a processor causes a method to be performed, the method comprising:
receiving a plurality of topics to which an object potentially belongs, each topic characterized by a probability distribution profile of a plurality of representative items that belong to the topic;
selecting, by a processor of the computing device, a plurality of sample items from the object less than a total number of a plurality of items of the object; and,
determining, by the processor, a probability that the object belongs to each topic using the probability distribution profile characterizing each topic and the sample items selected from the object.
16. The non-transitory computer-readable medium of claim 15 , wherein the method further comprises:
where an absolute value of a difference between a value of one and a sum of the probabilities is greater than a first threshold, or where at least one of the probabilities has a negative value less than a second threshold,
increase a counter, the counter corresponding to a number of times the absolute value is greater than the first threshold or at least one of the probabilities has a negative value less than the second threshold;
where the counter is less than a third threshold,
select new sample items from the items of the object to increase the number of the sample items used to determine the probability that the object belongs to each topic;
use the new items to redetermine the probability that the object belongs to each topic;
where the counter is equal to the third threshold,
conclude that the object potentially belongs to a new topic that is not currently part of the plurality of topics that have been received;
add the new topic to the plurality of topics; and,
determine the probability that the object belongs to each topic, including the new topic.
17. The non-transitory computer-readable medium of claim 15 , wherein the method further comprises determining a sample size guaranteeing that the probability that the object belongs to each topic is determined with a desired accuracy,
wherein the sample items selected from the object are equal in number to the sample size.
18. The non-transitory computer-readable medium of claim 15 , wherein the samples are uniformly and randomly selected from the object.
19. The non-transitory computer-readable medium of claim 15 , wherein each of at least one given object of a plurality of given objects is determined as having non-zero probabilities for at least two of the topics.