下载文档原格式
哈尔滨工程大学硕士学位论文限制性手写体字符OCR识别方法的研究姓名：杜彦蕊申请学位级别：硕士专业：信号与信息处理指导教师：郭连骐20030301哈尔滨工程大学硕＋学位论文摘要本系统的研究对象为限制性手写体字符（包括１０个阿拉伯数字和５２个英文字母的大小写，共６２个字符）。
本文研制的ＣＣ一ＯＣＲ系统完成了字符从扫描输入到计算机识别的全过程。
本文提出并实现了基于特征编码的多级分类识别方法，通过绘字符抽取足够多的有效的特征并给特征编码实现第一级分类，对于第一级分类后仍不能区分的字符，再进入第二级分类用模板匹配的方法最终达到区分的目的，这种方法的重点在第一级分类阶段。
实验结果表明这种基于特征编码的多级分类识别方法是可行有效的。
在预处理阶段，本系统对字符点阵进行了预处理，为以后的特征提取和识别打下了良好的基础。
在第一级分类阶段，本文提出了边沿表极值差特征、左边沿表间断特征、改进的宽度特征、针对所区分的字符在不同局部范围取交截特征的平均值与阈值比较等特征，这些特征与已有的一些特征相结合，较好的实现了在第一级分类阶段对字符的分类能力。
本系统的硬件部分由扫描仪与计算机组成，实现程序由Ｃ和ＶＣ＋＋６．０完成。
关键词：限制性手写体字符识别；光学字符识别；模式识别：特征提取哈尔滨工程大学硕士学位论文ＡＢＳＴＲＡＣＴＴｈｅｒｅｓｅａｒｃｈｏｂｊｅｃｔｏｆｔｈｉＳｓｙｓｔｅｍａｒｅｃｏｎｓｔｒａｉｎｅｄｈａｎｄｗｒｉｔｔｅｎｃｈａｒａｃｔｅｒｓ（ｉｎｃｌｕｄｉｎｇ１０ＡｒａｂｉｃｎｕｍｅｒａｌＳ，２６ｃａｐｉｔａｌＥｎｇｌｉｓｈｌｅｔｔｅｒｓａｎｄ２６ｓｍａｌｌＥｎｇ］ｉｓｈｌｅｔｔｅｒｓ，６２ｃｈａｒａｃｔｅｒｓａｇｇｒｅｇａｔｅｌｙ）．ＴｈｅＣＣ—ＯＣＲｓｙｓｔｅｍｄｅｖｅｌｏｐｅｄｂｙｔｈｅａｕｔｈｏｒｃａｎｃｏｍｐｌｅｔｅｔｈｅｐｒｏｃｅｓｓｆｒｏｍｔｈｅｃｈａｒａｃｔｅｒｓｓｃａｎｉｎｐｕｔｔｏｔｈｅｃｏｍｐｕｔｅｒｒｅｃｏｇｎｉｔｉｏｎ．ＴｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｂｒｉｎｇｓｆｏｒｗａｒｄａｎｄｒｅａｌｉｚｅｓｔｈｅｍｕｌｔｉｌｅｖｅｌＣ１ａＳＳｉｆｉａｂｌｅｍｅｔｈｏｄｗｈｉｃｈｉＳｂａｓｅｄｏｎｃｈａｒａｃｔｅｒｓｃｏｄｉｎｇ．Ａｂｏｖｅａ１１，ｔｈｉＳｍｅｔｈｏｄｒｅａｌｉｚｅｓｔｈｅｆｉｒｓｔ—ｇｒａｄｅＣｌａｓｓｉｆｉｃａｔｉｏｎｂｙｅｘｔｒａｃｔｉｎｇｅｎｏｕｇｈｅｆｆｅｃｔｉｖｅｃｈａｒａｃｔｅｒｓｆｒｏｍｃｈａｒａｃｔｅｒｓａｎｄｃｏｄｉｎｇｔｈｅｍ，ｔｏｔｈｅｏｔｈｅｒｓｗｈｉｃｈｃｏｕｎｄｎ’ｔｂｅｒｅｃｏｇｎｉｚｅｄｂｙｔｈｅｆｉｒｓｔ—ｇｒａｄｅｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｔｈｅｍｅｔｈｏｄｗｉ儿ａｄｏｐｔｔｈｅｓｅｃｏｎｄ—ｇｒａｄｅｃｌａｓｓｉｆｉｃａｔｉｏｎｕｓｉｎｇｔｅｍｐｌａｔｅｍａｔｃｈｊｎｇｔｏｒｅｃｏｇｎｉｚｅｔｈｅｓｅｃｈａｒａｃｔｅｒｓ．ＴｈｅｅｍｐｈａｓｉｓｏｆｔｈｉＳｍｅｔｈｏｄｓｔａｎｄｓｏｎｔｈｅｆｉｒｓｔ—ｇｒａｄｅｃｌａｓｓｉｆｉｃａｔｉｏｎｐｈａｓｅ．ＴｈｅｅｘｐｅｒｉｍｅｎｔｐｒｏｖｅｓｔｈａｔｔｈｉＳｍｅｔｈｏｄｉＳｆｅａｓｉｂｌｅａｎｄｅｆｆｅｃｔｉｖｅ．Ｉｎｔｈｅｐｒｅ—ｐｒｏｃｅｓｓｉｎｇｐｈａｓｅ，ｅａｃｈｃｈａｒａｃｔｅｒｉＳｆｅｄｉｎｔｏａｐｒｅ—ｐｒｏｃｅｓｓｏｒ，ｔｈｉＳｍａｋｅｓｆｅａｔｕｒｅｅｘｔｒａｃｔｉｏｎａｎｄｒｅｃｏｇｎｉｔｉｏｎｅａｓｙ．Ｉｎｔｈｅｆｉｒｓｔ—ｇｒａｄｅｃｌａｓｓｉｆｉｃａｔｉｏｎｐｈａｓｅ，ｔｈｅｄｉｓｓｅｒｔａｔｉｏｎｐｕｔＳｆｏｒｗａｒｄｂｏｒｄｅｒ－ｔａｂｌｅｓｕｂｔｒａｃｔｏｆｍａｘｉｍｕｍａｎｄｍｉｎｉｍｕｍｆｅａｔｕｒｅ、］ｅｆｔ—ｂｏｒｄｅｒ—ｔａｂｌｅｉｎｔｅｒｍｉｓｓｉｏｎｆｅａｔｕｒｅ、ｉｍｐｒｏｖｉｎｇｗｉｄｔｈｆｅａｔｕｒｅ、ｃｒｏｓｓｉｎｇａｍｏｕｎｔａｖｅｒａｇｅｆｅａｔｕｒｅ，ｔｈｅｓｅｆｅａｔｕｒｅｓｃｏｍｂｉｎｅｓｗｉｔｈｓｏｍｅｅｘｉｓｔｉｎｇｆｅａｔｕｒｅｓ，ｒｅａｌｉｚｅｓｔｈｅａｈｉｌｉｔｙｏｆｃｌａｓｓｉｆｉｅａｔｉｏｎｉｎｔｈｅｆｉｒａｔ—ｇｒａｄｅｃｌａｓｓｉｆｉｃａｔｉｏｎｐｈａｓｅｂｅｔｔｅｒ．ＴｈｉＳｓｙｓｔｅｍｉＳｃｏｍｐｏｓｅｄｏｆｓｃａｎｎｅｒａｎｄｃｏｍｐｕｔｅｒ．ＴｈｉＳｐｒｏｇｒａｍｉＳｃｏｍｐｌｅｔｅｄＵＳｉｎｇＣａｎｄＶＣ＋＋６．０．Ｋｅｙｗｏｒｄｓ：ｃｏｎｓｔｒａｉｎｅｄｈａｎｄｗｒｉｔｔｅｎｃｈａｒａｃｔｅｒｒｅｃｏｇｎｉｔｉｏｎ：ＯＣＲ（ＯｐｔｉｃａｌＣｈａｒａｃｔｅｒＲｅｃｏｇｎｉｔｉｏｎ）：ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ：ｆｅａｔｕｒｅｅｘｔｒａｃｔｉｏｎ哈尔滨ｊ二程入学硕士学位论文第ｌ章绪论１．１ＯＯＲ系统研究的意义８０年代以来，随着计算机在各行各业和社会生活各个方面的广泛应用以及计算机网络的高速发展，我们所生活的社会进入了信息技术不断发展的时代。
西交《Java语⾔》在线作业⼀、单选题（共 10 道试题，共 20 分。
）V 1. 哪个关键字可以对对象加互斥锁？( )A. transientB. synchronizedC. serializeD. static满分：2 分2. 对⽅法main的第1⾏定义正确的是（）。
A. public main( String arg [ ] )B. public void main( String arg [ ] )C. public static void main( String arg [ ] )D. public static void main( String args [ ] )满分：2 分3. 下列哪些语句关于内存回收的说明是正确的? ( )A. 程序员必须创建⼀个线程来释放内存；B. 内存回收程序负责释放⽆⽤内存C. 内存回收程序允许程序员直接释放内存D. 内存回收程序可以在指定的时间释放内存对象满分：2 分4. 运⾏下列程序, 会产⽣什么结果public class X extends Thread implements Runable{ public void run(){System.out.println("this is run()"); } public static void main(String args[]) { Thread t=new Thread(new X()); t.start(); } } ( )A. 第⼀⾏会产⽣编译错误B. 第六⾏会产⽣编译错误C. 第六⾏会产⽣运⾏错误D. 程序会运⾏和启动满分：2 分5. 看以下程序：boolean a=false; boolean b=true; boolean c=(a&&b)&&(!b)；int result=c==false?1:2; 这段程序执⾏完后，c与result的值是：（）。
当你提到“调用fill方法必须使用模板”，我猜测你可能是在谈论某种编程上下文，特别是在处理文件、数据填充或模板化的内容时。
在很多编程语言和库中，当你想要根据某种模板填充数据时，确实需要指定一个模板。
模板通常提供一种占位符或结构，你可以基于这些占位符或结构来填充实际的数据。
例如，在Python的`fill`方法中，如果你正在处理一个表格或数据结构，你可能需要一个列表或数组来指定要填充的数据。
这里有一个简单的例子来说明这个概念：
```python
# 假设我们有一个模板列表
template = ['Name', 'Age', 'City']
# 我们可以使用实际的数据来填充这个模板
data = ['Alice', 25, 'New York']
# 使用zip函数来填充模板
filled_template = list(zip(template, data))
print(filled_template) # 输出: [('Name', 'Alice'), ('Age', 25), ('City', 'New York')]
```
在这个例子中，`template`是我们的模板，而`data`是我们想要填充到模板中的实际数据。
我们使用`zip`函数来匹配模板和数据，并得到一个填充后的模板列表。
当然，具体的实现和上下文可能会有所不同。
如果你能提供更多的详细信息或代码示例，我会更乐意为你提供更具体的帮助。
628IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 2, FEBRUARY 2006Channel Combining and Splitting for Cutoff Rate ImprovementErdal Arıkan, Senior Member, IEEEAbstract—The cutoff rate 0 ( ) of a discrete memoryless channel (DMC) is often used as a figure of merit alongside the is split into two possibly channel capacity ( ). If a channel correlated subchannels 1, 2 , the capacity function always satisfies ( 1 ) + ( 2 ) ( ), while there are examples for which 0 ( 1 ) + 0 ( 2 ) 0 ( ). The fact that cutoff rate can be “created” by channel splitting was noticed by Massey in his study of an optical modulation system. This paper gives a general framework for achieving similar gains in the cutoff rate of arbitrary DMCs by methods of channel combining and splitting. The emphasis is on simple schemes that can be implemented in practice. We give several examples that achieve significant gains in cutoff rate at little extra system complexity. Theoretically, as the complexity grows without bound, the proposed framework is capable of boosting the cutoff rate of a channel to arbitrarily close to its capacity in a sense made precise in the paper. Apart from Massey’s work, the methods studied here have elements in common with Forney’s concatenated coding idea, a method by Pinsker for cutoff rate improvement, and certain coded-modulation techniques, namely, Ungerboeck’s set-partitioning idea and Imai–Hirakawa multilevel coding; these connections are discussed in the paper. Index Terms—Channel combining, channel splitting, coded modulation, concatenated coding, cutoff rate, error exponent, multilevel coding, random-coding exponent, reliability exponent, set partitioning, successive cancellation decoding.1) Nonnegativity. and if (iff) i.e.,with equality if and only are conditionally independent given ,2) Monotonicity in the first ensemble. with equality iff and are conditionally independent given , i.e., 3) Monotonicity in the second ensemble. with equality iff and are conditionally independent given , i.e., 4) If i.e., and are independent, thenI. INTRODUCTIONMutual information has two other important properties: sym, and chain rule (additivity), metry, . For the function, neither holds in general. Lack of additivity means that for either inequality (1) there exists an example satisfying that inequality strictly. We will give such examples in the next subsection. The main motivation for this paper is to demonstrate that the possibility of can be used to gain significant advantages in coding and modulation. For the most part, we will consider discrete memoryless chanto denote a discrete memoryless nels. We write channel (DMC) with input alphabet , output alphabet , and that output is received transition probability is sent. For such a DMC , let be a given that input . probability distribution on , and let The cutoff rate of under input distribution is defined as . The cutoff rate of is defined asTHE cutoff rate function for any pair of discrete random with a joint distribution (denoted variables in the sequel) is defined asand for any three random variables, as(All logarithms are to the base throughout.) The function shares many properties of the mutual informationlisted as follows.Manuscript received April 27, 2004; revised October 20, 2005. The material in this paper was presented at the 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, September 2005. The author is with the Electrical–Electronics Engineering Department, Bilkent University, Ankara, TR-06800 Turkey (e-mail: arikan@ee.bilkent. edu.tr). Communicate by A. E. Ashikhmin, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2005.862081A. Lack of Chain Rule for the Cutoff Rate We give two examples showing that no general inequality exists between the left- and right-hand sides of (1). The first example is derived from Massey’s work [1] and illustrates in a simple fashion the main goals of the present paper. In a study of0018-9448/$20.00 © 2006 IEEEARIKAN: CHANNEL COMBINING AND SPLITTING FOR CUTOFF RATE IMPROVEMENT629Fig. 1. Relabeling and splitting of a QEC into two correlated BECs.Fig. 2. Two coding alternatives over the QEC.coding and modulation for an optical communication system, Massey showed that splitting a given channel into correlated subchannels may lead to an improvement in the sum cutoff rate. He modeled the optical communication channel as an -ary erasure channel and considered splitting the -ary channel into binary erasure channels (BECs). The following example shows . This same example was also disMassey’s idea for cussed in [2] to illustrate some unexpected behavior of cutoff rates. Example 1 (Massey [1]): Consider the quaternary erasure channel (QEC), shown on the left in Fig. 1, and relabel its inputs and outputs to obtain the channel where , , andcutoff rates. The first alternative is the ordinary coding of the QEC as a single-user channel. The second is the independent and , ignoring the correcoding of the component BECs lation between the two subchannels. The capacity and cutoff rate and of an -ary erasure channel are given by , respectively, for any . It , i.e., the capacity of the follows that QEC is not degraded by splitting it into two BECs. On the other hand, it is easily verified and shown in Fig. 3 that the cutoff rate . is improved by splitting, i.e., Massey’s example shows that the left-hand side in (1) may be strictly smaller than the right-hand side. To see this, define an ensemble where is the uniform distribution on , and verify thatwhere is the erasure probability. The QEC can , , as be decomposed into two BECs: shown on the right in Fig. 1. In this decomposition, a transition over the QEC is viewed as two transitions, and , taking place on the respective component channels, withand Implications of the possibility that cutoff rate can be “created” will be discussed shortly. We complete this subsection by giving an example for the reverse inequality in (1). Example 2: Let , where , and or otherwise.These BECs are fully correlated in the sense that an erasure occurs either in both or in none. We now compare the two coding alternatives for the QEC that are shown in Fig. 2 in terms of their respective capacities and630IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 2, FEBRUARY 2006to achieve arbitrarily reliable communication on any DMC at rates arbitrarily close to the cutoff rate while keeping the average computation per decoded digit bounded by a constant that depends on the code rate, the channel , but not on the desired level of reliability. If the desired rate is between and channel capacity , sequential decoding can still achieve arbitrarily reliable communication but the average computation becomes arbitrarily large as well. Proofs of these results can be found in the textbooks [7]–[9]. If we consider using sequential decoders in the two coding alternatives in Fig. 2, the achievable sum cutoff rate by the second alternative exceeds that by the first, since BEC QEC for allFig. 3. Capacity and cutoff rate for the splitting of a QEC.The channelmay be thought of as consisting of two BECs , , where each has erasure probability . Subchannels and are correlated since an erasure occurs either in one or the other but never in both. is achieved by the uniform distribution on and . On the other hand, we haveThis improvement comes at negligible extra system complexity, if any. apApart from its significance in sequential decoding, pears in the union bound on the probability of error for coding and modulation systems [7, p. 396], and hence, serves as a simple measure of reliability. This issue is connected to the to the channel reliability exponent, and will be relation of discussed in detail in Section VII. C. Outline This paper addresses the following questions raised by Massey’s example. Can any DMC be split in some way to achieve coding gains as measured by improvements in the cutoff rate? And, if so, what are the limits of such gains? We address these questions in a framework where channel combining prior to splitting is allowed. In Massey’s example there is no channel combining; a given channel is simply split into two subchannels. In general, however, it may not be possible to split a given channel into subchannels so as to obtain a gain in the cutoff rate. By applying channel combining prior to splitting, we manufacture large channels which can be more readily split to yield cutoff rate gains. In fact, we show that the cutoff rate of a given DMC can be improved all the way to in the limit of combining an arbitrarily large its capacity number of independent copies of . An outline of the rest of the paper follows. In Section II, we describe the general framework for cutoff rate improvement. Section III demonstrates the effectiveness of the proposed framework by giving two very simple examples in which the cutoff rates of BECs and BSCs are improved significantly. Section IV explores the limits of practically achievable cutoff rate gains by combining a moderately large number of BSCs based on some ad hoc channel combining methods. Section V exhibits Pinsker’s method [10] as a special case of the method presented in Section II, thus establishing that the cutoff rate of any DMC can be boosted to as close to channel capacity as desired. (Unfortunately, this is an asymptotic result with no immediate practical significance.) In Section VI, we give an example that illustrates the common elements of the channel splitting method and coded-modulation schemes. In Section VII, we show that channel splitting may be used to improve the reliability–complexity tradeoff in maximum-likelihood (ML) decoding. Section VIII concludes the paper with a summary and discussion.Thus, this is an example where the sum cutoff rate is worsened . This example also by splitting, shows that the left-hand side in (1) may be strictly greater than the right-hand side. This can be seen by considering the enwhere semble is the uniform distribution on , and verifying thatandIn both of the above examples, the erasure events in the suband are fully corchannels related; the correlation is positive in the first, negative in the second. This vaguely suggests that, in order to obtain cutoff rate gains, one should seek to split a given channel into subchannels in such a way that the noise levels in subchannels are positively correlated. B. Significance of the Cutoff Rate Channel cutoff rate has long been used as a figure of merit for coding and modulation systems and this has been justified in well-known works, such as [3] and [4]. Here, we summarize as a figure of merit. the argument in favor of using One reason for the significance of stems from its role in connection with sequential decoding, which is a decoding algorithm for tree codes invented by Wozencraft [5], with important later contributions by Fano [6]. Sequential decoding can be usedARIKAN: CHANNEL COMBINING AND SPLITTING FOR CUTOFF RATE IMPROVEMENT631The present work is tied to previous work along many threads. We have already mentioned Massey’s work [1] as the main starting point. There is also a close similarity to techniques employed in coded modulation and multilevel coding as represented by the pioneering works of Ungerboeck [11], [12] and Imai–Hirakawa [13]. Finally, the present work is connected through Pinsker’s serial concatenation approach [10] to iterative coding methods that date back to Elias [14]. Concatenated coding in general is a well-known technique for improving the reliability–complexity tradeoff in coding, and it is pertinent to cite Forney’s seminal work on the subject [15] and important later works [16], [17] as part of the broader background for the present paper. Notation: We write to denote the vector for . If , denotes a void vector. any II. CHANNEL COMBINING AND SPLITTING In order to seek coding gains in the spirit of Massey’s exfor ample, we will consider DMCs of the form . Such a channel may have been obtained some integer by labeling the input and output symbols of a given channel by vectors, as in Massey’s example. Typically, such a channel will be obtained by combining independent copies of a given , as shown in Fig. 4. We incorporate into the DMC channel combining procedure a bijective label mapping func. Relabeling of the inputs of (the tion channel that consists of independent uses of ) is an essential ingredient of the proposed method; without such a relabeling, there would be no gain. The resulting channel is a DMC such thatFig. 4. Channel combining and input relabeling.where . Whatever the origin of the channel , we regard as a channel with input terminals where each terminal is into encoded by a different user. We will consider splitting subchannels by using the coding system shown in Fig. 5 where a type of decoder known variously as a successive cancellation decoder or a multilevel decoder is employed. The latter term is more common in the coded-modulation literature [13]. We will adopt the former term in the sequel since the context here is broader than modulation. The decoder in a successive cancellation system is designed around a random code ensemble for channel , specified by a random vector , where is a prob. Roughly, corresponds ability distribution on , to the input random variable that is transmitted at the th input terminal. Given such a reference ensemble, we define DMCs , , so that, which it transmits at input terminal , . The codeword length is assumed to be the same for all users to simplify the description; in general, each user may have a different codeword length. The messages are assumed independent. Decoder 1 observes the channel output vector where is the output of the th copy of at time , of , and also an estimate and generates its estimate of . It puts out as its decision, and feeds to all succeeding decoders to help them with their decoding tasks. This first decoder knows only the code , in effect, used by encoder 1 and uses the channel model at time at other input modeling the inputs terminals as generated by a memoryless source from the , . (In case the distribution users employ tree coding with certain truncation periods, each user is assumed to be aware of the position and identity of the truncation symbols used by each succeeding user and to modify the channel model accordingly.) In general, decoder observes and proceeds to generate an estimate of and an estimate of using the channel model . The is sent out, while is passed to the succeeding estimate decoders. This successive cancellation system provides the general framework in which we will consider channel combining and splitting methods. We will assume that the decoders in the system are sequential decoders and use the sum cutoff rate as the criterion for measuring coding gains. By standard random-coding arguments for tree codes and sequential decoding, one may show that an ensemble average error probability as small as desired can be achieved while still ensuring that the average decoding complexity per decoded symbol is bounded by a constant provided that encoder operates at a rate , . Thus, the sum rate achievable by such a scheme is given by .The th decoder in the system will use as its channel model in carrying out the decoding task. The precise operation of the successive cancellation system into a vector is as follows. User encodes a message632IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 2, FEBRUARY 2006Fig. 5.Channel splitting by successive cancellation.Note that equals , which in since and are indeturn equals pendent. So, the sum cutoff rate for the preceding scheme normalized by the number of channels isWe will speak of a coding gain if is greater than , the ordinary cutoff rate of the elementary channel . It may be of interest to consider also the cutoff rate for the channel , namelyFig. 6. Synthesis of a quaternary input channel from two binary-input channels.where the maximum is over all , not necessarily in product form. The rate is the supremum of achievable rates by a single sequential decoder that decodes all inputs jointly, with no restriction that different inputs of are encoded independently. Gallager’s “parallel channels theorem” with equality iff [8, p. 149] ensures that the label map is bijective. Thus, the only possible method of achieving a coding gain as measured by the sum cutoff rate is to split the decoding function into multiple sequential decoders. The splitting of the encoder plays an incidental role in improving the sum cutoff rate by facilitating the use of multiple sequential decoders in a successive cancellation configuration. III. BEC AND BSC EXAMPLES In this section, we give an immediate application of the method outlined in the preceding section to the BEC and BSC. The main point of this section is to illustrate that by combining just two copies of these channels one can obtain significant improvements in the cutoff rate. be the BEC with alExample 3 (BEC): Let , , and erasure probability phabets . Consider combining two copies of to obtain a channel as shown in Fig. 6. The label map is given bywhere denotes modulo- addition. Let the input variables be where , are uniform specified as . Then onA heuristic interpretation of these cutoff rates can be given by is effectively observing that user 1’s channel a BEC with erasure probability ; an or is erased. erasure occurs in this channel when either On the other hand, given that decoder 2 is supplied with the correct value of , the channel seen by user 2 is a BEC with erasure probability ; an erasure occurs only when both and are erased. The normalized sum cutoff rate under this scheme is given bywhich is to be be compared with the ordinary cutoff rate of the BEC, . These cutoff rates are shown in Fig. 7. The figure shows and it can be verified analytically that . the above method improves the cutoff rate for all and the labeling given We note that the distribution of above are optimal in the sense that it maximizes . This can be verified by exhaustively trying all possibilities for . In order to achieve higher coding gains, one needs to combine a larger number of copies of the BEC.ARIKAN: CHANNEL COMBINING AND SPLITTING FOR CUTOFF RATE IMPROVEMENT633Fig. 7.Cutoff rates for the splitting of BEC.Fig. 8. Cutoff rates for the splitting of BSC.Example 4 (BSC): Let andbe a BSC withIV. LINEAR LABEL MAPS In the previous section, we have shown that there exist linear that improve the sum cutoff rate. In label maps of order this section, we give higher order linear label maps that attain further improvements. Throughout the section, we restrict atten. tion to a BSC with a crossover probability We consider combining copies of a BSC as in Fig. 4 using where a label map that is linear. Thus, we set is a full-rank matrix of size . The output of the combined has the form where is the channel channel noise vector with independent and identically distributed (i.i.d.) components. For capacity and cutoff rate calculations, we use an input consisting of i.i.d. components, each component ensemble equally likely to take the values and . This defines a joint enwhere is the channel input and semble the channel output. We consider a successive cancellation decoder as in Fig. 5. Note that each decoder observes the entire channel output vector and can compute the vector . We denote the th column of by , so we have , . For decoder 1, which is interested in recovering only, a sufficient statistic is the first component of , namely If the number of ’s in equals , then the channel is the cascade of independent BSCs, and is itself a BSC with a crossover probabilityfor all , . Assume the BSC is given by. The cutoff rate ofwhere for . Combine two copies of the BSC as in Fig. 6 to obtain the and define the input variables channel where , are uniform on . The cutoff rates and can be obtained by direct calculation; however, it is instructive to obtain them by the following argument. The input and output variables of the are related by channelwhere and are independent noise terms taking the values and with probabilities and , respectively. Notice that is a sufficient statistic for decoder 1, whose goal is to estimate . Thus, the channel that decoder 1 sees is, in effect, , which is a BSC with crossover probability and has cutoff rate Next, note that the channel of , is equivalent to the channel which is a BSC with diversity order , given the knowledgeand has cutoff rateThus, the normalized sum cutoff rate with this splitting scheme is given byThe cutoff rate of this channel equals , and is given in in Fig. 9 as a function of for various . is supplied to deSupposing that the correct value of coder 2, that decoder in turn can compute the left-hand sides of the two equationswhich is larger than Fig. 8.for all, as shown in634IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 2, FEBRUARY 2006Fig. 9. Cutoff rate for the cascade of k probability per BSC.= 1; . . . ; 10BSCs versus the crossoverFig. 10.Capacity and cutoff rates for Example 5.which form sufficient statistics for estimating . This channel . In general, has cutoff rate have been supplied to decoder , , supposing that decoder computes the sufficient statistics . . .from which it tries to decode . This is a channel where is observed through two independent BSCs each with crossover and has cutoff rate probabilityGiven that both the channelandare available to decoder 3, it hasand estimates, achieving a cutoff rateThe following example illustrates the above method. Example 5: SupposeBy adding the third equation to the first and second, we see that this is a channel where the variable is observed through three channels, each of which is a BSC with crossover probability ; however, in this instance, the channels are not independent. The can still be computed readily. cutoff rate Finally, given , decoder 4 has the channelThis matrix equals its inverse has the channel. Thus, the first decoder or, equivalentlyThis is a BSC with crossover probability and has cutoff rate where is as defined before. Supposing that is decoded correctly and passed to the second decoder, decoder 2 has the channelThis is a channel where BSCs, andis observed through four independentor, alternatively, by adding the second equation to the firstThe normalized sum cutoff rate is plotted in Fig. 10 as a function of ; also shown in the figure are the cutoff and capacity of the raw BSC. There is a visible rate improvement in the sum cutoff rate compared to the scheme inARIKAN: CHANNEL COMBINING AND SPLITTING FOR CUTOFF RATE IMPROVEMENT635Example 4 and the gap between and is roughly half-way . closed for This improvement in cutoff rate is achieved at the expense of somewhat increased system complexity. One element of complexity for a successive cancellation decoder is the size of the transition probability matrices at each level. This matrix is needed to compute the likelihood ratios in ML decoding or the metric values in sequential decoding. In this example, the channel at level , , has two inputs and outputs; the entries. corresponding transition probability matrix has In general, the storage complexity of these matrices grows exponentially in the number of channels combined, and sets a limit on practical applicability of the method for large . A. Kronecker Powers of a Given Labeling The linear map where in the above example has the formFig. 11. Rate allocation for Example 6.is the linear map used in Example 4. We have also carried out cutoff rate calculations for linear maps of the form for at a fixed raw error probability . The resulting normalized sum cutoff rates are listed in the following table. For comparison, the cutoff rate and capacity of the BSC are and . atThe th “syndrome subchannel” (3) is a BSC with crossover probability where is the number of ’s in the th row of . The remaining subchannels, which we call “information subchannels,” have the formThe motivation for the above method is to make use of linear block codes with good distance properties to improve the sum cutoff rate. The following example illustrates the method. Example 6 (Dual of the Golay Code): Let , , and be as in (2) withThe scheme with has subchannels. The equals . number of possible values of the output vector The rapid growth of this number prevented computing for . B. Label Maps From Block Codes be the generator matrix, in systematic form, Let linear binary block code . Here, is a of an matrix and is the -dimensional identity matrix. A linear label map is obtained by setting (2) Note that has full rank and . Also note that the columns of form the transpose of a parityfirst for . Thus, when the receiver check matrix computes the vector the first where coordinates of have the form (3) is the th element of the syndrome vectorThe code with the generator matrix is the dual of the Golay code [18], [19, p. 119]. We computed the normalized at for this sum cutoff rate scheme. The rate allocation vectoris shown in Fig. 11. There is a jump in the rate allocation vector in going from the syndrome subchannels to information subchannels, as may be expected. Finally, it may be of , we obtain interest that, for the Golay code with , which is worse than the performance achieved by the dual code. It is natural to ask at this point whether linear label maps can achieve normalized sum cutoff rates arbitrarily close to channel capacity in the limit as goes to infinity. The next section shows that this is indeed possible.636IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 52, NO. 2, FEBRUARY 2006Fig. 12.Bit mapping for 4-PAM.V. PINSKER’S SCHEME In this section, we show that the general framework of Section II admits Pinsker’s method as a special case. This section will also help explain the relation of the present work to concatenated coding schemes in general. In a theoretical study of coding complexity, Pinsker [10] combined the idea of sequential decoding and Elias’ method of iterative coding [14] to prove that the cutoff rate of any DMC could be boosted to as close to channel capacity as desired. Pinsker’s method is a form of serially concatenated coding where an inner block code is combined with an outer sequential decoder. For simplicity, we describe Pinsker’s method for the case of . Let a BSC with a crossover probability and denote, respectively, the cutoff rate and capacity of a BSC with crossover probability , and note that as . The encoding in Pinsker’s scheme follows the method of Secand a tion IV-B. A systematic block code with rate is chosen and a linear map is generator matrix formed as in (2). The decoder in Pinsker’s scheme is a simplified form of the successive cancellation decoder where the decoders work completely independently, with no exchange of decisions. This is made possible by using a step-function-type rate allosuch that cation vector and where is to be specified. and there is no need to decode the syndrome Thus, , comchannels. The decoder at stage , putes the vector as in (3), which directly reveals the synsince by construction. Thus, each drome vector such decoder can independently implement the ML decoding rule using a syndrome decoding table. This creates binary channels , , where denotes the estimate of obtained from the syndrome decoding table. By well-known coding theorems, there are codes for which can be made arbitrarily the the probability of error small by using a sufficiently large , provided that is kept bounded away from . (In fact, goes to zero exponentially in for optimal codes.) Thus, the cutoff rate under the of each information subchannel, given by independent decoding scheme described here, goes to . , we can choose To summarize, asymptotically as arbitrarily close to and arbitrarily close to , resulting in an overall coding rate arbitrarily close to . This completes Pinsker’s argument for improving the cutoff rate to channel capacity limit. Clearly, Pinsker’s argument is designed to give the proof of a theoretical point in the simplest possible form, with no attention to asymptotically insignificant details. In a nonasymptotic setting, the performance of the sequential decoders in Pinsker’s scheme can be improved if the decoder at stage , , calculates the soft-decision statisticsFig. 13.Cutoff rates versus noise variance in 4-PAM.instead of the hard decisions obtained from the syndrome decoder. The calculation of the soft-decision statistics may be performed by applying the Bahl–Cocke–Jelinek–Raviv (BCJR) algorithm [20] to a trellis description of the block code . In closing this section, we would like to mention Falconer’s work [21], where another method is given for boosting the sum cutoff rate to near channel capacity. Falconer’s method uses multiple inner sequential decoders and an outer Reed–Solomon code, and it does not fit into the framework considered in this paper. Neither Pinsker’s method nor Falconer’s appear to have had much impact on coding practice because of their complexity. VI. RELATION TO CODED MODULATION The channel combining and splitting method presented in the preceding sections has common elements with well-known coded-modulation techniques, namely, Imai and Hirakawa’s [13] multilevel coding scheme and Ungerboeck’s [11], [12] set-partitioning idea. To illustrate this connection, we give the following example where the cutoff rate of a pulse-amplitude modulation (PAM) scheme is improved through channel splitting. Example 7 (4-PAM): Consider a 4-PAM scheme over a memoryless additive Gaussian noise channel so that in each is transmitted and use of the channel a symbol is received where is Gaussian with mean zero and variance . In order to split this channel into two subchannels, as in the channel input is relabeled by a pair of bits . Fig. 12 so that We consider an input ensemble so that , are indepen. dent and each takes the values and with probability . The channel input ensemble is then uniform over , , Fig. 13 shows the resulting cutoff rates。
参考文献(人工智能)曹晖目的：对参考文献整理（包括摘要、读书笔记等），方便以后的使用。
分类：粗分为论文（paper）、教程（tutorial）和文摘（digest）。
0介绍 (1)1系统与综述 (1)2神经网络 (2)3机器学习 (2)3.1联合训练的有效性和可用性分析 (2)3.2文本学习工作的引导 (2)3.3★采用机器学习技术来构造受限领域搜索引擎 (3)3.4联合训练来合并标识数据与未标识数据 (5)3.5在超文本学习中应用统计和关系方法 (5)3.6在关系领域发现测试集合规律性 (6)3.7网页挖掘的一阶学习 (6)3.8从多语种文本数据库中学习单语种语言模型 (6)3.9从因特网中学习以构造知识库 (7)3.10未标识数据在有指导学习中的角色 (8)3.11使用增强学习来有效爬行网页 (8)3.12★文本学习和相关智能A GENTS：综述 (9)3.13★新事件检测和跟踪的学习方法 (15)3.14★信息检索中的机器学习——神经网络，符号学习和遗传算法 (15)3.15用NLP来对用户特征进行机器学习 (15)4模式识别 (16)4.1JA VA中的模式处理 (16)0介绍1系统与综述2神经网络3机器学习3.1 联合训练的有效性和可用性分析标题：Analyzing the Effectiveness and Applicability of Co-training链接：Papers 论文集\AI 人工智能\Machine Learning 机器学习\Analyzing the Effectiveness and Applicability of Co-training.ps作者：Kamal Nigam, Rayid Ghani备注：Kamal Nigam (School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, knigam@)Rayid Ghani (School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 rayid@)摘要：Recently there has been significant interest in supervised learning algorithms that combine labeled and unlabeled data for text learning tasks. The co-training setting [1] applies todatasets that have a natural separation of their features into two disjoint sets. We demonstrate that when learning from labeled and unlabeled data, algorithms explicitly leveraging a natural independent split of the features outperform algorithms that do not. When a natural split does not exist, co-training algorithms that manufacture a feature split may out-perform algorithms not using a split. These results help explain why co-training algorithms are both discriminativein nature and robust to the assumptions of their embedded classifiers.3.2 文本学习工作的引导标题：Bootstrapping for Text Learning Tasks链接：Papers 论文集\AI 人工智能\Machine Learning 机器学习\Bootstrap for Text Learning Tasks.ps作者：Rosie Jones, Andrew McCallum, Kamal Nigam, Ellen Riloff备注：Rosie Jones (rosie@, 1 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213)Andrew McCallum (mccallum@, 2 Just Research, 4616 Henry Street, Pittsburgh, PA 15213)Kamal Nigam (knigam@)Ellen Riloff (riloff@, Department of Computer Science, University of Utah, Salt Lake City, UT 84112)摘要：When applying text learning algorithms to complex tasks, it is tedious and expensive to hand-label the large amounts of training data necessary for good performance. This paper presents bootstrapping as an alternative approach to learning from large sets of labeled data. Instead of a large quantity of labeled data, this paper advocates using a small amount of seed information and alarge collection of easily-obtained unlabeled data. Bootstrapping initializes a learner with the seed information; it then iterates, applying the learner to calculate labels for the unlabeled data, and incorporating some of these labels into the training input for the learner. Two case studies of this approach are presented. Bootstrapping for information extraction provides 76% precision for a 250-word dictionary for extracting locations from web pages, when starting with just a few seed locations. Bootstrapping a text classifier from a few keywords per class and a class hierarchy provides accuracy of 66%, a level close to human agreement, when placing computer science research papers into a topic hierarchy. The success of these two examples argues for the strength of the general bootstrapping approach for text learning tasks.3.3 ★采用机器学习技术来构造受限领域搜索引擎标题：Building Domain-specific Search Engines with Machine Learning Techniques链接：Papers 论文集\AI 人工智能\Machine Learning 机器学习\Building Domain-Specific Search Engines with Machine Learning Techniques.ps作者：Andrew McCallum, Kamal Nigam, Jason Rennie, Kristie Seymore备注：Andrew McCallum (mccallum@ , Just Research, 4616 Henry Street Pittsburgh, PA 15213)Kamal Nigam (knigam@ , School of Computer Science, Carnegie Mellon University Pittsburgh, PA 15213)Jason Rennie (jr6b@)Kristie Seymore (kseymore@)摘要：Domain-specific search engines are growing in popularity because they offer increased accuracy and extra functionality not possible with the general, Web-wide search engines. For example, allows complex queries by age-group, size, location and cost over summer camps. Unfortunately these domain-specific search engines are difficult and time-consuming to maintain. This paper proposes the use of machine learning techniques to greatly automate the creation and maintenance of domain-specific search engines. We describe new research in reinforcement learning, information extraction and text classification that enables efficient spidering, identifying informative text segments, and populating topic hierarchies. Using these techniques, we have built a demonstration system: a search engine forcomputer science research papers. It already contains over 50,000 papers and is publicly available at ....采用多项Naive Bayes 文本分类模型。
Chapter 3. Operating SystemsMultiple Choice Questions1. Which of the following components of an operating system maintains the directory system?A. Device driversB. File managerC. Memory managerANSWER: B2. Which of the following components of an operating system handles the details associated with particular peripheral equipment?下列哪个组件的一个操作系统处理与特定的外围设备相关联的细节吗?A. Device drivers 设备驱动程序B. File managerC. Memory managerANSWER: A3. Which of the following components of an operating system is not part of the kernel?A. ShellB. File managerC. Scheduler调度器ANSWER: A4. Multitasking in a computer with only one CPU is accomplished by a technique called .多任务在计算机只有一个CPU通过一种技术被称为A. Bootstrapping 自助法B. Batch processing 成批处理C. Multiprogramming多道程序设计ANSWER: C5. Execution of an operating system is initiated by a program called the .A. Window managerB. SchedulerC. Bootstrap引导程序ANSWER: C6. The end of a time slice is indicted by the occurrence of a signal called .时间片结束时发生的一个信号A. An interruptB. A semaphore 一个信号量C. A login一个登录ANSWER: A7. A set of instructions that should be executed by only one process at a time is called .一组指令,应执行一次只有一个进程A. Utility 实用B. Critical region临界区C. Privileged instruction特权指令ANSWER: B8. Which of the following is not an attempt to provide security?A. Passwords密码B. Privilege instructionsC. Multitasking多重任务处理ANSWER: C9. Which of the following events is harmful to an operating system’s performance?A. DeadlockB. InterruptC. Booting引导启动ANSWER: A10. Which of the following is a technique for controlling access to a critical region?下列哪个技术控制访问临界区?A. Spooling 假脱机B. Time sharingC. Semaphore 信号；旗语D. BootingANSWER: C11. Which of the following is not involved in a process switch?A. InterruptB. Process tableC. Dispatcher调度程序D. ShellANSWER: D12. Which of the following is a task that is not performed by the kernel of an operating system?下列哪个是一个任务,并不是由一个操作系统的内核?A. Communicate with the userB. Schedule processes调度进程C. Allocate resources分配资源D. Avoid deadlockANSWER: A13. Which of the following components of an operating system is executed to handle an interrupt signal?A. DispatcherB. Memory managerC. File managerANSWER: AFill-in-the-blank/Short-answer Questions1. In contrast to early batch processing techniques, __A__ allows the user to communicate with the computer while the user’s application is being executed. In turn, this type of processing requires that the computer’s responses to its environment be performed in a timely manner, a requirement known as __B__.与早期的批处理技术相比,便利允许用户与计算机进行通信,用户的应用程序被执行。
