Information processing apparatus, information processing method, and program

Patent metadata

Field	Value
Publication number	US-9311729-B2
Application number	US-201313845626-A
Country	US
Kind code	B2
Filing date	Mar 18, 2013
Priority date	Mar 28, 2012
Publication date	Apr 12, 2016
Grant date	Apr 12, 2016

Abstract

An information processing apparatus that tests independence among a multiplicity of variables includes an execution section and a determination section. The execution section executes a test for conditional independence between two variables in a graphical model that are at least not independent in the case where a condition variable serving as a condition for independence between the two variables is provided on a path between the two variables. The determination section determines whether or not a V-shaped structure is present on a path between the two variables, the V-shaped structure being a graph structure in which first and second variables that are independent are each not independent of a third variable. The execution section does not execute a test for conditional independence between the two variables in the case where the condition variable is provided only on a path determined to have the V-shaped structure.

First claim

What is claimed is:

1. An information processing apparatus that tests independence among a multiplicity of variables in a data set, comprising:
one or more processors configured to:
execute a test for conditional independence between two variables in a graphical model to be displayed on a display device,
wherein the two variables are at least not independent in a case where a condition variable serving as a condition for independence between the two variables is provided on a path among a plurality of paths between the two variables,
wherein the independence between the two variables is adopted when an index value of the test for conditional independence is greater than a threshold value, wherein the index value is based on a joint probability estimated for the two variables and the condition variable; and
determine whether or not a V-shaped structure is present on one or more paths among the plurality of paths between the two variables,
wherein the V-shaped structure is a graph structure in which first and second variables are independent of each other and not independent of a third variable,
wherein the one or more paths correspond to a number of a set of condition variables which is incremented up to a predetermined number, and
wherein the test for conditional independence between the two variables is not executed in a case where the condition variable is provided on the one or more paths determined to have the V-shaped structure.

2. The information processing apparatus according to claim 1 , wherein the one or more processors are configured not to execute the test for conditional independence between the two variables in a case where the condition variable is the third variable in the V-shaped structure.

3. The information processing apparatus according to claim 1 , wherein the one or more processors are configured to:
execute a test for unconditional independence between the first and second variables before executing the test for conditional independence; and
search for a graph structure in which the first and second variables are unconditionally independent and in which each of the first and second variables are not independent of the third variable, as the V-shaped structure.

4. The information processing apparatus according to claim 1 , wherein the one or more processors are configured to search for a graph structure in which the first and second variables are conditionally independent on condition of a variable other than the third variable and in which each of the first and second variables are not independent of the third variable, as the V-shaped structure.

5. The information processing apparatus according to claim 1 , wherein the one or more processors are configured not to search for the V-shaped structure in a case where the number of the set of the condition variables is incremented to exceed the predetermined number.

6. The information processing apparatus according to claim 1 , wherein the one or more processors are further configured to:
detect a contradiction between directed edges in a plurality of V-shaped structures to change one or more directed edges into undirected edges to resolve the contradiction.

7. The information processing apparatus according to claim 6 , wherein the one or more processors are configured to use an index in a test for independence between the first and second variables in the plurality of V-shaped structures to change the directed edges of the V-shaped structure having the first and second variables which are less dependent, into the undirected edges.

8. The information processing apparatus according to claim 6 , wherein, in a case where a variable X and a variable W are not independent in a first V-shaped structure in which the variable X and a variable Y are not independent of a variable Z, and a second V-shaped structure in which the variable W and the variable Y are not independent of the variable Z, the one or more processors are configured to change a directed edge from the variable X to the variable Z in the first V-shaped structure and a directed edge from the variable W to the variable Z in the second V-shaped structure into the undirected edges.

9. The information processing apparatus according to claim 6 , wherein, in a case where a variable X and a variable W are not independent in a first V-shaped structure in which the variable X and a variable Y are each not independent of a variable Z, and a second V-shaped structure in which the variable W and the variable Y are not independent of the variable Z, the one or more processors are configured to change all the directed edges in the first V-shaped and second V-shaped structures into the undirected edges.

10. The information processing apparatus according to claim 6 , wherein, in a case where a variable X and a variable W are not independent in a first V-shaped structure in which the variable X and a variable Y are not independent of a variable Z, and a second V-shaped structure in which the variable W and the variable Y are not independent of the variable Z, the one or more processors are configured to use an index used in a test for independence between two variables to compare independence between the variable X and the variable Y and independence between the variable W and the variable Y to change directed edges of a V-shaped structure from the plurality of V-shaped structures having two less independent variables into the undirected edges.

11. An information processing method for an information processing apparatus having one or more processors that test independence among a multiplicity of variables in a data set, comprising:
executing a test for conditional independence between two variables in a graphical model to be displayed on a display device,
wherein the two variables are at least not independent in a case where a condition variable serving as a condition for independence between the two variables is provided on a path among a plurality of paths between the two variables,
wherein the independence between the two variables is adopted when an index value of the test for conditional independence is greater than a threshold value, wherein the index value is based on a joint probability estimated for the two variables and the condition variable; and
determining whether or not a V-shaped structure is present on one or more paths among the plurality of paths between the two variables,
wherein the V-shaped structure is a graph structure in which first and second variables are independent of each other and not independent of a third variable,
wherein the one or more paths correspond to a number of a set of condition variables which is incremented up to a predetermined number, and
wherein the test for conditional independence between the two variables is not executed in a case where the condition variable is provided on the one or more paths determined to have the V-shaped structure.

12. A non-transitory computer-readable storage medium having stored thereon, a set of computer-executable instructions executed by one or more processors of an information processing apparatus for causing the one or more processors to execute a process for testing independence among a multiplicity of variables in a data set, the process comprising:
executing a test for conditional independence between two variables in a graphical model to be displayed on a display device, wherein the two variables are at least not independent in a case where a condition variable serving as a condition for independence between the two variables is provided on a path among a plurality of paths between the two variables,
wherein the independence between the two variables is adopted when an index

Assignees

• Sony Corp

Inventors

• Isozaki Takashi

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06F18/24155

  Bayesian classification · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F18/29

  Graphical models, e.g. Bayesian networks · CPC title

• G06N7/005

  Physics · mapped topic