近似技术范文

近似技术范文（精选7篇）

近似技术 第1篇

TD-SCDMA系统是一个时域和帧控的TDMA系统, 特殊的帧结构有利于联合检测实现的高效性。根据联合检测信号模型, 可把联合检测转化为一个求最小二乘解的问题, 为了尽可能地降低复杂度, 又不削弱联合检测的性能, 充分利用系统矩阵特殊的结构即块Teoplitz结构, 文献[2][3][4]分别提出了近似的Levinson算法、Schur算法及Cholesky算法。由于TD-SCDMA系统所用的扩频码按照扩频因子周期性地重复, 且信道冲激响应在一个时隙内近似认为时不变, 所以系统矩阵还具有块Sylvester结构。利用此结构, 文献[5][6]提出了一种Block-Fourier算法, 将原来的块Sylvester结构的系统矩阵扩展成块循环矩阵, 这样就可以通过FFT有效地将联合检测问题转换到频域, 由于卷积计算在频域比在时域容易得多, 从而计算复杂度进一步降低。

已有的联合检测算法主要针对系统矩阵的特殊结构进行算法的简化。不管对系统矩阵如何变换, 计算复杂度仍是联合检测的主要问题。为了达到不削弱系统性能的同时又降低计算复杂度的目的, 本文提出了基于ε近似算法[7,8]的联合检测。

1 TD-SCDMA系统的联合检测信号模型

结合TD-SCDMA系统的上行链路构造联合检测的MIMO系统模型, 考虑具有K个用户的同步基带TD-SCDMA上行链路系统, 接收信号表示为:

其中:y (k) (t) 、A (k) 、di (k) 和qc (k) 分别为第K个用户的接收信号、信号幅度、符号序列和扩频码序列, v (t) 是加性高斯白噪声, Ts、Tc和Q分别为符号周期、码片周期和扩频因子, di (k) ∈{±1±j}为用户发送的信息符号, 且它们的实部和虚部是以相等的概率取±1的统计独立的随机变量。

其中:g (k) (t) 为第K个用户的复信道冲激响应, 为码片波形, W是以符号为周期的信道的阶数。

对第K个用户的接收信号y (k) (t) 以码片速率进行抽样, 可得到第k个用户的第l个符号第n个码片的离散值

其中:hn (k) (i) 表示第k个用户第i个符号第n个码片的合成信道冲激响应值, 表示如下:

第l个符号第n个码片的抽样值rn (l) ) 。

经过上述的推导, 我们得出了TD-SCDMA系统上行链路的MIMO联合检测信号模型, 表达式如下:

其中:

2 联合检测问题转为二次规划问题

为了从接收信号r (l) 中检测出第k个用户的发送信号d (k) (l) , 可通过解下列优化问题来得到[9]:

要求解式 (7) 的优化问题, 理论上需要接收序列和计算均衡器系数但在实际求解过程中, 通常根据均衡器的阶数L和用有限求和代替无限求和这两个近似来求解该问题。这样式 (7) 可转化为:

定义如下等式:

其中:

是数据以符号速率抽样的参考时刻, Ns是抽样的符号个数。

根据上述的定义, 那么式 (8) 的优化问题可写为:

所谓的联合检测就是从接收信号中恢复出用户发送的信号。而该系统的联合检测器是由均衡器和解调器D组成的, 待检测的第k个用户的信号可表示为:

在TD-SCDMA系统中, 我们采用的是QPSK数据调制, 即输入是QPSK复数据符号, 所以无线信道也该采用复值信道。针对这种情况, 我们采用实部、虚部分离的方法来表示复数,

则优化问题式 (9) 转化为:

其中:,

这样, 我们就把联合检测问题转化为一个二次规划问题。

3 寻找约束条件

为了从上述二次规划问题中检测出某一个用户的信号, 关键在于寻找合适的约束条件。在基站接收端, 用户的扩频码是已知的, 且用户的信道冲激响应可根据训练序列估计出来, 因此, 每个用户的合并信道冲激响应是已知的。不失一般性, 我们以第1个用户的信号为例来寻找其二次规划的约束条件。

经过推导, 可求得限制条件为:

这样, 把限制条件式 (11) 加到二次规划问题式 (10) 中, 就得到带约束条件的二次规划问题:

其中:

通过式 (12) 的求解, 我们可恢复出第一个用户的信号。而对于该式的求解, 本文利用近几年提出的一种有效的优化算法来求解, 即采用ε近似算法来求上述带约束条件的二次规划问题的ε近似解。

4 性能仿真与分析

联合检测算法性能的仿真主要包括QPSK调制、扩频、加扰、形成突发并进行脉冲成型、通过无线多径瑞利衰落信道、信道估计、联合联测、解调和计算误码频率几个过程。其中无线多径瑞利衰落信道的仿真是基于中国电信科学技术研究院和德国西门子公司联合提出了TD-SCDMA系统的多径传播模型[10], 采用改进的谐波叠加方法来仿真。

结合TD-SCDMA系统的一个时隙的一个数据块, 对本文的仿真环境做如下假定:

选择单根天线;采用低代价信道估计方法[11]且估计信道窗长为16;所有用户的扩频因子都相等;载波频率为2GHz;码片速率为1.28 Mchip/s;信道间隔为1.6 MHz;数据调制为QPSK调制;扩频因子为16;扩频码为OVSF码;每个用户发送的符号数为22。

本文主要从计算复杂度和误码率两方面对快速傅立叶变换联合检测算法和基于ε近似算法的联合检测算法进行比较。

文献[12]给出了快速傅立叶变换算法的计算量为

其中:

而在ε近似算法中, 其复乘计算量表示为:

上面两式中满足Qw=W, 这是由于在ε近似算法中, 信道的长度是以符号为周期的。

从上述公式可知:在快速傅立叶变换算法中, 计算复杂度与用户数K成三次方关系, 而本文算法的计算量与用户数K的平方呈比例关系。

从图1, 图2可看出:当用户数较小时, 本文算法比快速傅立叶变换算法的性能要好, 但随着用户数的增大, 两种算法的性能很接近, 但从计算复杂度方面来考虑, 本文算法的复乘计算量明显比快速傅立叶变换算法减少。

由此可见, 本文提出的基于ε似算法的联合检测技术具有较强的抗干扰能力, 且计算复杂度比块傅里叶变换算法明显降低, 因此, 它在实际应用中具有一定的应用价值。

5 结束语

本文以TD-SCDMA系统上行链路和采用单根天线的情况为例, 研究了联合检测信号模型, 把该系统的联合检测问题转化为一个带约束条件的二次规划问题, 最后借助于90年代初提出的一种有效的优化算法ε近似算法, 对上述优化问题进行求解, 以检测用户发送的信号, 并结合MATLAB软件对该算法仿真, 从不同的角度对仿真结果进行比较。从仿真图可直观看出:本文算法的复乘计算量明显比块傅里叶变换算法低。本文只以单根天线和上行链路为例进行研究, 而对于多根天线的联合检测技术的性能分析是我们下一步要研究的问题。

参考文献

[1]A.Klein, P.W.Baier.Simultaneous Cancellation Cross of Interference and ISI in CDMA Mobile Radio Communications[C], Proc.Of the3th IEEE International Symposium on PIMRC, 1992, 10:118-122

[2]LEE W, NAM J, RYU C, Joint Beamformer-Rake and Decorrelating Multiuser Detector Using Matrix Levinson Polynomials[J].IEICE Trans Commun, 2000, E83-B (8) :1640-1648

[3]Vollmer M, Haardt M, Gotze J, Schur Algorithms for Joint Detection in TD-CDMA based Mobile Radio Systems[J].Ann.Telecommun, 1999, 54 (7) :365-378

