浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S)29.语言被文法生成ⅲ它是re的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题H={"M"w":M在w上停机}lH={"M"w":M是一台在"w"上不停机的TM}H1={"M":M在“M”上停机}H1={w:要么w不是一台TM的编码,要么w是M的编码,M是一台在"M"上不停机的TM}H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NPThe world as We Dont Know itreAsumming P≠APCo『eHrecursiveSATSATCO-A伊II Asumming P=Npr, eCo-r.erecursiveNP= cO-Np= p33没有算法的问题称作不可判定的or不可解的,如TM的停机问题34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的ic若L1非递归,并存在L1到L2的归约,则L2也非递归。递归函数是 Turing Computable的35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特殊状态q来枚举L,任意顺序且可重复)6.不可判定语言与递归语言互为补集,与rc语言有交集。37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P39.H={M"wM在最多2w步后停机}唾P40.所有正则语言和所有CFL都属于P41.NPA.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。B.基于 verifier的定义:NP问题上建立的非确定机包含两步1)非确定地猜一个解2〕用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP问题当且仅当存在一个多项式时间的 verifier这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的翰入是否满足,就是基于 verifier的定义。P和NP的区别a problem is in P if we can decide them in polynomial time. It is in NP if we candecide them in polynomial time, if we are given the right certificate42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项式归约44.证明NP完全法一、按定义:LΣ*,若(a)L∈NP,且(b)对每个语言L∈NP,存在从L到L的多项式归约则L称为NP完全的。法二、归约,对于语言L,(a)若L∈NP(b)一个NP完全问题可以在多项式时间规约到L,ie. SAT 0 is context-free but not regular49.L=L1L2,L是CFL,则L1一定是CFL(x50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben51. 2-way PDalie PDa whose input heads can move both left and right] are more powerfulthan 1-way pda52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable53.DFA/NFA识别的是 exactly正则语言54.Re.只在补和差下不封闭,CFL在交下也不封闭55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言56.典型非正则:w=wR57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ*58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least asdifficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到Y,记X≤Y。e.gx2可以归约到任意两数的乘积。若有A≤B,A是不可判定问题>B不可判定A不递归->B不递归B可判定>A可判定B是递归的->A是递归的59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到PRIME COMPOSITE )o62.若A≤PB,B∈NP,则A∈NP。证明A≤PB→存在确定图灵机X,可将A归约到B。B∈NP→存在一个非确定图灵机N可判定B。我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NPRunning time of X*N≤1+p(mB>+qp(m)(B多项式时间非确定判定是多项式时间所以A∈NP63若AsPB,B∈P,则A∈P64.若X是NPC的,则X在多项式时间内可解ifP=NP65.SAT多项式时间归约到3SA(3AT是NPC的)66.证明语言L是R/Re, Non rea) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re)严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈Beg1∈H,M∈L证明Recg2∈非H,iM∈L证明 Non rc注意方向:是从A的实例经过递归函数推向B的实例。详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf67.递归与μ递归等价68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下封闭69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只要不接受w,就不停机。70. Chomsky hierarchyElements of the Chomsky HierarchyRecursively enumerable languagesRecursive languageContext sensitive languagesContext ee languageseterministccontext free languagesRegularanguages71.俩证明7.6证明P在并、交、 Kleene*连接和补运算下封闭(1)并:对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab}对L1L2构造判定器MM=“对于输入字符串w1)在W上运行M1,在w上运行M22)若有一个接受则接受,否则拒绝。时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab}第一步用时0(n+n),因此总时间为Oma+n)=0(n9所以L1L2属于P类,即P在并的运算下封闭。(2)连接对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且c=max{ab}。对L1l2构造判定器MM=“对于输入字符串w=w2灬,Wn对k=0,1,21…,n重复下列步骤。在wW2…wk上运行M1,在wk1wk+2…n上运行M若都接受,则接受。否则继续。若对所有分法都不接受则拒绝。时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即P在连接的运算下封闭。对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器MM=“对于输入字符串〔1)在w上运行M12)若M1接受则拒绝,若M1拒绝则接受。时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。77证明NP在并和连接运算下封闭。1)并对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它们,且c=max{a,b}。构造判定LL2的非确定图灵机M:M=“对于输入字符串w1)在W上运行M1,在w上运行M2。2)若有一个接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所以LLz∈NP,即NP在并的运算下封闭2)连接对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它们,且c=max{ab}。构造判定L1oL2的非确定图灵机M:M=“对于输入字符串w:1〕非确定地将分成两段xy,使得w=xy。2)在x上运行M1,在y上运行M23)若都接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。专题一一图灵机可判定性问题判定以下问题是否可判定:声明:思路—想证明B问题不可解,1.从一个不可解问题A入手(如停机问题)2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了3.所以B是不可解的1.一个图灵机有至少481个状态。我们可以给出这样一个TMN进行cnc(M)a)数M中状态数,直到481b)如果达到了481,N就接受,否则拒绝2.给定图灵机在空串上走了481步还没停机。构造2带图灵机N,a)2a带:写481个0b)1s带在空串上模拟M,每走一步,第2带就删掉一个0c)如果M在所有0都删掉之后停机,则N接受,否则不接受给定图灵机,判定它是否在一些输入上经过481步还没停机?a)按字典序找出所有 length
- 2020-12-01下载
- 积分：1
风控建模一等奖
使用拍拍贷数据，建模全过程，从数据预处理开始到最后的模型比较。仅用于交流学习。队伍介绍队名“不得仰视本王”,队伍由五个小伙伴组成,我们是在一个类以的比赛(微额借款用户人品预测大赛)认识的,对数据挖掘竹热爱让我们走到了一起,以下是成员简介:姓名学校、学历比赛经历匚陈靖」中国科学技术大学研二天泡科学家总分第三,微额借贷用户人品预测大赛季军朱治亮浙江大学研二淘宝穿衣搭配比赛李军,微额借贷用户人品预测大赛李军质耀重庆邮电大学研二微额借贷用户人品预测大赛冠军匚赵蕊」重庆邮电大学研微额借贷用户人品预测大赛亚军黄伟鹏北京大学研一微额借贷用户人品预测大赛冠军解决方案概述2.1项目介绍与问题分析拍拍贷“魔镜风控系统”从平均400个数据维度评估厍户当前的信用状态,给每个告款人打出当前状态的信用分,在此基础上再结合新发标的信息,打出对于每个标约6个月内逾期率的预沨,为没资人提供关键的决策依据。本次竞赛目标是根据用户历史行为数据来颈测用户在六来6个月内是否会逾期还款的概率。问题转换成2分类问题,评估指标为AUC,从 Master, LogInfo, Update Info表中构建恃征,考虑评估指标为AUC,其本质是排序优化问题,所以我们在模型顶层融合也使用基于排序优化的 RANK AVG融合方法。2.2项目总体思路本文首先从数据清洗开始,介绍我们对缺失值的多维度处、对离群点的剔除方法以及对字符、空格等的处理;其次进行特征工程,包括对地理位置信息的特征构建、成交玉间特征、类别特征编码、组合特征构建、 Lpdatelnfo和 Log Info表的特征提取等;再次进行特征选择,我们采用了 boost, boost的训练过栏即对特征重要性的排序过程;然后处理类别的不平衡度,由于赛题数据出现了类不平衡的情况,我们采用了代价敏感学习和过采样两和方法,重点介绍我们所使用的过采样方法;最后一部分是模型设计与分析,我们采用了二业界广泛应用的逻辑回归模型、数据挖掘比赛大杀器 ghost.,创新性地揆索了large- scale sⅧm的方法在本赛题二的应用,玟得了不错的效果,此外还介绍了模型融合方、数据清洗3.1缺失值的多维度处理在征信领域,用户信总的完善程度可能会影响该层户的信用评级。一个信息完苦程度为100%的户比起完善程度为50%的用户,会更加容易官核通过并得到借款。从这一点亡发,我们对缺失值进行了多维度的分析和处理按列(属性)统计缺失值个数,进一步得到各列的缺失比率,下图(图1)显示了含有缺失值的属性和相应的缺失比率sing rate of Attributes图1.属性缺失比枣WeblogInfo_1和 WeblogInfo3的缺失值比率为97%,这两列属性基本不携带有用的信息,直接剔除。 Uscr Info_11、 Userinfo_12和 Uscr info_13的缺失值比率为63%,这三列属性是类别型的,可以将缺失值用-1垣充,相当于“是否缺失”当成另一种类别。其他缺失值比卒较小的数值型属性用中值填充按行统计每个样本的属性缺矢值个数,将缺失值个数从小到大排序,以序号为横坐标,缺失值个数为纵坐标,画出如下散点图(图2)test set16016014014C12012Cw9mczE100400060008000Order Numbe(sort ircreasinglyOrde Nt mber(sort increasing ly)图2.样本属性缺失个数对比 trainset和 testset上的样本的属性缺失值个数,可以发现其分有基本一致,但是trainset上出了几个缺失值个数特别多的样本(红框区域内),这几个样本可以认为是离群点,将其剔除另外,缺矢值个数可以作为一个特征,衡量用户信息的完善程度。3.2剔除常变量原始数据宁有190维数值型特征,通过计算每个数值型特征的标准差,剔除部分变亿很小的特征,下表(表1)列出的15个特征是标准差接近于0的,我们剔了这15维特征表1.剔除数值特征标准差属性标准差属性标准差属忾标准差Webloglnfo_10 0.0707 WeblogInfo_41 0.0212 Webloglnfo_490.0071Webloglnfo_23.0939 WeblogInfo_43 0.0372 Webloglnfo_5200512Webloglnfo_31.0828 Webloglnfo_44.0166 Webloglnfo_5400946Webloglnfo_32 0.0834 Webloglnfo_46.0290 WeblogInfo_5500331Webloglnfo_40.0666 Webloglnfo_47 0.0401 WeblogInfo_58006093.3高群点剔除在样本空间中与其他样本点的一般行为或特征不一致的点称为离群点,考虑到离群点的异常特征可能是多维度的组合,我们通过分析样本属性的缺矢值个数,剔除了极少量的离群点(见3.1节)此外,我们还采用了另外一种简单有效的方法:在原始数捶上训练ⅹ gboost,用得到的xgb模型输出特征的重要性,取最重要的前20个特征(如图3所示),统计每个栏本在这20个特征上的缺失值个数,将缺矢值个数大于10的样本作为离群点。ThrciParty Ifn PeriodIntrAparty nto HerodThrcPorty hfo Penod3ardiParty hfo Period?ThirdParty Info Penod图3.Xgb特征重要性通过这个方法,易除了400多个样水。这些样在重要特征上的取值是缺失的,会使得模型学习变得因难,从这个角度妖说,它们可以看成是离群点,应剔除掉。3.4其他处理(1)字符大小写转换Userupdate Info表宁的 Userupdate Info1字段,属性取值为英文字符,包含了大小写,如Q"和”qQ",很玥显是同一和取值,我们将所有字符统一转换为小写(2)空格符处理Mastor表中 UserInfo9字段的取值包含了空格字符,如“中国移动”和“中国移动”它们是同一种取值,需要将空格符去除。(3)城市名处理Userinfo_8包含有“重庆”、“重庆市”等取僬,它们实际上是同一个城市,需要把字符中的“市”全部去掉。去掉“市”之后,城市数由600多下降到400多。四、特征工程4.1地理位置的处理对地理位置信(类别型变量)最简单的处理方式是独热编码(one- hot encoding),但是这样会得到很高维的稀疏特征,影响糢型的学习,我们在独热编码旳基础上,做了特征选择。下面介绍具体的方法。赛题数据提供了用户的地挛位置信息,包括7个字段: Userinfo2、 Userinfo4、UserInfo7、 UserInfo8、 UserInfo I9、 UserInfo20,其中 UserInfo_7和 UserInfo19是省份信息,其余为城市信息。我们统计了每个省份和城市的违约率,下图以 Userinfo_7为例图1.省分违约率可视化图5可视化了每个省份的违约率,颜色越深代表违约率越大,其中违约率最大的几个省份或直辖市为四川、湖南、湖北、吉林、天津、山东,如下图所示:图5.违约深突出省份可视化因此我们可以构建6个二值特征:“是否为四川省”、“是否为湖南省”...“是否为山东省”,其取值为或1。其实这相当于对地理位置信息做了独热编码,然后保留其中有判别性的菜些列。这里 UserInfo_7何含32和取值,编码后可以得到32维的稀疏特征,而我们只保留其宇的6维以上我们是通过人工的分析方法去构延二值特征,在处理省份信息时还是匕较直观的,但是处理城市信息,比如 Userinfo2,包含了33个减市,就没有那么直观了。为了得到有判别性的二值特征,我们首先对 Userinfo2进行独热编码,得到333维的二值特征,然后在这333维稀疏特征上训练ⅹgb模型,再根据xgb输出的特征重要性刷选二值痔征,以下是选取到的部分二值特征(对应的城市):“淮纺市”、“九江市”、“三门峡市”、“汕头市”、“长春市”、“铁岭市”、“济菊市”、“成都市”、“淄博市”、“牡丹江市”。按城市等级合并类别型特征取值个数太多时,独热编码后得到太高维的稀疏特征,除了采用上面提到的特征选择方法外,我们还使用了合并变量的方法。按照城市等级,将类别变量合并,例如线城市北京、上海、广州、深圳合并,赋值为1,同样地,二线城市合并为2,三线城市合并为3>经纬度特征的引入以上对地理位置信息的处理,都是基于类别型的,我们另外收集了各个城市的经纬度,将城市名用经纬度替换,这样就可以将类别型的变量转化为数值型的变量,比如北京市,用经纬度(39.92,116.46)替换,得到北纬和东经两个数值型特征。加入经纬度后,线下的cross validation有千分位的提升。城市特征向量化我们将城可特征里的城市计数,并取Log,然后等值离散化到610个区间内。以下图为例,将 serino2这个特征里面的325个城市离散为一个6维向量。向量“100000”表示该城位于第一个区间。线下的 cross validation有千分位的提升。Loglui2 num)6.城市特征离散化地理位置差异特征如图8所示,1,2,1,6列郗是城市。那么我们构建一个城市差异的特征,比妇diff_12表示1,2列的城市是否相同。如此构建 diff l2,diff_14,diff_l6,diff_24,diff26,diff46这6个城市差异的特征。线下的 cross validation有千分位的提升。⊥aJse⊥nfa2 userinfo4 Userinfo7 Userinfo8 Userinfo19uer⊥nf。201C013郴州1C020惠州1C033零1c035深圳东东东东建东福建省10038济104连云港远言港带1C042德州1c043青岛聊拔东自聊城市46深圳汕广东广东省汕尾市105所多工新乡图7.地理位置差异样例4.2成交时间特征按日统计训练集中每天借贷的成交量,正负样本分别统计,得到如下的曲线图8,横坐标是日期(20131101至20141109),纵坐标是每天的借贷量。蓝色由线是违约的样本每天的数量(为了对比明显,将数量乘上了2),绿色曲线对应不违约的样本train set1200count o10008004002广外从20030350Date20131101~20141109图8.每日借贷量统计可以发现拍拍贷的业务量总体是在埤长的,而违约数量一开始也是缓慢增长,后面基本保持不变,总体上违约率是平稳甚至下降的。在横坐标300~350对应的日期区间,出现了些借贷量非鸴大的时间苄点,这些可能隐减着苿些信息,我们尚未挖掘出来。考虑到违约率跟时间线有关,我们将戒交时间的字段 Listinginfc傲了几种处理,一和是直接将其当做连续值特征,也就是上图对应的横坐标,另一和是离散化夂理,每10天作为一个区间,乜就是将日期0`10离散化为1,日期1120离散化为2.4.3类别特征的处理除了上面提到的对菜些类别特征进行特殊处理外,其他类别特征都做独热编码。44组合特征Xgboost的训练完成后可以输出特征的重要性,我们发现第三方数据特征ThirdParty Info Period XX”的 feature score比较大(见图3),即判别性比较高,于是用这部分特征构建了ξ合特征:将特征两两相除得到7000个特征,然后使用 boost对这7000多个特征单独训练模型,训练完成后得到特征重要性的排序,取其中top500个特征线下cv能达到0.73+的AUC值。将这500个特征添加到原始特征体系中,线下cv的AC值从0.777捉高到0.7833。另外,也组合了乘法特征(取对数):10g(x*y),刷选出其中的270多维,加入到原始特征休系中,单模型cv又提高到、0.785左右。4.5 Upadte Info表特征根据提供的修改信息表,我们从中抽取了用户的修改信息特征,比如:修改信息次数,修改信息时间到成交时间的跨度,每和信息的修改次数等等特征。46 LogInfo表特征类似地,我们从登录信息表里提取了用户的登录信息特征,比如登录天数,平均登录间隔以及每种操作代码的次数等47排序特征对原始特征中190维数值型特征接数值从小到大进行排序,得到190维排序特征。排序特征对异常数据有更强的鲁棒性,使得模型更加稳定,降低过拟合的风险。五、特征选择在特征工程部分,我们构建了一系列位置信息相关的特征、组合特征、成交时间特征、排序特征、类别稀疏侍征、 updateinfo和1 oginfo相关的特征等,所有特征加起来将近1500维,这么多维特征一方面可能会导致维数灾难,另一方面很容易导致过拟合,需要做降维处理,降维方法赏用的有如PCA,tSNE等,这类方法的计算复杂度比较高。并且根据以往经验,在数据挖掘类的匕赛中,PCA或t-SNE效果仨往不好。除了釆用降维算法之外,也可以通过特征选择来降低特征维度。特征选择的方法很多:最大信息系数(MIC)、皮尔森相关系数(衡量变量间的线性相关性)、正则化方法(L1,L2)、基于模型的特征排序方法。比较高效的是最后一种,即基于学习模型的特征排序方法,这种方法有一个好处:模型学习的过程和特征选择的过程是同时进行的,医此我们采用这和方法,基于 boost来做特征选择, xgboost模型洲练完成后可以输岀特征的重要性(见3.3图),据此我们可以保留TopN个特征,从而达到特在选择的目的。
- 2020-06-23下载
- 积分：1
