第五届国际逼近算法会议论文集

4星 · 超过85%的资源需积分: 3 15 浏览量更新于2024-07-31 收藏 12.1MB PDF 举报

"Algorithms for Approximation - 这是一份关于算法在近似计算中的应用的会议论文集，涵盖了多个主题，包括成像与数据挖掘、数值模拟、统计近似方法、数据拟合与建模、微分和积分方程以及特殊函数与流形上的近似。" 这篇论文集详细探讨了在不同领域的近似算法，以下是各部分的主要内容概要： **Part I. Imaging and Data Mining** 这部分重点关注图像处理和数据挖掘中的算法。可能涵盖了图像分析、特征提取、模式识别以及如何利用近似算法有效地处理大量数据。这些技术对于理解和解释复杂的数据集至关重要，特别是在计算机视觉和机器学习领域。 **Part II. Numerical Simulation** 数值模拟是科学计算的核心部分，这部分可能讨论了如何使用近似算法解决复杂的数学问题，如偏微分方程。这些算法可能包括有限差分、有限元方法或蒙特卡洛模拟等，它们在工程、物理和环境科学中有着广泛应用。 **Part III. Statistical Approximation Methods** 统计近似方法主要涉及如何通过概率和统计手段进行数据建模。内容可能涵盖贝叶斯推理、最大似然估计、非参数统计和随机过程的近似。这些方法在数据分析、预测和决策制定中起着关键作用。 **Part IV. Data Fitting and Modelling** 数据拟合和建模通常涉及找到最佳的函数或模型来描述观测数据。这部分可能讨论了多项式拟合、样条函数、最小二乘法以及非线性回归等技术，这些工具广泛用于实验科学和工程设计。 **Part V. Differential and Integral Equations** 微分和积分方程在描述自然现象时起着核心作用。这部分可能介绍了使用近似算法求解这类方程的方法，如格林函数、幂级数展开或数值积分技术，这些对于物理、化学和生物系统的建模极其重要。 **Part VI. Special Functions and Approximation on Manifolds** 这部分可能深入到特殊函数（如贝塞尔函数、勒让德多级数）和流形上的近似。特殊函数在数学和物理学中有许多应用，而流形上的近似则涉及到高维空间的几何和拓扑问题。这份论文集提供了关于近似算法的广泛视角，覆盖了从基础理论到实际应用的多个层面，对于科研工作者和工程技术人员来说，是一份宝贵的参考资料。每一部分都可能包含最新的研究成果和创新性的方法，旨在提高我们理解和处理复杂问题的能力。

Ranking as Function Approximation 5

imagine that a psychologist has devised an aptitude test

. Mathematician A

is considered stronger than mathematician B if, given three particular theo-

rems, A can prove at least two theorems faster than B. The psychologist ﬁnds

the measurements shown in Table 1.

Minutes Per Proof

Mathematician Theorem 1 Theorem 2 Theorem 3

Archimedes 8 1 6

Bryson 3 5 7

Callippus 4 9 2

Table 1. Archimedes is stronger than Bryson; Bryson is stronger than Callippus;

but Callippus is stronger than Archimedes.

2 Measures of Ranking Quality

In the information retrieval literature, there are many methods used to mea-

sure the quality of ranking results. Here we brieﬂy describe four. We observe

that there are two properties that are shared by all of these cost functions:

none are diﬀerentiable, and all are multivariate, in the sense that they depend

on the scores of multiple documents. The non-diﬀerentiability presents par-

ticular challenges to the machine learning approach, where cost functions are

almost always assumed to be smooth. Recently, some progress has been made

tackling the latter property using supp ort vector methods [19]; below, we will

outline an alternative approach.

Pair-wise Error

The pair-wise error counts the number of pairs that are in the incorrect order,

as a fraction of the maximum possible number of such pairs.

Normalized Discounted Cumulative Gain (NDCG)

The normalized discounted cumulative gain measure [17] is a cumulative mea-

sure of ranking quality (so a suitable cost would b e 1-NDCG). For a given

query Q

the NDCG is computed as

≡ N

j=1

r(j)

− 1)/ log(1 + j)

Of course this “magic-square” example is not serious, although it illustrates the

p erils of one-dimensional thinking.

Ranking as Function Approximation 7

To solve the ranking problem we solve the following QP:

min

w,ξ

(

kwk

+ C

)

subject to:

w · (x

(1)

− x

(2)

) > 1 − ξ

∈ R

In the separable case, by minimizing kwk, we are maximizing the gap, pro-

jected along w , between items that are to be ranked diﬀerently; the slack

variables ξ

