SYSTEMS AND METHODS ASSOCIATED WITH SEQUENTIAL MULTIPLE HYPOTHESIS TESTING

• US 20170330114A1
• Filed: 05/16/2016
• Published: 11/16/2017
• Est. Priority Date: 05/16/2016
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Ghavamzadeh, Mohammad, Malek, Alan John, Chow, Yinlam, Katariya, Sumeet
• Granted Patent: US 10,586,200 B2
• Time in Patent Office: Days
• CPC Class Codes: G06Q 10/067 Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

Embodiments of the present invention are directed at providing a sequential multiple hypothesis testing system. In one embodiment, feedback is collected for hypothesis tests of a multiple hypothesis tests. Based on the collected feedback, a sequential p-value is calculated for each of the hypothesis tests utilizing a sequential statistic procedure that is designed to compare an alternative case with a base case for a respective hypothesis test. A sequential rejection procedure can then be applied to determine whether any of the hypothesis tests have concluded based on the respective p-value. A result of the determination can then be output to apprise a user of a state of the multiple hypothesis test. This process can then be repeated until a maximum sample size is reached, termination criterion is met, or all tests are concluded. Other embodiments may be described and/or claimed.

Claims

1. One or more computer-readable storage media having instructions stored thereon, which, when executed by one or more processors of a computing device, provide the computing device with a hypothesis testing system to iteratively:

distribute base digital content to a first user, first alternative digital content to a second user, and second alternative digital content to a third user, the base digital content representing a base case of a multiple hypothesis test, the first alternative digital content representing a first alternative case of a first hypothesis test of the multiple hypothesis test and the second alternative digital content representing a second alternative case of a second hypothesis test of the multiple hypothesis test;

monitor interactions of the first user, second user and third user with the base digital content, first alternative digital content, and second alternative digital content, respectively, to collect feedback for the multiple hypothesis test;

based on the collected feedback, determine the first hypothesis test can be concluded utilizing a sequential rejection procedure designed to control a family-wise error rate or a false discovery rate associated with the multiple hypothesis test and the second hypothesis test has yet to conclude utilizing the sequential rejection procedure; and

generate a user interface that is indicative of the determination to inform a user of the hypothesis testing system of a state of the multiple hypothesis test.

2. The one or more computer-readable storage media of claim 1, wherein the hypothesis testing system is further to:

in response to determining that the first hypothesis test has concluded, terminate the distribution and collection of feedback with respect to the first hypothesis test to conserve resources of the hypothesis testing system; and

in response to determining that the second hypothesis test has yet to conclude, continue to iteratively distribute the second alternative digital content to one or more additional users and collect feedback with respect to the second alternative case, and determine whether the second hypothesis test has concluded based on the the sequential rejection procedure until the second hypothesis test is determined to have concluded or a maximum amount of feedback is reached.

3. The one or more computer-readable media of claim 2, wherein the hypothesis testing system is further to:

determine the maximum amount of feedback based on a desired Type-II error constraint for the multiple hypothesis test.

4. The one or more computer-readable storage media of claim 1, wherein the hypothesis testing system is further to:

in response to determining the first hypothesis test can be concluded, and the second hypothesis test has yet to conclude, continue collection of feedback with respect to the first and second hypothesis tests until a stopping rule for the multiple hypothesis test is satisfied.

5. The one or more computer-readable storage media of claim 4, wherein the stopping rule is based on a specified number or percentage of hypothesis tests of the multiple hypothesis test that are determined to have concluded, and wherein the hypothesis testing system is further to, upon the stopping rule being satisfied, declare hypothesis tests that have yet to conclude as inconclusive.

6. The one or more computer-readable storage media of claim 1, wherein to determine the first hypothesis test can be concluded utilizing the sequential rejection procedure and the second hypothesis test has yet to conclude utilizing the sequential rejection procedure comprises:

calculation of;

a first sequential p-value based on a first sequential statistic procedure, the first sequential p-value being in an inverse relationship with the first sequential statistic procedure, the first sequential statistic procedure designed to compare the feedback collected for the first alternative digital content with feedback collected for the base digital content, and

a second sequential p-value based on a second sequential statistic procedure, the second sequential p-value being in an inverse relationship with the second sequential statistic procedure, the second sequential statistic procedure designed to compare the feedback collected for the second alternative digital content with feedback collected for the base digital content, and wherein the sequential rejection procedure utilizes the first sequential p-value to determine he first hypothesis test can be concluded and the second sequential p-value to determine the second hypothesis test has yet to conclude.

