OptimalMassTransport-Signalprocessingandmachinelearningapplications.pdf资源-CSDN文库

需积分: 9 117 浏览量 2021-08-07 18:04:50 上传评论收藏 1.23MB PDF 举报

在理解文件内容后，我们可以提取以下知识点： 1. 最优质量传输（Optimal Mass Transport，OMT）原理与应用：最优质量传输是指在一定条件下，将物体从一种分布转换到另一种分布所需的最小成本。在信号处理和机器学习领域，这种原理有助于分析和处理信号强度和其他数据分布，被广泛应用于内容检索、癌症检测、图像超分辨率及统计机器学习等多个领域。OMT因其能够整合空间和强度信息，给数据分布提供了不同的几何解释，而受到关注。 2. 地球移动者距离（Earth Mover’s Distance，EMD）：在工程相关领域中，OMT也被称为地球移动者距离。这是一种度量两个概率分布之间的差异的方法，它模拟了将一个分布中的“土堆”运输到另一个分布所需的最小工作量，从而实现了对不同分布之间差异的评估。 3. 信号处理中的应用：OMT技术被用于信号处理中的多个方面，如提高模式识别的准确性。例如，在医学图像分析中，使用OMT技术可以有效区分良性和恶性肿瘤；在解决逆问题时，它可以帮助学习模型（如字典学习）；在内容检索中，OMT方法可以用于提高检索准确率等。 4. 机器学习中的应用：OMT在机器学习中的应用也非常重要，它可以用于学习数据表示，包括图像、声音和指纹等。OMT提供了一种从数据中提取信息的方法，并有助于解释数据分布的含义，使得机器学习算法能够更准确地理解数据。 5. 算法的几何特征：OMT方法的几何特征启发了新的算法设计，这些算法用于解释数据分布的意义。例如，OMT的几何特性可以用于定义新的距离度量，或者在特征空间中找到更有效的数据表示。 6. 数值实现：OMT不仅理论上有意义，也有实际的数值实现方式。文件提到了伴随教程的软件，这表明OMT方法已经足够成熟，以至于可以实现为算法，并在实际问题中得到应用。 7. 研究目标与动机：文件的介绍部分强调了在科学和技术领域中有效建模和从信号图像数据中提取信息的重要性。OMT技术因其独特的能力而在多种应用中取得了最先进的结果。通过文件内容，我们可以了解到OMT原理在现代信号处理和机器学习领域中的重要性，以及它的应用如何促进了这些领域的发展。文件还强调了理论研究与实际应用的结合，这表明OMT技术已经从理论研究走向了实用，为技术应用带来了突破性的进展。

资源推荐

资源详情

资源评论

Optimal Mass Transport: Signal processing and machine-

learning applications

Soheil Kolouri, Serim Park, Matthew Thorpe, Dejan Slepčev, and Gustavo K. Rohde

Abstract

Transport-based techniques for signal and data analysis have received increased attention recently.

Given their ability to provide accurate generative models for signal intensities and other data

distributions, they have been used in a variety of applications including content-based retrieval,

cancer detection, image super-resolution, and statistical machine learning, to name a few, and

shown to produce state of the art results in several applications. Moreover, the geometric

characteristics of transport-related metrics have inspired new kinds of algorithms for interpreting

the meaning of data distributions. Here we provide a practical overview of the mathematical

underpinnings of mass transport-related methods, including numerical implementation, as well as

a review, with demonstrations, of several applications. Software accompanying this tutorial is

available at [43].

I. Introduction

A. Motivation and goals

Numerous applications in science and technology depend on effective modeling and

information extraction from signal and image data. Examples include being able to

distinguish between benign and malignant tumors from medical images, learning models

(e.g. dictionaries) for solving inverse problems, identifying people from images of faces,

voice profiles, or fingerprints, and many others. Techniques based on the mathematics of

optimal mass transport, also known as Earth Mover’s distance in engineering-related fields,

have received significant attention recently given their ability to incorporate spatial (in

addition to intensity) information when comparing signals, images, and other data sources,

thus giving rise to different geometric interpretations of data distributions. These techniques

have been used to simplify and augment the accuracy of numerous pattern recognition-

