US-12625921-B2 - Estimation apparatus, estimation method and estimation program

US12625921B2US 12625921 B2US12625921 B2US 12625921B2US-12625921-B2

Abstract

An estimation apparatus includes a memory; and a processor configured to execute: receiving spatiotemporal population data and a probability of movement between areas as input; constructing a collective graphical model (CGM) in a path graph for estimating a number of people who have moved between areas from the spatiotemporal population data and the probability of movement between areas; generating an instance of a minimum cost flow problem for performing MAP estimation on the constructed CGM; solving the instance of the minimum cost flow problem to estimate the number of people who have moved between areas at individual time steps; and outputting the estimated number of people who have moved between the areas at the individual time steps.

Inventors

Yasunori AKAGI
Yusuke Tanaka
Takeshi Kurashima
Hiroyuki Toda

Assignees

NTT, INC.

Dates

Publication Date: 20260512
Application Date: 20200528

Claims (5)

1 . An estimation apparatus comprising: a memory; and a processor configured to execute: receiving spatiotemporal population data and a probability of movement between areas as input; constructing a collective graphical model (CGM) in a path graph for estimating a number of people who have moved between areas from the spatiotemporal population data and the probability of movement between areas; generating an instance of a minimum cost flow problem for performing maximum a posteriori (MAP) estimation on the constructed CGM; solving the instance of the minimum cost flow problem to estimate the number of people who have moved between areas at individual time steps, wherein the instance of the minimum cost flow is solved by iterating a shortest path search and a flow update until a required amount of flow M is satisfied, wherein solving the instance of the minimum cost flow is based on having a minimum number of sample data; and outputting the estimated number of people who have moved between the areas at the individual time steps.
2 . The estimation apparatus according to claim 1 , wherein the solving solves the instance of the minimum cost flow problem using a shortest path iteration method to estimate the number of people who have moved between areas at the individual time steps.
3 . An estimation method executed by a computer including a memory and a processor, the estimation method comprising: receiving spatiotemporal population data and a probability of movement between areas as input; constructing a collective graphical model (CGM) in a path graph for estimating a number of people who have moved between areas from the spatiotemporal population data and the probability of movement between areas; generating an instance of a minimum cost flow problem for performing maximum a posteriori (MAP) estimation in the constructed CGM; solving the instance of the minimum cost flow problem to estimate the number of people who have moved between areas at individual time steps, wherein the instance of the minimum cost flow is solved by iterating a shortest path search and a flow update until a required amount of flow M is satisfied, wherein solving the instance of the minimum cost flow is based on having a minimum number of sample data; and outputting the estimated number of people who have moved between areas at the individual time steps.
4 . The estimation method according to claim 3 , wherein, in the solving solves the instance of the minimum cost flow problem using a shortest path iteration method to estimate the number of people who have moved between areas at the individual time steps.
5 . A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which when executed, cause a computer to execute an estimation process comprising: receiving spatiotemporal population data and a probability of movement between areas as input; constructing a collective graphical model (CGM) in a path graph for estimating a number of people who have moved between areas from the spatiotemporal population data and the probability of movement between areas; generating an instance of a minimum cost flow problem for performing maximum a posteriori (MAP) estimation in the constructed CGM; solving the instance of the minimum cost flow problem to estimate the number of people who have moved between areas at individual time steps, wherein the instance of the minimum cost flow is solved by iterating a shortest path search and a flow update until a required amount of flow M is satisfied, wherein solving the instance of the minimum cost flow is based on having a minimum number of sample data; and outputting the estimated number of people who have moved between areas at the individual time steps.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is a U.S. National Stage Application filed under 35 U.S.C. § 371 claiming priority to International Patent Application No. PCT/JP2020/021223, filed on 28 May 2020, the disclosure of which is hereby incorporated herein by reference in its entirety. TECHNICAL FIELD The present disclosure relates to an estimation apparatus, an estimation method, and an estimation program. BACKGROUND ART Generally, positional information of individuals obtained from a global positioning system (GPS) or the like is provided as spatiotemporal population data in which individuals cannot be tracked in consideration of privacy. Spatiotemporal population data is data indicating populations of areas at individual time steps where the areas refer to, for example, areas obtained by dividing a geographical space into grid cells. As a technique for estimating the number of people who have moved between areas at individual time steps, based on such spatiotemporal population data, for example, a maximum a posteriori (MAP) estimation technique on a collective graphical model (CGM) in a path graph, has been known. CITATION LIST Non Patent Literature NPL 1: Yasunori Akagi, Takuya Nishimura, Takeshi Kurashima, Hiroyuki Toda, “A Fast and Accurate Method for Estimating People Flow from Spatiotemporal Population Data,” Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), pp. 3293-3300, 2018. NPL 2: D. R. Sheldon and T. G. Dietterich, “Collective Graphical Models,” In Proceedings of the 24th International Conference on Neural Information Processing Systems, pp. 1161-1169, 2011. SUMMARY OF THE INVENTION Technical Problem However, in the case of the above estimation technique, Stirling's approximation is applied to a factorial part of an objective function, and hence, a solution far from a correct solution may be output when the total number of samples is small. This is because Stirling's approximation is not accurate when the total number of samples is small. Further, in the case of the above estimation technique, a feasible region is continuously relaxed (that is, a constraint of taking only integer values is removed) when optimizing the objective function, and hence, a solution of a non-integer value (a non-sparse solution) may be output. Thus, upon estimating the number of people who have moved between areas at individual time steps based on spatiotemporal population data, an estimation method is required that is capable of outputting a more accurate sparse solution in a MAP estimation on a CGM in a path graph. It is an object of the present disclosure to improve the estimation accuracy when estimating the number of people who have moved between areas at individual time steps based on spatiotemporal population data. Means for Solving the Problem According to an aspect of the present disclosure, an estimation apparatus includes an input unit configured to receive spatiotemporal population data and a probability of movement between areas as input, a construction unit configured to construct a CGM in a path graph for estimating a number of people who have moved between areas from the spatiotemporal population data and the probability of movement between areas, a generation unit configured to generate an instance of a minimum cost flow problem for performing MAP estimation in the constructed CGM, an estimation unit configured to solve the instance of the minimum cost flow problem to estimate the number of people who have moved between areas at individual time steps, and an output unit configured to output the estimated number of people who have moved between areas at the individual time steps. Effects of the Invention According to the present disclosure, the estimation accuracy when estimating the number of people who have moved between areas at individual time steps based on spatiotemporal population data can be improved. BRIEF DESCRIPTION OF DRAWINGS FIG. 1 is a first diagram for explaining an overview of MAP estimation on a CGM. FIG. 2 is a second diagram for explaining the overview of MAP estimation on a CGM. FIG. 3 is a third diagram for explaining the overview of MAP estimation on a CGM. FIG. 4 is a diagram for explaining an overview of an instance of a minimum cost flow problem. FIG. 5 is a diagram for explaining a shortest path iteration method used when solving an instance of a minimum cost flow problem. FIG. 6 is a diagram illustrating an example of a hardware configuration of an estimation apparatus. FIG. 7 is a diagram illustrating an example of a functional configuration of the estimation apparatus. FIG. 8 is a diagram showing an example of data stored in storage units. FIG. 9 is a diagram showing an example of generating an instance of a minimum cost flow problem. FIG. 10 is a flowchart showing a flow of a moved people count estimation process. DESCRIPTION OF EMBODIMENTS Hereinafter, embodiments will be described with reference to