# US 2021/0279579 A1 · Conversion apparatus, learning apparatus, conversion method, learning 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 2021/0279579 A1
- Document ID: US20210279579A1
- Status: Published application
- Kind: A1
- Application number: 17/258,236
- Filed: 2019-06-27
- Published: 2021-09-09
- Earliest claimed: 2018-07-09
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Mathieu BLONDEL; Mensch ARTHUR
- Web page: https://patentgrep.com/patent/US20210279579A1

## CPC

- G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)}
- G06F 18/29: {Graphical models, e.g. Bayesian networks}
- G06F 40/211: Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]
- G06N 3/045: Combinations of networks
- G06N 3/08: Learning methods
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/09: Supervised learning
- G06N 3/082: modifying the architecture, e.g. adding, deleting or silencing nodes or connections
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A conversion device of the present invention converts input first data X into second data Y using a neural network. The conversion device includes: calculating means for calculating an approximation DPΩ(θ) of a solution of dynamic programming that addresses a problem expressed by a weighted directed acyclic graph G, with use of third data θ obtained by predetermined preprocessing performed on the first data X, and with use of a DPΩ function recursively defined using a maxΩ function in which a strongly-convex regularization function Ω is implemented in a max function; and outputting means for outputting, as the second data Y, at least one of DPΩ(θ) calculated by the calculating means and a gradient ∇DPΩ(θ) of DPΩ(θ).

## Claims

### Claim 1

A conversion device that converts input first data X into second data Y using a neural network, the conversion device comprising:
a processor; and
a memory storing program instructions that cause the processor to calculate an approximation DPΩ(θ) of a solution of dynamic programming that addresses a problem expressed by a weighted directed acyclic graph G, with use of third data θ obtained by predetermined preprocessing performed on the first data X, and with use of a DPΩ function recursively defined using a maxΩ function in which a strongly-convex regularization function Ω is implemented in a max function, and output, as the second data Y, at least one of the calculated approximation DPΩ(θ) and a gradient ∇DPΩ(θ) of the calculated approximation DPΩ(θ).

### Claim 2 (depends on 1)

The conversion device according to claim 1, wherein letting the maxΩ function be defined as
max
Ω
⁢
(
x
)
⁢
=
Δ
⁢
max
q
∈
Δ
D
⁢
〈
q
,
x
〉
-
Ω
⁡
(
q
)
and letting vi(θ) be recursively defined as follows for i=1, . . . , N
v
1
⁡
(
θ
)
⁢
=
Δ
⁢
0
v
i
⁡
(
θ
)
⁢
=
Δ
⁢
max
Ω
j
∈
𝒫
i
⁢
θ
i
,
j
+
v
j
⁡
(
θ
)
Here, Pi represents a set of parent nodes of node i in G
the DPΩ function is defined as DPΩ(θ)=vN(θ).

### Claim 3 (depends on 1)

The conversion device according to claim 1, wherein the strongly-convex regularization function Ω is one of
Ω
⁡
(
q
)
=
-
γ
⁢
H
⁡
(
q
)
⁢
⁢
-
H
⁡
(
q
)
=
∑
i
=
1
D
⁢
q
i
⁢
log
⁢
⁢
q
i
and
Ω
⁡
(
q
)
=
γ
2
⁢

q

2
2
where γ>0.

### Claim 4

A training device that trains a neural network for converting input first data X into second data Y, the training device comprising:
a processor; and
a memory storing program instructions that cause the processor to calculate an approximation DPΩ(θ) of a solution of dynamic programming that addresses a problem expressed by a weighted directed acyclic graph G, with use of third data θ obtained by predetermined preprocessing performed on the first data X, and with use of a DPΩ function recursively defined using a maxΩ function in which a strongly-convex regularization function Ω is implemented in a max function, output, as the second data Y, at least one of the calculated approximation DPΩ(θ) and a gradient ∇DPΩ(θ) of the calculated approximation DPΩ(θ), and update the third data θ based on a derivative of a loss function that uses the output approximation DPΩ(θ) or the output gradient ∇DPΩ(θ) and correct answer data Ytrue for the first data X, the third data θ being a parameter of the neural network.

### Claim 5 (depends on 4)

The training device according to claim 4, wherein if the approximation DPΩ(θ) is output, the loss function is DPΩ(θ)−<Ytrue,θ>, and if the gradient ∇DPΩ(θ) is output, the loss function is divergence Δ(Ytrue,∇DPΩ(θ)).

### Claim 6

A conversion method performed by a computer that converts input first data X into second data Y using a neural network, the conversion method comprising:
calculating an approximation DPΩ(θ) of a solution of dynamic programming that addresses a problem expressed by a weighted directed acyclic graph G, with use of third data θ obtained by predetermined preprocessing performed on the first data X, and with use of a DPΩ function recursively defined using a maxΩ function in which a strongly-convex regularization function Ω is implemented in a max function; and
outputting, as the second data Y, at least one of the calculated approximation DPΩ(θ) and a gradient ∇DPΩ(θ) of the calculated approximation DPΩ(θ).

### Claim 7

(canceled)

### Claim 8 (depends on 1)

A non-transitory computer-readable recording medium having stored therein a program comprising the program instructions for causing a computer to function as the conversion device according to claim 1.