related problems. Some examples covered in this tutorial include image retrieval [32, 44],

signal and image representation [25, 27, 40, 50], inverse problems [30], cancer detection [4,

39], texture and color modeling [18, 41], shape and image registration [22, 29], and machine

learning [12, 17, 19, 28, 36, 42], to name a few. This tutorial is meant to serve as an

introductory guide to those wishing to familiarize themselves with these emerging

techniques. Specifically we

•

provide a brief overview of key mathematical concepts related to optimal mass

transport

•

describe recent advances in transport related methodology and theory

HHS Public Access

Author manuscript

IEEE Signal Process Mag

. Author manuscript; available in PMC 2018 June 29.

Published in final edited form as:

IEEE Signal Process Mag

. 2017 July ; 34(4): 43–59. doi:10.1109/MSP.2017.2695801.

Author Manuscript Author Manuscript Author Manuscript Author Manuscript

•

provide a practical overview of their applications in modern signal analysis,

modeling, and learning problems.

Software accompanying this tutorial is available at [43].

B. Why transport?

In recent years numerous techniques for signal and image analysis have been developed to

address important learning and estimation problems. Researchers working to find solutions

to these problems have found it necessary to develop techniques to compare signal

intensities across different signal/image coordinates. A common problem in medical

imaging, for example, is the analysis of magnetic resonance images with the goal of learning

brain morphology differences between healthy and diseased populations. Decades of

research in this area have culminated with techniques such as voxel and deformation-based

morphology which make use of nonlinear registration methods to understand differences in

tissue density and locations. Likewise, the development of dynamic time warping techniques

was necessary to enable the comparison of time series data more meaningfully, without

confounds from commonly encountered variations in time. Finally, researchers desiring to

create realistic models of facial appearance have long understood that appearance models for

eyes, lips, nose, etc. are significantly different and must thus be dependent on position

relative to a fixed anatomy. The pervasive success of these, as well as other techniques such

as optical flow, level-set methods, deep neural networks, for example, have thus taught us

that 1) nonlinearity and 2) modeling the location of pixel intensities are essential concepts to

keep in mind when solving modern regression problems related to estimation and

classification.

The methodology mentioned above for modeling appearance and learning morphology, time

series analysis and predictive modeling, deep neural networks for classification of sensor

data, etc., is algorithmic in nature. The transport-related techniques reviewed below are

nonlinear methods that, unlike linear methods such as Fourier, wavelets, and dictionary

models, for example, explicitly model jointly signal intensities as well as their locations.

Furthermore, they are often based on the theory of optimal mass transport from which

fundamental principles can be put to use. Thus they hold the promise to ultimately play a

significant role in the development of a theoretical foundation for certain subclasses of

modern learning and estimation problems.

C. Overview and outline

As detailed below in section II, the optimal mass transport problem first arose due to Monge

[35]. It was later expanded by Kantorovich [23] and found applications in operations

research and economics. Section III provides an overview of the mathematical principles and

formulation of optimal transport-related metrics, their geometric interpretation, and related

embedding methods and signal transforms. We also explain Brenier’s theorem [9], which

helped pave the way for several practical numerical implementation algorithms, which are

then explained in detail in section IV. Finally, in section V we review and demonstrate the

application of transport-based techniques to numerous problems including: image retrieval,

registration and morphing, color and texture analysis, image denoising and restoration,

Kolouri et al.

Page 2

IEEE Signal Process Mag

. Author manuscript; available in PMC 2018 June 29.

Author Manuscript Author Manuscript Author Manuscript Author Manuscript

morphometry, super resolution, and machine learning. As mentioned above, software

implementing the examples shown can be downloaded from [43].

II. A brief historical note

The optimal mass transport problem seeks the most efficient way of transforming one

distribution of mass to another, relative to a given cost function. The problem was initially

studied by the French mathematician Gaspard Monge in his seminal work “Mémoire sur la

théorie des déblais et des remblais” [35] in 1781. In 1942, Leonid V. Kantorovich, who at

that time was unaware of Monge’s work, proposed a general formulation of the problem by

considering optimal mass transport plans, which as opposed to Monge’s formulation allows

for mass splitting [23]. Kantorovich shared the 1975 Nobel Prize in Economic Sciences with

