# US 2013/0257873 A1 · Information processing apparatus, information processing method, and program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0257873 A1
- Document ID: US20130257873A1
- Status: Published application
- Kind: A1
- Application number: 13/845,626
- Filed: 2013-03-18
- Published: 2013-10-03
- Earliest claimed: 2012-03-28
- Assignees: Sony Corporation
- Applicants: Sony Corporation
- Inventors: Takashi Isozaki
- Web page: https://patentgrep.com/patent/US20130257873A1

## CPC

- G06T 11/26: Drawing of charts or graphs
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F 18/24155: {Bayesian classification}
- G06F 18/29: {Graphical models, e.g. Bayesian networks}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

An information processing apparatus that tests independence among a multiplicity of variables, comprising:
an execution section that 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; and
a determination section that 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,
wherein 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.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1,
wherein the execution section does not execute a test for conditional independence between the two variables in the case where the condition variable is the third variable in the V-shaped structure.

### Claim 3 (depends on 1)

The information processing apparatus according to claim 1,
wherein the execution section executes a test for unconditional independence between the first and second variables before executing a test for conditional independence, and
the information processing apparatus further includes a V-shaped structure search section that searches for a graph structure in which the first and second variables are unconditionally independent and in which the first and second variables are each not independent of the third variable as the V-shaped structure.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3,
wherein the V-shaped structure search section searches 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 the first and second variables are each not independent of the third variable as the V-shaped structure.

### Claim 5 (depends on 4)

The information processing apparatus according to claim 4,
wherein the V-shaped structure search section does not search for the V-shaped structure in the case where the number of a set of the condition variables is incremented to exceed a predetermined number.

### Claim 6 (depends on 1)

The information processing apparatus according to claim 1,
wherein the determination section determines whether or not the V-shaped structure is present for a number of paths between the two variables, the number of paths corresponding to the number of a set of the condition variables which is incremented, and
the execution section does not execute a test for conditional independence between the two variables in the case where any of the condition variables is provided on any of paths determined to have the V-shaped structure.

### Claim 7 (depends on 1)

The information processing apparatus according to claim 1, further comprising:
a contradiction detection section that detects a contradiction between directed edges in a plurality of the V-shaped structures to change some or all of the directed edges into undirected edges to resolve the contradiction.

### Claim 8 (depends on 7)

The information processing apparatus according to claim 7,
wherein the contradiction detection section uses an index used in a test for independence between the first and second variables in the plurality of V-shaped structures to change directed edges of the V-shaped structure having the first and second variables which are less dependent into undirected edges.

### Claim 9 (depends on 7)

The information processing apparatus according to claim 7,
wherein in the 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 each not independent of the variable Z, the contradiction detection section changes 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 undirected edges.

### Claim 10 (depends on 7)

The information processing apparatus according to claim 7,
wherein in the 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 each not independent of the variable Z, the contradiction detection section changes all the directed edges in the first and second V-shaped structures into undirected edges.

### Claim 11 (depends on 7)

The information processing apparatus according to claim 7,
wherein in the 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 each not independent of the variable Z, the contradiction detection section uses 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 the V-shaped structure having two less independent variables into undirected edges.

### Claim 12

An information processing method for an information processing apparatus that tests independence among a multiplicity of variables, comprising:
executing 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; and
determining 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,
wherein a test for conditional independence between the two variables is not executed in the case where the condition variable is provided only on a path determined to have the V-shaped structure.

### Claim 13

A program that causes a computer to execute a process for testing independence among a multiplicity of variables, the process comprising:
executing 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; and
determining 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,
wherein a test for conditional independence between the two variables is not executed in the case where the condition variable is provided only on a path determined to have the V-shaped structure.
