اطلاعات، واگرایی و ریسک برای آزمایش های باینری PDF

پیش نمایش اطلاعات، واگرایی و خطر برای آزمایش های باینری

اطلاعات ، واگرایی و خطر برای آزمایش های باینری مارک D. Reid [از طریق ایمیل محافظت شده] دانشگاه ملی استرالیا کانبرا قانون 0200 ، استرالیا رابرت سی ویلیامسون [ایمیل محافظت شده] دانشگاه ملی استرالیا و قانون Nicta Canberra 0200 ، ویراستار استرالیا: 9 0 چکیده 0 2 ماUnify F-Divergences ، واگرایی Bregman ، مرزهای ضرر جانشین (مرزهای پشیمانی) ، N properscoringrules ، تطبیق ، لباس های لباس ، ROC-CurvesandInformation. Wedo یک سیستماتیک است که از نظر studyinginitegralandvariationalretationsofteseobjects j و با انجام این کار مشخصات اولیه آنها را شناسایی کنید که همه مربوط به 5 طبقه بندی باینری حساس به هزینه هستند. و همچنین روشن کردن روابط بین دیدگاههای تولیدی و تبعیض آمیز] از یادگیری ، ماشین آلات جدید منجر به محدودیت های ضرر و زیان جامه ای تنگ تر و نابرابری های پینزکر عمومی در رابطه با واگرایی F با واگرایی متنوع می شود. iteewViewPointilluminateseSexistingAlgoritoms: ItProvidesAnewderivation دستگاه های بردار پشتیبانی از نظر واگرایی و حداکثر میانگین dis- را نشان می دهد. t یک crepancytofisherlineardiscriminants. italsosuggestsnewtechniquesforemating t f-divergences. S [1 1. مقدمه V 6 5 مشکلات یادگیری ماشین اغلب مربوط به آزمایش های باینری است. در آنجا فرض بر این است که 3 مشاهده از ترکیبی از دو توزیع (یکی برای هر کلاس) تهیه شده است. این 0 توزیع بسیاری از اشیاء مهم مربوط به مشکلات یادگیری آنها را تعیین می کند. 1 زیربنایی مانند خطر ، واگرایی و اطلاعات. هدف ما در این مقاله ارائه 0 همه این اشیاء در یک چارچوب منسجم است که دقیقاً نحوه ارتباط آنها با هر 9 0 دیگر را توضیح می دهد.: v i x 1. 1 انگیزه r a بسیاری از مفاهیم مختلف وجود دارد که زیربنای تعیین مشکلات یادگیری ماشین است. این موارد شامل اطلاعات ، از دست دادن ، خطر ، پشیمانی ، منحنی های ROC و منطقه زیر آنها ، عملکردهای از دست دادن ، واگرایی Bregman و فاصله یا واگرایی بین توزیع احتمال است. بر روی سطح ، مشکل تخمین اینکه آیا دو نام تجاری (Asmempecturedby ، مثلاً ، آنها ، leiblerdivergence) به حداقل می رسند و به حداقل می رسد در یک مشکل پیش بینی به حداقل می رسد. یکی از اهداف مقاله حاضر این است که نشان دهیم چگونه این تفاوت فوق العاده فوق العاده فقط فوق العاده است - 1 عمیق تر آنها همان مشکل هستند و بینش های تحلیلی و الگوریتمی برای یکی می توانند به دیگری منتقل شوند. machineleaingasaasaangineeringdisciplineisstillinitsinfancy1.<0 0,s> 0 uf8f4 uf8f4 uf8f4 uf8f20, τ = 0,s = 0 I (s,τ) := (1) φ uf8f4τφ(0), τ> 0,s = 0 uf8f4 uf8f4 uf8f4uf8f3sφ(cid:48) , τ = 0,s> 0 ∞ where φ(0) := lims→0φ(s) R and φ(cid:48)∞ is the slope at infinity defined as ∈ φ(s +s) φ(s ) φ(s) φ(cid:48) := lim 0 − 0 = lim (2) ∞ s→+∞ s s→+∞ s for every s S where φ(s ) is finite. This slope at infinity is only finite when φ(s) = 0 0 ∈ O(s), that is, when φ grows at most linearly as s increases. When φ(cid:48) is finite it ∞ 12. TherestrictionofthevaluesofφtoRwillbeassumedthroughoutunlessexplicitlystatedotherwise. This implies the propeess of φ since it caot take on the values −∞ or +∞. 7 measures the slope of the linear asymptote. The function Iφ : [0, )2 R is convex in ∞ → both arguments (Hiriart-Urruty and Lemar´echal, 1993b) and may take on the value + ∞ when s or τ is zero. It is introduced here as it will form the basis of the f-divergences described in the next section.13 ♦ The perspective transform can be used to define the Csisz´ar dual φ : [0, ) R of ∞ → a convex function φ : R+ R by letting → (cid:18) (cid:19) 1 ♦ φ (τ) := I (1,τ) = τφ (3) φ τ for all τ R+ and φ♦(0) := φ(cid:48)∞. Note that the original φ can be recovered from Iφ as ∈ φ(s) = I (s,1). f The convexity of the perspective transform I in both its arguments guarantees φ ♦ the convexity of the dual φ . Some simple algebraic manipulation shows that for all s,τ R+ ∈ Iφ(s,τ) = Iφ♦(τ,s). (4) This observation leads to a natural definition of symmetry for convex functions. We will call a convex function ♦-symmetric (or simply symmetric when the context is clear) when its perspective transform is symmetric in its arguments. That is, φ is ♦-symmetric when I (s,τ) = I (τ,s) for all s,τ [0, ). Equivalently, φ is symmetric if and only if φ φ ♦ ∈ ∞ φ = φ. 2.2 The Legendre-Fenchel Dual Representation A second important dual operator for convex functions is the Legendre-Fenchel (LF) dual. The LF dual φ(cid:63) of a function φ : S R is a function defined by → φ(cid:63)(s(cid:63)) := sup s,s(cid:63) φ(s) . (5) s∈S TheLFdualofanyfunctionisconvexand, ifthefunctionφisconvexthentheLF bidual is a faithful representation of the original function. That is, φ(cid:63)(cid:63)(s) = sup s(cid:63),s φ(cid:63)(s(cid:63)) = φ(s). (6) s(cid:63)∈S(cid:63) When φ(s) is a function of a real argument s and the derivative φ(cid:48)(s) exists, the Legendre-Fenchel conjugate φ(cid:63) is given by the Legendre transform (Hiriart-Urruty and Lemar´echal, 2001; Rockafellar, 1970) φ(cid:63)(s) = s (φ(cid:48))−1(s) φ(cid:0)(φ(cid:48))−1(s)(cid:1). (7) · − 13. The perspective transform is closely related to epi-multiplication which is defined for all τ ∈[0,∞) and (proper) convex functions φ to be τ ⊗φ := s (cid:55)→ τφ(s/τ) for τ> 0 and is 0 when τ = s = 0 and +∞ otherwise. Bauschke et al. (2008) provides an excellent summary of the properties of this operation along with its relationship to other operations on convex functions. 8 2.3 Integral Representations In this paper we are primarily conceed with convex and concave functions defined on subsetsoftherealline. AcentraltoolintheiranalysisistheintegralformoftheirTaylor expansion. Here, φ(cid:48) and φ(cid:48)(cid:48) denote the first and second derivatives of φ respectively. Theorem 1 (Taylor’s Theorem) Let S = [s0,s] be a closed interval of R and let φ : S R be differentiable on [s0,s] and twice differentiable on (s0,s). Then → (cid:90) s φ(s) = φ(s )+φ(cid:48)(s )(s s )+ (s t)φ(cid:48)(cid:48)(t)dt. (8) 0 0 0 − − s0 The argument s appears in the limits of integral in the above theorem and con- sequently can be awkward to work with. Also, it will be useful to expand φ about some point not at the end of the interval of integration. The following corollary of Tay- lor’s theorem removes these problems by introducing piece-wise linear terms of the form (s t) = (s t) 0. + − − ∨ Corollary 2 (Integral Representation I) Let φ : [a,b] R be a twice differentiable → function. Then, for all s,s [a,b] we have 0 ∈ (cid:90) b φ(s) = φ(s )+φ(cid:48)(s )(s s )+ φ (s,t)φ(cid:48)(cid:48)(t)dt, (9) 0 0 − 0 s0 a where (cid:40) (s t) s s + 0 φ (s,t) := − ≤ (10) s0 (t s) s>برای توصیف مشکلات یادگیری ماشین (این زبان معمولاً با ترکیبی غیررسمی از انگلیسی و ریاضیات انجام می شود). در روش ترکیب راه حل های یادگیری ماشین بسیار کمی وجود دارد. یعنی با توجه به راه حل یک مشکل ، از آن برای حل دیگری استفاده کنید. البته کسی دوست دارد فقط نتواند این کار را انجام دهد ، بلکه مشخص شود که چه کسی ممکن است در انجام این کار از دست بدهد. برای انجام این کار ، فرد باید بتواند ضمانت های نظری را در مورد چگونگی حل مشکل اصلی با حل مشکل جانشین ارائه دهد. مربوط به این موضوعات این واقعیت است که هیچ ابتدایی درک خوبی برای یادگیری ماشین وجود ندارد. در واقع ، این حتی به چه معنی است؟همه این موضوعات انگیزه اصلی این مقاله است. هدف بلند مدت ما (که این مقاله به نظر می رسد اما اولین قدم است) تبدیل شدن به یادگیری ماشین به یک رشته مهندسی خوب تر با یک زبان توافق شده و قوانین ترکیب کاملاً درک شده است. انگیزه ما این است که تا زمانی که فرد نتواند سیستم های ساختمانی را به صورت مدولاری شروع کند ، به جای به دست آوردن مزایای کارآیی مجدداً از ابتدا برای شروع هر مشکل جدید محدود می شود. ما در حال مقایسه مشکلات هستیم ، نه راه حل یا الگوریتم. در حالی که تلاش هایی برای ارائه درجه ای از منحصر به فرد در سطح الگوریتم ها وجود داشته است (Altun and Smola ، 2006) ، محدودیت های ذاتی برای چنین برنامه تحقیقاتی وجود دارد. اساسی ترین این است که (با کمال تعجب!) هیچ تعریف رسمی توافق شده در مورد آنچه که یک الگوریتم واقعاً چیست ، وجود ندارد ، و نه چگونه می توان دو الگوریتم را با یک دیدگاه برای تعیین اینکه آیا یکسان هستند مقایسه کنید (Blass and Gurevich ، 2003). ما با آزمایش های باینری شروع کرده ایم زیرا آنها ساده و به طور گسترده استفاده می شوند. همانطور که نشان خواهیم داد ، با پیگیری دستور کار تحقیقاتی سطح بالا که در بالا خلاصه شد ، ما موفق شده ایم همه مفاهیم متفاوت ذکر شده را متحد کنیم و علاوه بر این ، همزمان دو نتیجه اساسی را ساده و تعمیم داده ایم: نابرابری های پینکر بین F-Divergences و مرزهای پشیمانی از بین رفته. اثبات این نتایج جدید اساساً به تجزیه به مشکلات بدوی متکی است. 1. Bousquet (2006) نیاز به یک واژگان توافق شده ، بیانیه روشنی از مشکلات اصلی را بیان کرده است ، و "تجدید نظر در مورد آنچه که تاکنون با یک نگاه تازه انجام شده است یا کشف شده است". 2. Abelson و همکاران.(1996) اصول ساخت نرم افزار را با کمک (لاک ، 1690 ، فصل 12 ، بند 1) شرح داد: theactsofthemind ، که در آن initexertsitspoweroversimpleideas ،arechie fl ythesethree: (1) CombiningSeveralsimpleIdeasintoOneCompoundone ؛ و ایده های thusallcomplex ساخته شده است.(2) مورد دوم ، دو ایده ، چه ساده و چه پیچیده ، با هم و تنظیم آنها توسط یکدیگر ، به منظور ایجاد یکباره از آنها ، بدون اینکه آنها را به یک واحد بپردازید. که توسط آن تمام ایده های روابط خود را بدست می آورد.(3) مورد سوم آنها را از AllotherideasthatacCompanyhemintheirrelexization جدا می کند. ThisiscalledAbstraction: و بنابراین تمام ایده های کلی آن ، مدولار بودن برای سخت افزار رایانه اصلی است (بالدوین و کلارک ، آینده ، 2006) و سایر رشته های مهندسی (گرشنسون و همکاران ، 2003). 2 1. 2 تازگی و مهم ، هدف اولیه ما ارائه مطالب موجود به روش یکپارچه بود. ما واقعاً این کار را کرده ایم. با انجام این کار ، ما اثبات جدید (و ساده تر) نتایج موجود را تهیه کرده ایم. به طور اضافی ما نتایج فنی جدید را توسعه داده ایم: 1) پیوندی بین بازنمایی های انتگرال وزنی برای قوانین امتیاز دهی مناسب و موارد مربوط به-واگرایی. 2) مشتق یکپارچه از بازنمودهای انتگرال از نظر سری تیلور. 3) استفاده از این نمایندگان برای به دست آوردن مرزهای جدید برای واگرایی ، خطرات و پشیمانی های بیز ("مرزهای ضرر جانشین" و نابرابری های پینکر). 4) نشان می دهد که اطلاعات آماری (و از این رو اطلاعات) هر دو اطلاعات Bregman هستند. 5) نشان دادن اتصالات بین بازنمایی تغییرات خطرات و واگرایی. 6) اشتقاق SVM ها از دیدگاه متنوع. 7) نتایج مربوط به AUC (منطقه زیر منحنی ROC) به واگرایی. نکته مهم این اتصالات جدید این است که آنها نشان می دهند که انتخاب عملکرد ضرر (قانون امتیاز دهی) ، F-Divergence و Bregman Divergence (پشیمانی) با هم ارتباط نزدیکی دارند-انتخاب یکی از این موارد به معنای انتخاب برای دیگران است. علاوه بر این ، ما نشان می دهیم که بیش از حد قابل استفاده است. توابع وزن این مزیت را دارند که اگر دو عملکرد وزن مطابقت داشته باشند ، اشیاء مربوطه یکسان هستند. این مورد برای پارامترهای F- واگرایی F یا عملکرد محدب پارامتری یک واگرایی از برونژ ، اینگونه نیست. و همچنین علاقه نظری به چنین اتصالات ، این بازنمودهای متناوب الگوریتم های جدیدی را برای برآورد تجربی چنین مقادیر نشان می دهد. 1. 3 نتایج خاص پس زمینه در بدنه مقاله ذکر شده است. ما نشان می دهیم که جارو گسترده کار قبلی را در امتداد خط مقاله حاضر نشان می دهیم.<>مهمترین پیش سازها و الهام بخش سه اثر تقریباً همزمان 3 توسط Buja و همکاران است.(2005) ، لیز و واژدا (2006) و نگوین و همکاران.(2005). کار Dawid (2007) از نظر روحیه بسیار شبیه به آنچه در اینجا ارائه شده است. نکته مهم این است که او به یک دیدگاه پارامتری متکی است و می تواند از ماشین آلات هندسه Riemaian 4 استفاده کند. در مقابل ، تمام نتایج در این مقاله "بدون هماهنگی" است. انگیزه کار حاضر از نزدیک با آن از Hand (1994) مطابقت دارد که هدف از آن "تحریک بحث در مورد لزوم تدوین سؤالات تحقیق به طور دقیق است که ممکن است به طور واضح و به درستی با تکنیک های استوار مطابقت داشته باشند." 5. مقاله یکپارچه سازی انواع را ارائه می دهد. این به خودی خود به سختی در یادگیری ماشین جدید است. رویکردهای مختلفی برای اتحاد وجود دارد. یک تمایز بین رویکردهای مونیستی و کثرت گرا است (جیمز ، 1909 ؛ ترکل و پاپرت ، 1992). 3. (Nguyenetal. ، 2005) Isdated13october ، 2005 ، (LieseAndvajda ، 2006) Wasreceivedon26october 2005 و (Buja et al. ، 2005) مورخ 3 نوامبر 2005 است. پایان نامه PHD (شن ، 2005) ، که شامل بیشتر مواد موجود در آن است.. 5- Hand و Vinciotti (2003) برخی از کارهای یادگیری ماشین را که می توانند به عنوان مشکلات وزنی مشاهده شوند ، توسعه دهند. بوجا و همکاران را اعطا کنید.(2005). 3 رویکردهای مونیستی هدف یک تئوری 6 را شامل می شود. مشکلی که در بیشتر رویکردهای مونیستی وجود دارد این است که شما باید آن را "همه یا هیچ چیز" بپذیرید. بسیاری از رویکردهای متحد کننده در آمار و یادگیری ماشین وجود دارد که ردیابی کمی از آنها باقی مانده است. رویکردهای کثرت گرا به آنچه در اینجا پیشنهاد شده است نزدیکتر است (جایی که به جای جستجوی یک نمایش استاد واحد ، روابط و ترجمه ها را بین طیف وسیعی از بازنمودهای مختلف مطالعه می کنیم). این ادعا با ادعای کیفر طنین انداز است که "آماری بسیار پیچیده است که از نظر یک نسخه ساده که یک پاناسه برای همه تنظیمات است ، کدگذاری می شود. باید در روشهای مختلف ممکن تا حد امکان با دقت به نظر برسد."(کیفر ، 1977). نمونه هایی از تلاش های کثرت گرا موجود شامل کاتالوگ های مشکل محدود مانند برای مفاهیم مختلف هزینه (Tuey ، 2000) یا مجموعه ای از مشکلات محدود است (Raudys ، 2001). رویکرد نظری تصمیم (Degroot ، 1970 ؛ Berger ، 1985 ؛ Kiefer ،