Tjalling Koopmans for his work in the optimal allocation of scarce resources. Kantorovich’s

contribution is considered as “the birth of the modern formulation of optimal transport” [49]

and it made the optimal mass transport problem an active field of research in the following

years.

A significant portion of the theory of the optimal mass transport problem was developed in

the Nineties. Starting with Brenier’s seminal work on characterization, existence, and

uniqueness of optimal transport maps [9], followed by Caffarelli’s work on regularity

conditions of such mappings [10] and Gangbo and McCann’s work on geometric

interpretation of the problem [20].

A more thorough history and background on the optimal mass transport problem can be

found in Villani’s book “Optimal Transport: Old and New” [49] and Santambrogio’s book

“Optimal transport for applied mathematicians” [45].

The significant contributions in mathematical foundations of the optimal transport problem

together with recent advancements in numerical methods [6, 14, 31, 37] have spurred the

recent development of numerous data analysis techniques for modern estimation and

detection (e.g. classification) problems.

III. Formulation of the problem and methodology

In this section we first review both the continuous and ‘discrete’ formulations of the optimal

transport problem (i.e. Monge’s and Kantorovich’s formulations). Next, we review the

geometrical characteristics of the problem, and finally review the transport based signal/

image embeddings. In the sections below we’ve elected to avoid measure-theoretic notation,

and other detailed mathematical language, in lieu of a more informal and intuitive

description of the problem. It is important to know, however, that certain mathematical

precision is required to best understand the differences between Monge’s and Kantorivich’s

formulation, their geometric interpretations, and so on. The interested reader may find useful

to consult [24] for a more complete and mathematical description of the concepts explained

below.

Kolouri et al.

Page 3

IEEE Signal Process Mag

. Author manuscript; available in PMC 2018 June 29.

Author Manuscript Author Manuscript Author Manuscript Author Manuscript

A. Optimal Transport: Formulation

Over the past century or so, the theory of optimal transport (earth mover’s distance) has

developed two main formulations, one utilizing a continuous map (Monge’s formulation)

and one utilizing what is called a transport plan (Kantarovich’s formulation) for assigning

the spatial correspondence necessary for the related transport problem. While Monge’s

continuous formulation is helpful in problems where a point-to-point assignment is desired,

Kantarovich’s formulation is more general, and also covers the case of discrete (Dirac)

masses (in our case signal intensities). These differ not only in mathematical formulation,

but also has consequences with regards to their respective numerical solutions, as well as

applications.

1) Monge’s continuous formulation—The Monge optimal mass transportation

problem is formulated as follows. Consider two signals or images

and

defined over

their respective domains Ω

and Ω

. Here Ω

and Ω

are typically subsets of ℝ

, and often

can be taken as the unit square (or cube in 3D). While a detailed measure-theoretic

formulation is typically required (see [24]) we bypass rigorous formulation here and simply

assume that

(

) and

(y) correspond to signal intensities at positions

∈ Ω

and

∈ Ω

For digital signals, an interpolating model can be used to construct these functions defined

over continuous domains from sampled discrete data. Except for extensions which are

described below, the signals are required to be nonnegative. That is,

(

) ≥ 0 ∀

∈ Ω

and

(

) ≥ 0 ∀

∈ Ω

. In addition, the total amount of signal (or mass) for both signals should

be equal to the same constant (which is generally chosen to be 1):

∫

x dx =

∫

y dy = 1

. In other words,

and

are assumed to be probability density

functions (PDFs).

Monge’s optimal transportation problem is to find a function

: Ω

→ Ω

that ‘pushes’

onto

and minimizes the following objective function,

, I

= inf

f ∈ MP

∫

c x, f x I

x dx (1)

where

: Ω

× Ω

→ ℝ

is the cost of moving pixel intensity

(

) from

(

) (Monge

considered the Euclidean distance as the cost function in his original formulation,

(

))

= |

−

(

)|), and

stands for a measure preserving map that moves all the signal intensity

from

. That is, for a subset

⊂ Ω

the MP requirement is that

∫

x: f x ∈ B

x dx =

∫

y dy . (2)

is one-to-one this just means that for

⊂ Ω

Kolouri et al.

Page 4

IEEE Signal Process Mag