7. The one or more computer-readable storage media of claim 6, wherein the first sequential p-value is in an inverse relationship with a first maximum value produced by the first sequential statistic procedure, and the second sequential p-value is in an inverse relationship with a second maximum value produced by the second sequential statistic procedure.

8. The one or more computer-readable media of claim 1, wherein the sequential rejection procedure is a sequential Bonferroni rejection procedure.

9. The one or more computer-readable media of claim 1, wherein the sequential rejection procedure is a sequential Holm rejection procedure.

10. The one or more computer-readable media of claim 1, wherein the sequential rejection procedure is a sequential Hochberg rejection procedure.

11. The one or more computer-readable media of claim 1, wherein the sequential rejection procedure is a sequential Benjamin-Hochberg rejection procedure.

12. The one or more computer-readable media of claim 11, wherein the hypothesis testing system is further to:

apply a corrective factor to the sequential rejection procedure to resolve dependencies between the first hypothesis test and the second hypothesis test.

13. A computer-implemented method for sequentially evaluating a multiple hypothesis test, the method comprising iteratively:

receiving feedback for a first hypothesis test of a plurality of hypothesis tests, each hypothesis test of the plurality of hypothesis tests including a respective base case and a respective alternative case, the respective base case for each of the plurality of hypothesis tests being the same across the plurality of hypothesis tests and the respective alternative case for each of the plurality of hypothesis tests being unique across the plurality of hypothesis tests;

based on the received feedback, calculating a current sequential statistic value for the first hypothesis test utilizing a predefined sequential statistic procedure associated with the first hypothesis test, the predefined sequential statistic procedure designed to compare the respective base case with the respective alternative case of the first hypothesis test;

determining whether the current sequential statistic value is larger than previously calculated sequential statistic values for the first hypothesis test;

in response to determining the current sequential statistic value is larger than the previously calculated sequential statistic values, updating a sequential p-value utilizing the current sequential statistic value, the sequential p-value having an inverse relationship with the current sequential statistic; and

determining whether the first hypothesis test has concluded, utilizing a sequential rejection procedure in conjunction with the updated sequential p-value.

14. The computer-implemented method of claim 13, wherein updating the sequential p-value utilizing the current sequential statistic value is based on the equation:

15. The computer-implemented method of claim 13, wherein the sequential rejection procedure is designed to control the family-wise error rate (FWER) of the multiple hypothesis test.

16. The computer-implemented method of claim 13, wherein the sequential rejection procedure is designed to control the false discovery rate (FDR) of the multiple hypothesis test.

17. The computer-implemented method of claim 13, wherein the sequential rejection procedure is:

a sequential Bonferroni rejection procedure;

a sequential Holm rejection procedure;

a sequential Hochberg rejection procedure;

or

a sequential Benjamin-Hochberg rejection procedure.

18. A computing system to sequentially evaluate a multiple hypothesis test, the computing system comprising:

one or more processors; and

one or more computer readable storage media, coupled with the one or more processors, having instructions stored thereon, which, when executed by the one or more processors cause the computing system to iteratively;

distribute to user computing devices, in response to requests from the user computing devices, digital content for each hypothesis test of an active set of hypothesis tests of the multiple hypothesis test;

collect feedback for each hypothesis test of the active set of hypothesis tests, wherein the feedback is indicative of user interactions with the distributed digital content;

based on the feedback, calculate a sequential p-value for each hypothesis test, of the active set of hypothesis tests;

automatically determine a subset of hypothesis tests, of the set of active hypothesis tests, that have concluded utilizing a sequential rejection procedure in conjunction with the respective sequential p-value for each hypothesis test of the subset of hypothesis tests;

remove the subset of hypothesis tests from the active set of hypothesis tests to terminate the collection of feedback for the subset of hypothesis tests to conserve resources of the computing system; and

output a notification to a user of the computing system to indicate that the subset of hypothesis tests have concluded.

19. The computing system of claim 18, wherein to update the sequential p-value utilizing the current sequential statistic value is based on the equation:

20. The computing system of claim 19, wherein the sequential rejection procedure is:

a sequential Bonferroni rejection procedure;

a sequential Holm rejection procedure;

a sequential Hochberg rejection procedure;

or

a sequential Benjamin-Hochberg rejection procedure.