[4]Pigeonnat Y, Alternative Solutions for Joint Detection in TD-CDMA Multiple Access Scheme for UMTS[C.2ndIEEE Workshop Signal Processing Advances in Wireless Communications, Annapolis, MD, 1999:329-332

[5]Vollmer M, Haardt M, Gotze J, Comparative Study of Joint Detection Techniques for TD-CDMA Based Mobile Radio Systems[J].IEEE Journal on Selected Areas in Communications, 2001, 19 (8) , pp1461-1475

[6]Vollmer M, Haardt M, Gotze J, Efficient Joint Detection Techniques for TD-CDMA in the Frequency Domain, Proc COST262Workshop:Multiuser Detection in Spread Spectrum Commmunications, 2001

[7]Li Qingyu, Bai Er-Wei, Ding Zhi, Blind Source Separation of Signals With Known Alphabets Usingε-Approximation Algorithms[J].EEE Trans on signal processing, 2003, 51 (1) , pp1-10

[8]Li Qingyu, Bai Er-Wei, Ye Yinyu, Blind Channel Equalization andεApproximation Algorithms[J].IEEE Trans on signalprocessing, 2001, 49 (11) , pp2823-2831。

[9]Ye Yingyu, Approximating Quadratic Programming with Bound and Quadratic Constraints[J].Math Program, 1999, 84, pp219-226

[10]Rec.ITU-R M.1225, Guidelines for Evaluation of Radio Transmission Technologies for IMT-2000[S]

[11]康绍莉, 裘正定, 李世鹤.TD-SCDMA系统中低代价信道估计方法的改进[J].通信学报, 2002.10.pp108-113

说说精确与近似 第2篇

关键词：精确,近似,矛盾统一

精确与近似看起来像是个数学问题,其实个中包含了丰富的辩证思想,普遍存在于人类认知、思维、思想和行动的各个方面,可以说无处不在无处不有。下面从哲学、物理、数学、化学、文学、电子学、生物学以及日常生活等方面说说两者的存在及其相互关系。

1 哲学

在人类历史上大名鼎鼎的哲学家如亚里士多德,柏拉图,苏格拉底,托马斯阿奎,迪卡尔,黑格尔,他们在各自所处的年代都提出了自己的哲学观点,都比较准确地反映了当时的哲学思想,但都不是完全正确的思想,于是后来出现了马克思主义哲学,它把唯物主义和辩证法有机地统一起来,特别是将唯物主义原则贯彻到社会历史观中,第一次正确解决了社会存在和社会意识的关系这一历史观的基本问题,创立了历史唯物主义; 第一次确立以 “外部世界和人类思维的一般规律”作为自己的对象,从而正确解决了哲学和具体科学的关系。所以我们认为马克思主义哲学是科学的世界观和方法论。不过可以肯定的是马克思主义哲学也不是终极学说,随着人类认识自身和世界的不断深入,它一定还会进一步得到发展甚至是更正。

2 物理

物理学的第一个问题就是运动与静止,运动是精确的静止是近似的或者说运动是绝对的静止是相对的。两者是对立统一的。运动是物质的根本属性,它是指宇宙中发生的一切变化和过程。物质和运动是不可分割的。一方面,物质是运动的物质。运动是物质所固有的根本属性和一切物质形态的存在方式。设想有不运动的物质是形而上学唯物主义的特征。另一方面,运动是物质的运动。物质是运动的承担者。设想有离开物质的运动是唯心主义的观点。静止是运动的特殊状态,是物质运动在一定条件下、一定范围内处于暂时稳定的平衡状态。相对静止有两种基本情况: 一是在机械运动中特定事物之间没有发生位置移动;二是事物处于量变阶段,没有发生根本性质的变化。绝对运动和相对静止是辩证统一的: 相对静止中包含着绝对运动; 绝对的运动中也包含着相对静止的状态; 物质的具体形态都是绝对运动和相对静止的统一。承认运动的绝对性,并不否认相对静止; 承认相对静止,但不能把静止绝对化。否认绝对运动,把相对静止绝对化,就会走向形而上学不变论; 借口绝对运动,否认相对静止,就会导致相对主义诡辩论。

17 世纪牛顿力学成功地把天上物体和地上物体的运动规律统一起来,完成了物理学上的第一次大综合。牛顿力学不仅准确地预言了彗星的回转,而且帮助人们发现了新的行星。人们由此对牛顿力学推崇备至。但是随着人类认识的发展,人们发现牛顿力学只是对宏观物体的低速运动规律的反映,而在微观物质运动和接近光速的高速运动上却不适用。所以牛顿力学只是对客观规律的近似反映,是相对论力学的一个特例。

3 数学

数学上精确与近似的例子更是多得不胜枚举。最简单的阿拉伯数字1,2,3,……每一个都是准确的,当用它计算可以数数的物体时,如一个苹果,两个橘子是准确的,但当它用于测量时却很难准确了,如某人身高1. 7 米,车速100千米/小时都不可能真的准确,只能是个近似值,最多是近似的程度不同罢了。

事物的模糊性也对精确描述提出了挑战。1965 年美国数学家查德发表了论文 《模糊集合》,从而开创了一门新学科———模糊数学。模糊数学首先改变了传统集合论的元素属于集合的概念,它把元素属于集合模糊化,变绝对的属于概念为相对的属于概念。查德用隶属度来度量事物类属关系的模糊性。给定论域U上的模糊集合A,对U中的每个元素,以1 表示完全隶属于A的元素的隶属度,以0 表示完全不属于A的元素的隶属度,以区间[0,1] 上的不同实数表示以不同程度属于A的元素的隶属度,较大的数对应于对A隶属程度较大的元素,较小的数对应于对A隶属程度较小的元素。这样得到的一个从U到[0,1]的函数叫作模糊集合A的隶属函数。隶属函数刻画了元素由不属于集合到属于集合的渐进过程。模糊集合论是模糊数学的基础,模糊数学是对模糊性进行数学和逻辑分析的工具。

4 化学

化学中的精确与近似现象也是普遍存在的。如水分子是由两个氢原子和一个氧原子组成的,不管哪里的水这种结构、比例都不发生变化,是绝对的。一千克水中包含的氢原子和氧原子的重量也是确定不变的。虽然氢原子和氧原子也许还可以有其他组合方式,但那样组成的物质已经不再是水了。实际上,化学中的方程式中各个元素的个数、比例都是固定不变的,是绝对的准确的,否则就不是此方程式了,它所表达的化学反应也就不同了。

但由于事物的复杂性,化学中也有许多近似,看看下面关于水泥的资料就明白了。

硅酸盐水泥的主要化学成分是: Ca O、Si O2、Al2O3、Fe2O3,还有Mg O、K2O、 Na2O、 SO3等。其含量大约为:Ca O=64%~67%,Si O2=20%~23%,Al2O3=4%~8%,Fe2O3=3%~6%。

水泥熟料的主要矿物组分是: 硅酸三钙( 3Ca O. Si O3简写成C3S) 、硅酸二钙( 2Ca O. Si O2简写成C2S) 、铁铝酸四钙( 4Ca O. Al2O3. Fe2O3简写成C4AF ) 、 铝酸三钙( 3Ca O.Al2O3简写成C3A) 。含量大约为C3S = 52% ~ 60% ,C2S =22% ~ 28% ,C3A = 4% ~ 15% ,C4AF = 4% ~ 15% 。

可见水泥分许多种,每种水泥中包含的各种化学成分比例又各不相同,千差万别,只能用近似含量来表达了。

5 文学

文学中关于精确与近似的例子也是不胜枚举。准确的有: “一日三省吾身”“三顾茅庐”等,但许多情况下作者为了比喻,形容,类比,夸张或者无法确认精确数量时常常用近似方法描述事物,人情世故等。 《诗经》中 《国风·魏风·硕鼠》“硕鼠硕鼠,无食我黍! 三岁贯女,莫我肯顾”。其中 “三岁”绝不是准确的三年,而应该是几年多年。李白“飞流直下三千尺”中的 “三千尺”是夸张的说法,绝对不是真的 “三千尺”,但是人人都觉得李白写的太好了,试想如果李白写成54 米之类的话,恐怕就没人认识李白,李白也就不是李白了。类似的句子还有: 五十步笑百步、百步穿杨、梅花潭水三千尺、燕山雪花大如席、自信人生二百年、会当水击三千里、千里之行、始于足下、千里之堤、溃于蚁穴、听君一席话、胜读十年书、一心一意、一分为二、不三不四( 三心二意) 、四面八方、四通八达、五光十色( 五颜六色) 、六神无主、七零八落( 七上八下) 、五花八门、半斤八两、九牛一毛、九死一生、九牛二虎之力、十全十美( 十万火急) 、百花齐放( 百家争鸣) 、千军万马,等等。

6 电子学

电子学属于工程类学科,其中的精确与近似更是常见。这里以三极管放大倍数为例。如图所示三极管的输出特性曲线,在放大区内,三极管的放大倍数分直流和交流两种,分别用 和 β 表示。其中的直流放大倍数 其实并不是一个定值,同一个三极管在其不同的寿命期 不一样,不同温度下也不一样,即便温度不变,在放大区的不同位置 也不一样,一些管子差别还相当大,这就存在一个分析计算时怎么处理的问题,如果一味地追求准确,实际上将无法进行,所以此时必须用近似值代替真值,认为是个常数。同理 β 和一样也只能用近似的固定数值代替真值。实际上 β 和 虽然从定义上完全是两回事,单就数值的大小而言两者也差别不大,在一定程度上完全可以近似认为两者相等。

7 生物学

地球上生物的进化经历了漫长的过程,从有机物到单细胞,从植物到动物最后进化出所谓的高级动物———人类。其中的任何时段的任何生物体都包含着精确与近似现象。第一个单细胞的出现,把原来不可数的有机物进化为可数的细胞个体,实现了从近似到准确的升华。

人类进化到今天已经比较固定地呈现出几种固定的人种,不同人种之间从基因的层面说差别几乎可以忽略不计,脏器管和机体结构几乎没有区别,智力也没有太大的差别,也就肤色有差别。所以大家都是相似的。但从另一个方面说,长的完全一样的两个人世界还没有,即便是双胞胎外人看起来非常相似但他们间同样有差别,他们的父母一般都能比较好的辨认。所以此人就是此人,他的行为就是他的行为,是准确的,可引分清的。

看看下面的考题,它也说明了准确与近似的普遍存在。

下列各题中的数据,哪些是准确数?哪些是近似数?

( 1) 通过第三次全国人口普查得知,山西省人口总数为3297 万人;

(2)生物圈中,已知绿色植物约有30万种;

(3)某校有1148人;

( 4 ) 由于我国人口众多,人均森林面积只有0. 128公顷;

( 5) 这个路口每分钟有3 人经过;

( 6) 地球表面积约5. 1 亿平方千米。

8 日常生活

近视数: 一棵树高5 米,一段路长20 米,一根绳长8 厘米,中国人口13 亿,中国陆地面积960 万平方千米,某市人口900 万。

准确数: 两本书,五把尺子,两张照片,我班共有46人,一包牛奶3. 5 元,一本本子68 页。

基于函数近似的知识迁移 第3篇

传统机器学习方法通常假设学习任务是孤立的, 缺乏迁移学习的能力, 造成了目前绝大多数机器学习方法对某一类问题的学习, 都是从零起点开始, 而不能借鉴其他同类问题的学习结果。所以, 提高机器学习能力的一个关键在于, 要让机器能够继承和发展过去学到的知识。利用已有的学习经验帮助新任务学习的方法称为“迁移学习 (Transfer Learning, TL) ”[1]。

迁移学习于上世纪90 年代引入到机器学习领域, 国内外对相关基础理论和方法进行了研究[2,3,4]。强化学习领域的知识迁移研究也有了一些初步进展, 文献[5]探讨了具有迁移学习能力的聚类方法;文献[6]基于相似任务间的共有特征建立了知识迁移框架;文献[7]在经典TD算法中提出 “行为迁移”方法以实现知识迁移;文献[8]讨论了知识迁移与机器学习的关系, 并对知识迁移的潜在问题进行了探讨;文献[9]提出了增量关系回归树算法处理强化学习和监督学习中的概念漂移问题, 并实现知识在任务间迁移;文献[10]在检索现有文献基础上, 对基于能力和目标的迁移学习方法进行分类, 并对迁移学习的研究方向提出了建议。

函数近似特别是线性函数近似作为一种泛化方法, 用于把有限状态子集上的学习经验, 泛化到很大的状态子集上, 这种泛化一般是在同一学习任务内不同状态之间进行的。不同任务间的知识迁移, 在强化学习领域尚未见到采用函数近似方法的文献, 本文对此做了一些探索和试验, 在相似模型的强化学习任务中, 提出基于函数近似的知识迁移 (Knowledge Transfer Based on Function Approximation, KTBFA) 。KTBFA方法用带参数的线性函数近似表示Agent在源任务中学习到的知识即V*值。根据任务的相似性, 把相同形式和参数的近似函数由源任务迁移至目标任务, 计算目标任务的初始V0并作为目标任务的先验知识, 实现知识迁移。实验表明, 在相似类型的强化学习任务中, 基于KTBFA的Transfer-Q-learning算法与经典Q-learning算法相比, 机器学习效率有非常大的提高。

1 基础理论

强化学习模型由Agent和环境构成, Agent与环境间的交互可以看成一个马尔可夫决策过程 (MDP) , 因此强化学习的研究主要集中在对MDP问题的处理。

MDP由环境的状态空间X , Agent的动作空间U , 状态转换函数f , 以及奖赏函数ρ组成。在每个离散时间步, 动作uk作用于状态xk, 引起状态变化到xk+1, 状态转换由函数f确定:xk+1=f (xk, uk) 。同时, Agent接收标量性质的奖赏信号rk+1, 奖赏由函数ρ确定:, 一般假定是有穷的。奖赏函数评估了状态从xk到xk1变化的即时效果, 一般情况下与动作的长期效果无关。Agent根据策略函数h选择动作:ukh ( xk) 。

只要给定f 、ρ、当前状态xk和当前动作uk, 就能确定下一状态xk1和奖赏rk1, 则称之满足马尔可夫性质, 该性质为强化学习算法提供了理论保证[8]。

强化学习算法的目标是寻找最优策略以最大化期望回报。所谓回报, 指连续多次交互后奖赏的累积值。一种描述策略的简便方法是使用策略值函数。

策略h的动作值函数Qh定义为从某一状态x开始, 施加给定的动作u , 然后根据策略h累积的奖赏:

这是用Bellman方程递归描述的, 上式表明:根据策略h , 在状态x采取动作u的Q值, 等于立即奖赏与下一状态在策略h下的折扣Q值之和。

所有策略的Q-函数中, 值最大的Q-函数定义为最优Q -函数:

在每个状态上选择动作, 如果满足:, 则由此得到的策略h*是最优的, 因为该策略能得到最大回报。

Q* 的特征是满足Bellman最优方程, 表明在状态x采取动作u的最优Q值, 等于立即奖赏加上下一状态最好动作的折扣最优Q值:

在Bellman最优方程的基础上, Watkins于1992年提出了Q-learning算法[12], 这是强化学习的一个重要里程碑。Q-learning算法采用Q (x, u) 作为估计函数, 从任意初始Q-函数Q0开始, 迭代计算Q-函数。每次迭代之后, 采用如下数据元组更新Q-函数:

其中是学习率, 方括号内的式子是时间差分, 即 (xk, uk) 的最优Q - 值更新后的估计与当前估计Qk ( xk, uk) 之间的差值。

需要注意的是, 传统Q-learning算法的初始Q0值一般都设置为零, 意味着该算法对新任务的学习都是从零开始的, 没有复用到Agent学习其他任务时获得的知识。

为了计算最优策略h*, Agent必须搜索整个X×U空间, 一般应用问题的非常大, 这一计算过程非常消耗计算时间, 甚至如连续状态-动作空间问题, X×U本身就是不可穷尽的。另外, 强化学习结果如值函数或者策略的表示, 总是依赖于具体的状态和动作, 意味着只要学习任务稍微改变, 以前的学习结果就会变得毫无用处。这些问题的存在, 是传统强化学习方法没有得到大规模实际应用的一个重要原因。

2 知识迁移

由于传统方法存在的问题, 对于强化学习来说, 学习结果的可复用性显得尤为重要。本质上, 迁移学习复用过去的学习经验和结果以加速新任务的学习。由于强化学习的目标是动态的策略即行为, 可以将强化学习中的迁移分为两类:行为迁移和知识迁移[1]。行为迁移通常将先前学习到的策略或部分解决方案用于新任务的学习。知识迁移注重对任务本身的理解, 并试图学习解决问题的一般原理。

知识迁移关注的焦点之一是值函数V: S →R的迁移。Konidaris提出了任务与论域分离的迁移学习框架, Mahadevan提出了被称为“原值函数 (proto-value function) ”的抽象Fourier基[13], 以实现值函数与具体任务无关。这里使用函数近似的知识表示方法, 实现值函数 (知识) 从源任务到目标任务的迁移。

2.1 函数近似V值迁移框架

设源任务状态空间X {x1, x2, ....xp}, 目标任务状态空间Y {y1, y2, ....yq}。 p为X中状态数量, q为Y中状态数量。

函数逼近器是一个从参数θ空间到V值函数空间的映射。根据源任务与目标任务的性质和特点, 事先设定函数的形式以及参数个数。函数逼近器的参数通过源任务V值函数进行调节。

设V值函数逼近器参数向量的维数为n , 逼近器表示为一个近似映射F , F:Rn→L, Rn是n维参数空间, L是V值函数空间。每个参数向量都对应一个近似V值函数

也可以等价写成关于状态x的形式:

其中表示V值函数在状态x上的函数近似。在调节的过程中, 不需要存储每一个状态所对应的V值, 只需要存储一个n维的向量。假如状态动作空间是离散的, n一般远小于, 因此, 近似函数是源任务V值空间的一种简洁表示方法, 在一些文献中也称为拟合函数。需要注意的是, 这种表示方法存在一定的近似误差。

一般情况下, 函数逼近器F都是非线性的函数形式, 但是在强化学习状态值函数的近似表示中, 我们使用线性的函数逼近器。因为线性函数逼近器实现简单, 且易于分析算法的理论性质[8]。一般线性V值函数逼近器包含n个基函数, , 以及一个n维的参数向量。状态所对应的近似V值的计算如下式所示:

其中是关于基函数的n维向量。在一些文献中, 基函数也被称作特征函数。

为了简化动作空间上的极大化问题, 连续动作空间一般被离散成n个离散的动作值。将原始动作空间离散为一个M维的动作集, 用Ud表示, 即是N维状态无关的基函数, 且动作空间Ud中每一个动作对应一组基函数。对于任意状态动作对, 近似Q值函数的计算如下式所示:

其中是关于当前状态动作对的基函数, 且所有与当前动作无关的基函数都被置零。

因此, 参数向量含有N*M个元素。这类函数逼近器可以看成Q值函数空间中M个离散的状态无关的切片, 每一个函数空间切片与动作空间中的一个动作相对应。需要注意的是, 函数逼近器仅针对离散动作空间Ud中的动作有效, 其他不属于Ud的动作, 函数逼近器的输出为0。

2.2 Tile编码

线性近似函数方法用于泛化时, 在数据量和计算量方面非常高效, 这些优势依赖于状态是如何表示为特征的。把源任务先验知识加入到目标任务系统中, 重要方法之一是选择与任务相符的恰当特征。Tile编码特别适用于顺序数字计算机和高效的在线学习。

Tile编码中, 特征感知域被聚集成多个分区, 每个分区都是状态输入空间的一个详尽划分。一个分区称为一个tiling, 分区中的一个元素称为一个Tile。一个Tile就是一个二值特征的感知域。

Tile编码的优点是, 任一时刻在场特征总数是严格受控的并独立于输入状态。每个在场特征恰好位于一个tiling, 所以在场特征的总数与tiling数量相同。

如果使用网格式tiling, 计算当前特征的索引特别简单。假设要处理的是具有两个连续状态变量的任务, 用tile覆盖状态空间最简单方法是用均匀分布的二维网格表示。

给定状态空间中一个点的坐标x和y , 很容易计算出该点所在Tile的索引。如果用到多个tiling, 每个tiling产生不同偏移, 则每个tiling都以不同方式切割状态空间。如图1 所示的例子, 在网格中额外加上一行和一列, 就覆盖了状态空间所有点。选择适当的tiling数量, 以获得适当的Tile密度。tiling越密集, 目标函数就可以逼近得越好越精确, 但是计算开销也越大。

2.3 参数求解及V值迁移

根据源任务真实V值与近似Vˆ 值的关系, 建立等式:

源任务共有p个状态, 则由上式可产生p个方程构成的联立方程组, 共有n个待求解的参数θ1, ..., θn。设真实V (x) 组成的列向量为b , 方程组系数矩阵为A。则联立方程组可以写成矩阵形式:

一般情况下, 源任务状态数量p远大于参数数量n, 如果满足, 则方程组无解, 这时方程组称为矛盾方程组。在数值代数中, 对矛盾方程组的计算是在均方误差极小意义下的解, 也就是在最小二乘意义下的矛盾方程组的解。相关定理证明, 方程组的解就是矛盾方程组在最小二乘意义下的解。由此可求得拟合均方误差极小的参数向量。

根据求解的参数向量, 可以近似表示目标任务空间Y的V值:

根据任务的相似性, 不同任务间使用同一近似值函数, 以实现从源任务状态空间到目标任务状态空间的V值迁移, 这一过程我们称之为基于函数近似的知识迁移 (KTBFA) 。要明确的是, 迁移到目标任务状态空间的知识是粗糙的, 甚至局部是负迁移, 必须进行后处理。

2.4 Transfer-Q-learning算法

设定目标任务初始, 设计Transfer-Q-learning如算法1 所示。其中Step1~ Step5为Q值扩展, 把迁移到目标任务的V0值扩展为初始Q0值, Step6~ Step10 使用Q-learning算法对Q0值进行后处理, 循环迭代至最优Q*值。

3 实验

在“格子世界”实验平台上, 设计了类型相同但是状态空间及障碍物都不同的两个格子世界任务, 用于比较提出的基于KTBFA方法的Transfer-Q-learning算法的性能。

3.1 实验描述

源任务:如图1 所示, 计算从起点S到终点G的最优策略, 其中黑色部分为障碍物。Agent可以上下左右移动 (不能出界和进入障碍物) , 每移动一步的奖赏为-1。

目标任务:如图2 所示, 黑色部分为障碍物, 其他同源任务。

由图1、图2 可以看出, 两个强化学习任务的类型相同, 但是状态空间的大小以及障碍物数量和位置都不相同, 我们称这两个任务为相似任务。Agent使用传统强化学习算法对两个任务进行充分学习得到的最优V*值, 如图1、图2 方格中的数字所示。

3.2 V值迁移

分别以终点G为原点, 在源任务和目标任务状态空间建立二维坐标系。源任务横、纵坐标系为x1, x2, 目标任务横、纵坐标系为y1, y2, 如图1、图2 中虚线箭头所示。每个方格的坐标设定为该方格离开原点的方格数量, 例如图1 中起点S的坐标为 (4, 5) 。

以每个状态的二维坐标 (x1, x2) 为该状态的特征值 (函数) , 建立二元线性函数逼近器:

把源任务每个状态x (x1, x2) 的真实V值代入函数逼近器并建立联立方程组, 求解矛盾方程组得:

根据任务的相似性, 把源任务V值函数逼近器V (x1, x2)  0.6295* x10.5571* x2迁移至目标任务:V ( y1, y2)  0.6295* y10.5571* y2, 其中 (y1, y2) 是目标任务状态y的特征值 (函数) 。目标任务空间计算出的迁移初始V0值如图3 所示, 读者可以将其与图2 所示目标任务最优V* 值的分布特点和变化趋势做一些比较。

3.3 算法比较

使用迁移初始V0值的Transfer-Q-learning算法的收敛过程, 以及不使用迁移初始V0值的原始Q-learning算法收敛过程对比如图4 所示。由对比实验的收敛过程可以看出, Transfer-Q-learning算法初始情节的迭代次数以及收敛需要的情节数, 都小于原始Q-learning算法, 学习效率有非常大的提高。

3.4 实验分析

强化学习的目标是寻找最优策略, 为了达到这个目标, 必须对每个状态做回报值大小的区分。本质上, 可以把强化学习过程理解为状态区分过程, 一般情况下, 采用迭代方式从零开始逐步求解回报值区分各个状态。KTBFA方法中, 迁移到目标任务的知识已经对各个状态做了初步区分, 而这个初步区分与最优区分 (最优V* 值) 是基本一致的, 对比图3 所示目标任务的迁移V0值与图2 所示目标任务的最优V* 值, 可以发现, 除了阴影部分障碍物状态, 其他状态的迁移V0值与最优V* 值的分布特点和变化趋势是基本一致的。在此基础上再进行迭代计算, 就可以显著减少迭代计算量, 提高学习效率。

4 结束语

“积的近似数”教学设计 第4篇

教学目标:

1.懂得求积的近似数的必要性, 掌握用“四舍五入”法取积的近似数。

2.利用已有知识经验, 学会根据题目要求与实际需要求积的近似数;培养自主探索和迁移类推能力。

3.感受数学与实际生活的联系, 逐步养成在生活中发现数学问题的意识和习惯;渗透人类与动物和谐相处的育人理念。

教学过程:

一、复习旧知, 导入新课

1. 复习求一个小数的近似数。

师:同学们已经学过求一个小数的近似数, 请大家按要求写出下表中小数的近似数。

小结:求小数的近似数, 可以用“四舍五入”法。即要看精确数位的下一位是几, 如果是4或比4小, 就把尾数舍去, 如果是5或比5大, 就把尾数舍去, 然后在精确的数位上加上1。

2. 导入新课。

师:在现实生活中, 许多小数并不一定都要知道它们的准确数, 而只需要知道它们的近似数就可以了。同样, 在实际应用中, 小数乘法乘得的积往往不需要保留很多的小数位数, 只要根据需要求出积的近似数就可以了。今天, 我们一起来学习求积的近似数。 (板书课题:积的近似数)

(设计意图:由于求积的近似数所用的方法同求一个小数的近似数的方法完全相同, 因此在教学新知前, 组织学生复习、练习, 让他们回忆求一个小数的近似数的方法, 目的是为自主探索求积的近似数做好准备。所以, 从求一个小数的近似数引出求积的近似数, 过渡自然、顺理成章。)

二、自主探索, 学习新知

1. 创设情境。

投影课本例6主题图, 教师讲述故事:一天晚上, 一个商店里的钱物被盗窃, 为了侦破这起盗窃案, 抓获犯罪嫌疑人, 某县公安干警随即带了一只警犬前往犯罪嫌疑人躲藏的地点。到达后警犬仔细搜索, 突然, 警犬大声叫喊:“坏蛋, 看你往哪儿跑!”警犬飞速扑向草丛里躲藏的犯罪嫌疑人。结果, 公安干警很快就抓到了这起盗窃案的犯罪嫌疑人。

2. 问题质疑。

师:同学们, 为什么警犬能很快帮助警察抓获犯罪嫌疑人?你们知道吗?谁来说一说。

根据学生的回答, 教师指出:因为狗的嗅觉很灵敏, 狗的嗅觉细胞数量比人多得多, 狗能利用它十分灵敏的嗅觉闻出坏蛋身上的气味。在现实生活中, 动物是人类的好朋友, 我们要保护动物, 保护动物生存的环境。

3. 教学例6。

(1) 呈现信息:人的嗅觉细胞约有0.049亿个, 狗的嗅觉细胞个数是人的45倍。

(2) 引导提问。

根据学生的提问, 教师板书:狗的嗅觉细胞约有多少亿个? (得数保留一位小数。)

(3) 引导列算式。求0.049的45倍, 就是求45个0.049是多少, 用乘法计算 (教师板书) :0.049×45。

(4) 学生独立完成求积的近似数。

当学生算出“0.049×45=2.205”后, 提问:“题目要求保留一位小数, 如何求积的近似数呢?”先让每个学生独立求出2.205的近似数 (指名板演) , 然后组织小组讨论交流:怎样保留积的一位小数?最后请板演的学生解释取近似数的过程和理由, 全体学生对他的板演过程和解释作出评价。正确的计算过程如下:

(5) 反馈、评价。引导学生反馈、评价自己的计算过程、结果是否正确, 更正自己做错的地方。

(6) 小结:求2.205这个积保留一位小数的近似数, 要看小数点后第二位, 因为积的十分位上的数是0, 0<5, 所以要舍去小数部分的0和5, 积的近似数约是2.2。由于求得的结果是近似数, 所以在横式中要用约等号“≈”。

(设计意图:教材主题图设计“警犬抓坏蛋”的情节对学生很有吸引力。创设警犬侦破盗窃案的故事情境, 激活学生的求知欲。通过引导质疑, 引出人和狗的嗅觉细胞的有关信息, 让学生提出问题、列式计算, 自主探索求积的近似数的方法。通过交流研讨、反馈、评价、更正错误, 提升学生的认知能力。同时渗透人类与动物和谐相处的思想教育。)

4. 拓展延伸。

师:同学们, 有些应用问题取近似数时, 还要联系实际想一想。下面这道题的答案没有要求保留几位小数, 应保留几位小数才合理呢?

出示:小丽家上个月的用水量是16.85吨, 每吨水的价格是2.5元。小丽家上个月应付水费多少元?

(1) 学生独立列式计算。16.85×2.5=42.125≈42.13 (元)

(2) 讨论交流:这道题为什么要保留两位小数?

(3) 小结:由于是计算钱数, 人民币最小的单位是分, 应精确到分 (百分位) , 所以将计算结果保留两位小数是合理的。根据“四舍五入”法把百分位后面的数省略, 千分位上的数是5, 向百分位进1, 得到近似数42.13。

5. 总结求积的近似数的方法。

在实际应用中, 小数乘得的积往往不需要保留很多的小数位数, 这时可以根据需要或题目要求取积的近似数。取近似数的一般方法是:保留整数, 就看第一位小数是几;保留一位小数, 就看第二位小数是几;保留两位小数, 就看第三位小数是几……然后按“四舍五入”法保留小数位数。

(设计意图:在教学例6后, 增加一道计算钱数的练习, 旨在拓展延伸, 让学生灵活掌握求积的近似数的方法。通过练习, 让学生认识到在收付现款时, 通常只算到“分”, 只要保留两位小数, 增强学生应用的自觉性。通过总结求积的近似数的方法, 促进学生思维的内化, 提升迁移、类推能力。)

三、巩固练习, 提高能力

1. 下面的计算对吗?把错误的改正过来。

(1) 9.1×0.5=4.6 (得数保留一位小数)

(2) 2.34×0.15≈0.36 (得数保留两位小数)

先让学生算一算, 再判断计算是否正确, 然后把错误的改正过来。

2. 计算下面各题。

(1) 1.8×0.7 (得数保留一位小数)

(2) 0.56×1.4 (得数保留两位小数)

学生独立完成计算 (指名板演) , 教师巡视, 进行个别辅导, 集体订正。

3. 解答下面各题。

(1) 一幢大楼有26层, 每层高2.84米。这幢大楼约高多少米? (得数保留整数)

(2) 一块长方形菜地, 长12.4米, 宽5.6米。这块菜地的面积是多少平方米? (得数保留一位小数)

学生独立完成列式计算 (指名板演) , 教师巡视, 进行个别辅导, 集体订正。

近似商标的侵权认定与限制 第5篇

一、近似商标侵权的认定

广义的商标侵权包括直接侵权和间接侵权, 直接侵权是指侵权人为了达到商业目的, 在没有经过权利人许可的情况下, 在形同或者相似的商品或服务、域名或商号上 (如果是驰名商标, 则非近似) 使用与他人注册商标相同或近似商标的行为;间接侵权主要是指, 在明知某种行为构成商标侵权的情况下, 仍然教唆、引诱他人去实施这种行为, 或者对他人的侵权行为提供实质性帮助的行为。在直接侵权中, 主观过错并不是构成侵权的必要条件, 只影响责任的承担。本文研究的只涉及近似商标侵权, 属于狭义的商标侵权, 因此只研究直接侵权。

近似商标侵权侵犯的是商标的消极全能, 即商标的排他权。商标权为依商标法注册取得的专有使用权, 其主体为注册人、继承人、受让人或合法被授权使用的人, 由于商标权具有排他的专有使用权, 故无法律上的权源而使用相同或近似于他人注册商标的图样于同一类商品或类似商品者即构成商标侵权。狭义的商标侵权是指侵权人在未经权利人许可的情况下在商品有效地域和有效期内, 在相同或类似商品上使用与其他相同或近似商标的行为。因此, 狭义的商标侵权与近似商标的侵权具有相同的表现形式, 是同一概念。笔者认为, 构成近似商标侵权有五大构成要件:

1.侵权人实施了侵权行为。商业标识类知识产权的保护是非穷尽式的, 除专门的《商标法》保护外, 还可以受《反不正当竞争法》等的补充性保护。我国《商标法》《反不正当竞争法》《商标法实施条例》以列举的方式对侵权行为的种类和表现形式进行了规定, 包括“使用”“销售”“伪造”“擅自制造”“假冒”等, 只有在法律规定的侵权行为范围内, 才能够被认定为侵权。

2.侵权行为与损害事实之间有因果关系。这种因果关系是指被侵权的权利主体的财产或名誉损失是由于侵权人的不正当行为导致的。

3.侵权商标与被侵权商标使用于相同或类似商品或服务上。除了驰名商标以外, 近似商标的侵权必须是侵权商标与被侵权商标使用于相同或类似商品或服务上, 否则属于合法范围内的正当使用。

4.近似商标的使用足以使消费者产生消费混淆的可能性。商标的识别性受到侵害即宣告商标侵权的产生。只有当两个商标构成混淆性近似才可以构成近似商标侵权。

5.符合商标侵权的归责原则。在我国, 商标权的归责原则并没有一个定论, 《商标法》也没有明确作出规定, 只能参考某些条文:“有下列行为之一的, 均属侵犯注册商标专用权:……销售侵犯注册商标专用权的商品的……”“销售不知道是侵犯注册商标专用权的商品, 能证明该商品是自己合法取得的并说明提供者的, 不承担赔偿责任”“有下列行为之一的, 属于商标法第五十二条第 (五) 项所称侵犯注册商标专用权的行为: (一) 在同一种或者类似商品上, 将与他人注册商标相同或者近似的标志作为商品名称或者商品装潢使用, 误导公众的……”, 从这些条文可以推断出归责原则采用的是无过错责任原则, 即归责原则不考虑侵权人的主观状态。

二、近似商标侵权保护的限制

任何权利的自由都是相对的, “自由就是做法律许可范围内的事情的权利”, 为了使私权利与公共利益达到一定的平衡, 对商标权的行使和保护进行部分限制很有必要。在我国法律上能够成立的商标权限制有以下三种:

1.商标的合理使用。合理使用是指权利人以外的人在进行经营活动时对描述性商标进行善意、正当使用, 则不构成对商标专用权的侵权。合理使用包括了叙述性使用和指示性使用。“当以一种不欺骗公众的方式使用商标时, 我们并不认为商标足以神圣到禁止使用它以告知真相的程度, 商标不是禁忌”, 否则就无法向社会公众尤其是消费者传达销售或维修等信息, 但必须以商标所有人的同意为前提。商标的合理使用本质上是为了达到将权利人的利益与他人利益或公共利益平衡的目的。

2.商标权用尽。商标权用尽, 是指在取得商标权利人的许可将已经附有商标的产品首次投入市场以后, 即使再有人生产、销售、使用该产品, 商标权人都不能再以其拥有商标权进行对抗。商标权用尽这一制度的设计是基于保障商品交易安全, 促进商品正常流通, 避免商标权利人利用商标分割市场、加大垄断、提高物价的目的, 这已经超越商标现有的功能价值, 但是很符合市场规律的要求。

3.商标的非商业性使用。非商业性使用包括两类, 一类是新闻报道及评论中对注册商标的引用, 另一类是滑稽模仿, 是指在某些舞台作品中使用与注册商标相同或近似的文字或图形符号, 这两种情况都是私权利向公权利的妥协, 也是对近似商标侵权的限制。

三、注册商标与外观专利冲突的情形和建议

商标强调的是识别性功能, 而外观专利则强调的是设计的新颖性、创造性、实用性和美感, 当二者图形或者其他文字存在重叠或交叉且分属不同权利主体的时候, 侵权纠纷随之产生。我国的法律法规没有直接作出具体处理规定, 笔者认为, 可以参照以下情形和建议:

1.将他人的注册商标申请为外观专利。根据我国《专利法》的规定, 取得外观设计专利的实质条件有:新颖性、创造性、实用性、富有美感, 且不得与他人在先取得的合法权利相冲突。同时, 我国《商标法》也规定申请商标注册不得损害他人现有的在先权利。由此可见两部知识产权法都有意保护“在先权利”, 使“智慧财产权”具有相当的独创性。外观专利的申请很容易给心怀坏心的人留下空子, 因为申请不做实质审查, 能够比较建议就将外观设计专利申请下来, 因此外观专利并不能当然的对抗商标权, 即使享有外观设计, 也不能在商标侵权的事实发生以后被减轻责任甚至免除责任。

2.将他人的外观专利注册为商标。这里要分为两种情况:一种是将他人专利权效力期间的外观专利注册为商标, 这类情形显然违反了《商标法》规定的不得损害他人在先权利的条款, “法律不保护权利上的睡眠者”, 此时外观专利权人可以在商标公告期内向国家商标局提出异议, 已经注册的商标, 可以向国家商标局申请注销, 造成损失的要承担相应的民事责任;另外一种是将他人过期的外观专利注册为商标, 《商标法》规定的外观专利保护期为10年且不能续展, 超过十年的将转化为公用财产, 此时将他人的外观专利注册为商标将不视为侵权。

3.权利主体的相互协商转让作为注册商标与外观专利冲突的救济。注册商标专用权与外观设计专利权本质上都是一种智慧财产性权利, 属于民法上的流通物, 不管哪边是在先权利者, 都可以依照法律自由协商转让。外观专利的保护期限是10年, 自申请日起计算且期满不可续展, 注册商标的保护期限同样是10年, 但是从核准日起计算且期满后可以无限制续展。因此, 注册商标所有人与外观专利所有人可以相互协商转让, 将不同权利主体变为一个主体, 避免侵权纠纷的产生。协商转让是侵权纠纷产生后的一种私力救济, 是比法院、商标局和专利局等公力救济较为容易变通的权利处置方式, 能够把商标侵权纠纷转化成互利共赢的商业合作。

四、结语

知识产权的发展与保护是创新型经济的主要表现形式, 也是人类思想得以发展和燃烧的动力。彼得·德鲁克认为, 知识经济将占据后资本主义时期的经济主导。商标权作为知识经济的主要表现形式之一, 是无形财产权的重要组成部分, 加深对相同或近似商标侵权的研究, 有助于推动司法实务中对商标的常规管理和法律保护。

本文针对在司法实务中怎样认定近似商标构成侵犯注册商标专用权, 着重强调了近似商标的认定标准、近似商标侵权构成及其归责原则, 为有效地限制近似商标的侵权提出了部分可行性建议, 希望对以后的相同或近似商标侵权案件纠纷能够产生实际指导价值的借鉴意义。

摘要：识别商品或服务来源是商标的最基本功能, 商标近似作为商标侵权的常见形态之一, 其侵犯的是商标的识别性功能, 使消费者产生视觉混淆, 扰乱市场竞争秩序。注册商标产生的权利通常用“专用权”来表达, 权利人具有排斥他人使用相同或近似商标的权利, 申请注册的商标与取得外观设计专利而未注册的商标撞车能否构成侵犯注册商标专用权, 需要借助于近似商标的认定标准、侵权构成要件、归责原则等进行认定。

更新稀疏模式的近似逆算法 第6篇

1 稀疏近似逆的分类

稀疏近似逆法分为基于Frobenius范数最小化和矩阵分解两种。基于前者的算法主要有SPAI、MR、自适应的MR等, 基于后者的算法主要有AINV、FSAI、逆ILU等。总体说来, 由于其拥有良好的并行性, 稀疏近似逆SAI方法具有更高的效率。

2 构造更新稀疏模式的近似逆算法

通过迭代更新稀疏近似逆M, 从而逐步得到系数矩阵近似逆A-1, 这就是Renewing sparsity Pattern (AIRP) 算法的基本思想。也就是对近似逆M的每一列进行迭代, 每次迭代后均计算该列残差向量的范数。当残差向量范数小于事先设定的阀值ε时, 则跳出迭代循环。

3 数值实验

预处理后, 比较系数矩阵的特征值分布以及迭代的收敛速度。矩阵均取于, n代表矩阵阶数, nnz代表矩阵中非零元的个数如表1所示。

3.1预处理前与预处理后的特征值分布及迭代曲线的对比

实验都是在Matlab环境下执行, 图1和图2分别给出了矩阵NOS7进行AIRP预处理前与预处理后的特征值分布, 横轴代表实轴, 纵轴代表虚轴。预处理前很多特征值围绕在零的附近, 迭代很难收敛, 预处理后绝大多数的特征值都集中在1附近, 迭代容易收敛, 图3则分别画出了预处理前与预处理后的迭代曲线, 其中横轴代表迭代次数, 纵轴是残差向量的相对误差取对数后的运算结果, 可以看到, 预处理后, 收敛速度非常快, 而预处理前则基本上不收敛。

通过图4-6可以看到, 矩阵进行预处理前与预处理后的特征值分布以及迭代曲线与矩阵进行预处理前后类似, 预处理后大多数的特征值都集中在1附近, 少数特征值靠近零, 收敛速度有了很大提高, 迭代200次基本上收敛, 而预处理前则不收敛。

图7-9分别给出了矩阵预处理前后的特征值分布和迭代曲线, 结果非常接近矩阵预处理前后的结果。

4结语

预处理后特征值大多集中在1附近, 迭代速度明显加快, 针对一些在没有做预处理时迭代不收敛的问题, 可以达到收敛效果。

参考文献

[1]朱波杰.非对称线性系统的稀疏近似逆预条件子的研究[D].成都:电子科技大学, 2012.

[2]林成森.数值分析[M].北京:科学出版社, 2006.

近似重复视频检索方法研究 第7篇

随着社交媒体Web 2.0 飞速膨胀式的发展, 大量的视频被上传到互联网上, 这些视频被下载、 观看、 编辑,重新被上传到网上,因此互联网上充斥着大量内容相近的视频。 根据com Score的数据分析,2008 年11 月时,互联网上的视频总量已达126 亿个, 而到2009 年1 月则达到了148 亿个,如此短短的3 个月时间内视频总量就有17%的增幅。 通过Wu[1]的分析, 可以知道通过24 次基于You Tube,Google Video和Yahoo Video的视频查询,平均有27% 的视频, 有最高可达93% 的近似重复内容。这些数据表明互联网上存在海量的近似重复视频。

大量存在的近似重复视频会带来诸多的问题, 例如视频版权保护和视频检索结果准确性等。 由于无处不在的网络, 拥有版权控制的视频可能会被重新编辑、 修改然后重新发布, 所以视频版权商经常会发现自己的视频在没有经过允许的情形下就被修改并且发布到互联网上, 这会给他们的利益带来巨大的损失。 同样, 大量近似重复视频的存在也会影响视频检索系统的准确性。 很多时候在网上搜索某一个视频,其实想要得到返回的结果是那些与之相关的原始视频, 但是往往搜索结果靠前的是某个视频和它的近似重复视频, 而另外那些与关键词相关的原始视频排名却靠后, 极大地影响着检索的效果。 同时大量近似重复的视频也会带来大量的存储开销。

对视频不同程度的编辑会给近似重复视频的提取造成不同的影响,近似重复视频的准确查询仍然存在着巨大的挑战。 虽然可以通过给视频添加标签、注释分类等文字信息帮助提取过程, 但是此类方法不够准确,而且提取结果较大程度上取决于标记的准确性。 另外一种则是基于视频内容的近似重复性鉴定。 当前基于内容的近似重复视频提取方法整体可分成两大类:全局特征提取方法和局部特征提取方法。 全局的特征首先通过提取关键帧特征,然后通过空间、时间、颜色等模型整合这些帧的特征信息构成多维向量,视频之间的比较则为全局特征的匹配。 局部特征方法则通过提取关键帧的局部特征( 如SIFT[2]、PCA-SIFT[3]特征向量) 信息, 来帮助查询近似重复视频。

全局特征方法提取的特征信息较局部特征方法更加精简,因此在存储和特征匹配的阶段能够节省大量资源,但是全局特征信息对于视频的变换较为敏感, 在变化较大的情形下不能准确地提取近似重复视频。 局部特征虽然在大量变形的情形下有较好的提取效果, 但是计算复杂性和大量的存储开销使其在真实应用中实用性不高。

本文从全局特征和局部特征的准确性和计算性能出发, 分析了当前主流方法的优缺点, 并在此基础上对近似重复视频的发展方向进行了展望。

1 近似重复视频概念

近似重复视频是那些和原视频几乎一样, 但是在文件格式、编码参数、光度变化(包括颜色以及光照变化)、编辑方式( 包括插入水印、 边框等)、 长度或者某些特定变化下(例如帧的增加和删除等)有所不同。 所以可以认定这些近似重复视频和原视频大体一样。

重复视频是近似重复视频的一种, 且重复视频包含的信息和原视频基本一样,这并不意味着重复视频在像素层面上和原视频一模一样, 而是说包含的场景、 任务一样,没有添加新的信息。 而且判断两个视频是否重复取决于比较的角度。 例如有些版权控制的场景甚至需要判断视频中的某一帧是否和其他视频一样,而视频搜索过程中视频是否重复则是通过视频播放的整体内容而定的。 本文所述的重复视频是近似重复视频的一种,在检索方法中并不区别对待,因为无论是重复视频还是近似重复视频, 都会被检索出来而且排名较高。 原始、重复、近似重复视频概念图例如图1 所示。

2 近似重复视频检索方法

视频作为多帧图像在时间轴上的累加, 图像领域的识别和检索方法也同样可以运用在近似重复视频检索中。 近似重复视频的检索整体分成3 个部分:视频特征的生成、视频特征的管理、视频特征的匹配。

给定一个查询视频,并且需要从视频数据库中检测出相应的近似重复视频,首先需要对视频库中的所有视频进行特征提取, 根据检索需要采用相应的特征, 然后再对这些视频特征采用特定数据结果进行管理,例如树形或者局部哈希的方法等。 这个阶段属于检索过程中的离线过程,在输入查询视频之前就可以完成。 接着提取输入视频的特征,与视频库中的视频特征进行匹配,找出与之近似重复的视频,该过程属于数据检索中的在线部分。

在视频特征提取过程中,主要可以分成全局特征和局部特征两种。 全局特征主要是基于视频关键帧的颜色、纹理、动作等信息,将其整合成一个多维向量,在计算和存储方面较局部特征有较大优势,但是对于变化较大的视频识别效果较差。 虽然局部特征能在光线、噪声、微视角变化较大的情形下有较高的辨识度,但是其带来的巨大计算和存储开销使得在实际应用中并不适用。所以当前较好的方法是采用两者各自的优势,先用全局特征过滤那些差别较大的视频,接着利用局部特征进一步匹配,使得检索结果在性能和准确性方面都有较大的提升,接下来描述一些当前主流的视频全局特征和局部特征方法。

3 视频特征

3 . 1 全局特征

视频全局特征是通过将视频作为一个整体提取出的特征, 该特征具有占用存储空间小、 提取速度高的特点,被用在很多应用中。 颜色直方图以及主成分分析是经常被采用的两种方法。

3 . 1 . 1 颜色直方图

颜色直方图能够较好地反映图像中颜色的组成分布, 即各种颜色区间在图像中出现的概率, 虽然该方法对光照敏感,但是仍然是一种好的特征方法。 对于视频而言,基于颜色直方图的特征首先应提取视频中的关键帧, 接着提取每一帧的直方图, 然后对这些关键帧的颜色直方图取平均值,如式(1)所示[1]。

式(1) 中VS表示视频基于颜色直方图的全局特征,n为视频中关键帧的数目, Si表示所有关键帧第i个直方图的平均值,。 从式(1)中可得,视频的颜色直方图由一个m维的向量构成, 其中m是直方图柱子的个数, 得到了视频的颜色直方图后, 两个视频的相似性可以通过计算两个视频颜色直方图m维向量VSi和VSj的欧式距离,如式(2)[1]所示。

其中VSi= ( x1, x2… xm) , VSj= ( y1, y2… ym) 。 如果两视频的距离接近,就认为它们是近似重复的。

3 . 1 . 2 主成分分析

主成分分析是一种将多个变量通过线性变换以选出较少个数重要变量的一种多元统计分析方法,又称为主分量分析。

通过视频的主成分分析可以将最重要的信息作为视频的特征,不重要的部分将被舍弃。 该方法认为视频中的一小段都有着自己独特表达的主题,所以可以通过对视频帧的变化趋势用向量的方式表示出来,然后通过获取突出分布从而获取重要维度得到主要成分,形成视频的特征[4], 在比较两个视频主成分的相似性的时候, 为了提高精确性,主成分的旋转变化也是需要考虑的部分。

3 . 2 局部特征

视频的局部特征主要来源于关键帧的局部特征。 在图像和模式识别领域,局部特征点的发明使得近似重复视频的检测也有了巨大的发展,而且由于基于关键帧的局部特征在视频几何变换程度很大的情况下仍然有较高的辨识度, 检索准确度较高, 但是由于局部特征包含过多的信息, 通常采用高维的向量表示, 其在存储和计算方面占用较大的资源。

一张图片或关键帧包含成百上千个的局部特征点,而每个特征点由高维的向量构成(如SIFT的128 维向量,PCA - SIFT的36 维向量) , 虽然已有研究通过出现频率的高低去过滤掉低频的特征点来减少存储和计算的开销,但是基于局部特征向量的关键帧信息在匹配阶段仍然是耗时的。

4 特征索引

无论是采用视频的全局特征还是局部特征方法, 在提取特征信息后, 都需要将查询视频与视频库进行匹配,那么如何管理海量数据库的特征信息将直接影响查询性能和准确性。

4 . 1 树形结构

树形结构已经在图像检索领域有非常广泛的应用,如VOC-Tree[5],可以利用该树形结构对视频帧的局部特征进行聚类, 使得在特征匹配过程中以树的方式查询,能够快速提升检索性能。 在视频检索领域,视频提取的特征是基于图像特征的, 都是用高维向量表示, 所以基于树形结构的索引能有效提高索引速度,但是随着维数的不断增大,检索的效率会有所减少。

4 . 2 局部敏感哈希

无论是视频采用全局特征或者是局部特征, 特征信息都是以高维向量进行表示,局部敏感哈希是一种在高维情形下有效提高搜索效率的方法,通过哈希的方法可以在存储的时候将相似的特征信息存放在一起,在搜索的时候便能快速定位到近似重复的特征,无论是从准确性还是速度方面都有很好的性能。

5 实验分析标准和数据集

在近似重复视频检测领域,需要有大量的视频数据集来测试检索效果,如今已经有很多机构专门在这方面提供了较为丰富的测试集, 这些视频都是从网络上下载下来,有些还经过了一些编辑处理以模拟近似重复关系。在测试性能方面,检索准确率和效率是关注度较高的两个方面。

5 . 1 测试基准集

CC_WEB_VIDEO是香港城市大学和卡耐基梅隆大学提供的近似重复视频数据集合。 它总共包含通过24次查询过程中从Google Video ,Yahoo Video和You Tube上下载的13 129 个视频,这些视频下载后没有通过特定的软件进行编辑,并且通过人工做标记来表明最真实的近似重复关系,来和实现结果做比较以判断准确性。

VCDB[6]是上海智能信息实验室和复旦大学收集的大规模的近似重复视频集合, 总共包括100 000 个网络视频, 这些视频没有经过人为的变化处理, 重复关系通过人为手动做标记。

TRECVID[7]是美国政府支持视频检索的数据集, 每年都会基于上一年提供一些新的视频集合,这些视频经过人工的编辑然后和原视频混合在一起,真实的重复关系在变换之后也有记录。

MUSCLE - VCD - 2007 是一个重复视频的集合, 该集合中总共包括100 个小时的视频, 这些视频形式多样,有网络视频片段、电视视频、电影片段等,这些视频从分辨率和文件格式等方面均存在很大差异。

5 . 2 性能标准

在近似重复视频检索中, 检索速度和准确性是评判结果的两个非常重要的指标。

检索速度一般是从检索行为开始至结果返回中间这段过程中花费的时间来评定的。 在实验过程中,实验准确性是将程序返回的近似重复结果和最开始人为标记的视频近似重复关系做比较,人为标记的重复关系作为基准,在Wu[1]的CC_WEB_VIDEO集合中,就对集合中的所有视频做了标记,以记录近似重复关系。

6 结语