. Author manuscript; available in PMC 2018 June 29.

Author Manuscript Author Manuscript Author Manuscript Author Manuscript

∫

x dx =

∫

f A

y dy .

Such maps

∈

are sometimes called ‘transport maps’ or ‘mass preserving maps’.

Simply put, the Monge formulation of the problem seeks to rearrange signal

into signal

while minimizing a specific cost function. In cases when

is smooth and one to one, then the

requirement (2) can be written in a differential form as

det D f x I

f x = I

x (3)

almost everywhere, where

D f

is the Jacobian of

(see Figure 1, top panel). Note that both

the objective function and the constraint in Equation (1) are nonlinear with respect to

(

Hence, for over a century the answers to questions regarding existence and characterization

of the Monge’s problem remained unknown.

It should be mentioned that, for certain measures the Monge’s formulation of the optimal

transport problem is ill-posed; in the sense that there is no transport map to rearrange one

PDF to another. For instance, consider the case where

is a Dirac mass while

is not.

Kantorovich’s formulation alleviates this problem by finding the optimal transport plan as

opposed to the transport map.

2) Kantorovich’s formulation—Kantorovich formulated the transportation problem by

optimizing over transportation plans, which we denote as

. One can think of

as the joint

distribution of

and

describing how much ‘mass’ is being moved to different

coordinates. That is let

be a subset of Ω

and similarly

⊆ Ω

. For notational simplicity

we will not make a distinction between a probability distribution and its density. More

precisely to a signal

we associate a probability distribution by

(

) =∫

(

)

The quantity

(

) tells us how much ‘mass’ in set

is being moved to set

. Here the

MP constraint can be expressed as

(Ω

) =

(

), and

(

×Ω

) =

(

). Kantorovich’s

formulation for the optimal transport problem can then be written as,

, I

= min

γ ∈ MP

∫

× Ω

c x, y dγ x, y . (4)

Note that the measure theoretic notation above (the integration over

dγ

(

x, y

) above) is meant

to represent the fact that this integral is more general than the routine Riemman-type integral

commonly used in signal processing, and can cover ‘integration’ over domains which are

more general. The minimizer of the optimization problem above,

∗

, is called the optimal

transport plan. Note that unlike the Monge problem, in Kantorovich’s formulation the

objective function and the constraints are linear with respect to

(

x, y

). Moreover,

Kantorovich’s formulation is in the form of a convex optimization problem. We also note

that the Monge problem is more restrictive than the Kantorovich problem. That is, in

Kolouri et al.

Page 5

IEEE Signal Process Mag

. Author manuscript; available in PMC 2018 June 29.

Author Manuscript Author Manuscript Author Manuscript Author Manuscript

剩余38页未读，继续阅读

评论收藏

内容反馈

TracelessLe

粉丝: 5w+
资源: 466

Optimal Mass Transport - Signal processing and machinelearning a...

最新资源

Optimal Mass Transport - Signal processing and machinelearning a...

英文版的电子书：信号处理和机器学习与应用.pdf

signal processing

optimum signal processing

Signalprocessing

Advances in Machine Learning and Signal Processing

Optimal Control Theory - An Introduction.(Kirk D. Dover, 2004)

Optimal-Scheduling-for-Charging-and-Discharging-of-Electric-Vehicles-master.zip

Machine Learning - Tom Mitchell

Optimal Control Theory - An Introduction.(Kirk D. Dover, 2004

Discrete-Time Signal Processing, 3rd

Digital signal processing principles, algorithms, and applicati

machine learning.pdf

signal:学习信号处理

Modern Signal Processing

Machine Learning.pdf

control-optimal-approche--HUM.rar_hum_optimal control

Optimal-Trajectory-generation-for-Lane-Changing-in-Frenet-Frame-master.zip

Machine Learning with PySpark

Pattern Recognition and Machine Learning (Bishop)

digital signal processing

MASS transfer

Optimal Tip-To-Tip Efficiency(弟高值d2f算法).pdf

Signal Processing: Image Communication

Statistical Reinforcement Learning - Modern Machine Learning Approaches

SQL Server 2014 Development Essentials - Masood-Al-Farooq, Basit A. [SRG].pdf

最新资源