allow for non-separable data, and their sum gives a bound on the

number of errors. This is similar to the original formulation of Support Vector

Machines for classiﬁcation [10, 5], and enjoys the same advantages: the algo-

rithm can be implicitly mapped to a feature space using the kernel trick (see,

for example, [22]), which gives the model a great deal of expressive freedom,

and uniform bounds on generalization performance can be given [13].

4 Perceptron Ranking

[9] prop ose a ranker based on the Perceptron (

’

PRank’), which maps a feature

vector x ∈ R

to the reals with a learned vector w ∈ R

and increasing

thresholds

= 1, ··· , N such that the output of the mapping function is

just w · x, and such that the declared rank of x is min

{w · x − b

< 0}. An

alternative way to view this is that the rank of x is deﬁned by the bin into

which w · x falls. The learning step is modeled after the Perceptron update

rule (see [9] for details): a newly presented example x results in a change in

w (and in the b

) only if it falls in the wrong bin, given the current values

of w and the b

. If this occurs, w is updated by a quantity proportional to

x, and those thresholds whose movement could result in x being correctly

ranked are also updated. The linear form of PRank is an online algorithm

, in

that it learns (that is, it updates the vector w, and the thresholds that deﬁne

the rank boundaries) using one example at a time. However, PRank can be,

and has been, compared to batch ranking algorithms, and a quadratic kernel

version was found to outperform all such algorithms described in [13]. [12] has

proposed a simple but very eﬀective extension of PRank, which approximates

ﬁnding the Bayes point (that point which would give the minimum achievable

generalization error) by averaging over PRank models.

Actually the last threshold is pegged at inﬁnity.

The general kernel version is not, since the support vectors must be saved.

8 C.J.C. Burges

5 Neural Network Ranking

In this Section we describe a recent neural net based ranking algorithm that is

currently used in one of the major commercial search engines [3]. Let’s begin

by deﬁning a suitable cost.

5.1 A Probabilistic Cost

As we have observed, most machine learning algorithms require diﬀerentiable

cost functions, and neural networks fall in this class. To this end, in [3] the

following probabilistic model was proposed for modeling posteriors, where

each training pair {A, B} has associated posterior P(A⊲B). The probabilistic

model is an important feature of the approach, since ranking algorithms often

model preferences, and the ascription of preferences is a much more subjective

process than the ascription of, say, classes. (Target probabilities could be

measured, for example, by measuring multiple human preferences for each

pair.) We consider models where the learning algorithm is given a set of pairs

of samples [A, B] in R

, together with target probabilities

that sample

A is to be ranked higher than sample B. As described above, this is a general

formulation, in that the pairs of ranks need not be complete (in that taken

together, they need not specify a complete ranking of the training data), or

even consistent. We again consider models A : R

7→ R such that the rank

order of a set of test samples is speciﬁed by the real values that A takes,

speciﬁcally, A(x

) > A(x

) is taken to mean that the model asserts that

⊲ x

Denote the modeled posterior P (x

⊲ x

) by P

, i, j = 1, . . . , m, and let

be the desired target values for those posteriors. The cost function is

a function of the diﬀerence of the system’s outputs for each member of a

pair of examples, which encapsulates the observation that for any given pair,

an arbitrary oﬀset can be added to the outputs without changing the ﬁnal

ranking. Deﬁne o

≡ A(x

) and o

≡ A(x

) − A(x

). The cost is a cross

entropy cost function

≡ C(o

) = −

log P

− (1 −

) log (1 − P

)

where the map from outputs to probabilities are modeled using a logistic

function

≡

1 + e

−o

The cross entropy cost has been shown to result in neural net outputs that

model probabilities [6]. C

then becomes

= −

+ log(1 + e

) (1)

Note that C

asymptotes to a linear function; for problems with noisy labels

this is likely to be more robust than a quadratic cost. Also, when

剩余386页未读，继续阅读

hyl20012

粉丝: 5
资源: 9

第五届国际逼近算法会议论文集

Algorithms for Approximation - 2007.pdf

approximation algorithms for np-hard problems.pdf 近似算法关于np问题

Outer approximation algorithms for separable nonconvex

Approximation algorithms for the team orienteering problem

Approximation algorithms for the scaffolding problem and its generalization

approximation algorithms

论文研究-Approximation Algorithms for K-Modes Clustering.pdf

Approximation and Parameterized Runtime Analysis of Evolutionary Algorithms for the Maximum Cut Problem

具有下限约束的$k$-中值近似算法_Approximation algorithms for $k$-median with l

Approximation.Algorithms.for.NP-Hard.Problems

最新资源