वैज्ञानिक कंप्यूटिंग में अंडरफ्लो से कैसे निपटें?

मैं संभाव्य मॉडल पर काम कर रहा हूं, और उन मॉडलों पर अनुमान लगाने पर, अनुमानित संभावनाएं बहुत छोटी हो सकती हैं। अंडरफ्लो से बचने के लिए, मैं वर्तमान में लॉग डोमेन में काम कर रहा हूं (मैं संभावनाओं का लॉग स्टोर करता हूं)। संभावनाओं गुणा एक अतिरिक्त के बराबर है, और जोड़ने पर सूत्र का उपयोग करके किया जाता है:वैज्ञानिक कंप्यूटिंग में अंडरफ्लो से कैसे निपटें?

log(exp(a) + exp(b)) = log(exp(a - m) + exp(b - m)) + m

जहां m = max(a, b)।

मैं कुछ बहुत बड़ी matrices का उपयोग करता हूं, और मुझे मैट्रिक्स-वेक्टर गुणाओं की गणना करने के लिए उन matrices के तत्व-वार घातीय लेना होगा। यह कदम काफी महंगा है, और मैं सोच रहा था कि संभावनाओं के साथ काम करते समय अंडरफ्लो से निपटने के लिए अन्य विधियां मौजूद हैं या नहीं।

संपादित करें: दक्षता कारणों के लिए, मैं एक समाधान आदिम प्रकार और नहीं वास्तविक संख्या की मनमानी परिशुद्धता प्रतिनिधित्व भंडारण वस्तुओं का उपयोग कर रहा हूँ।

संपादित करें 2: मैं लॉग डोमेन चाल से अधिक तेज़ समाधान की तलाश में हूं, अधिक सटीक समाधान नहीं। मैं वर्तमान में प्राप्त सटीकता से खुश हूं, लेकिन मुझे एक तेज विधि की आवश्यकता है। विशेष रूप से, सारांश मैट्रिक्स-वेक्टर गुणाओं के दौरान होता है, और मैं कुशल बीएलएएस विधियों का उपयोग करने में सक्षम होना चाहता हूं।

समाधान: जोनाथन दर्सी के साथ चर्चा के बाद, मैं अपने सबसे बड़े तत्व द्वारा प्रत्येक मैट्रिक्स और वेक्टर गुणनखंड के लिए, और लॉग डोमेन कि कारक स्टोर करने के लिए फैसला किया। गुण सरल हैं। जोड़ों से पहले, मुझे दो कारकों के अनुपात से जोड़े गए मैट्रिक्स/वैक्टरों में से एक को कारक बनाना होगा। मैं हर दस ऑपरेशन कारक अद्यतन करता हूं।

स्रोत

2012-02-17 Edouard

आप जावा का उपयोग करना चाहिए है? या आप अन्य भाषाओं का उपयोग कर सकते हैं? – enzom83

@ पीटर - यह बिल्कुल असामान्य नहीं है। उदाहरण के लिए अधिकतम संभावना अनुमान के साथ काम करना, इस तरह की संख्या देखने के लिए बिल्कुल असामान्य नहीं होगा। आपका ऑप्टिमाइज़र अभी भी अभिसरण करने में सक्षम होना चाहिए, भले ही शुरुआती बिंदु उतना अच्छा न हो जितना आप चाहें। और यदि आप वहां आते हैं, तो अभिसरण एक विकल्प नहीं है। –

यह ध्वनि की तरह लगता है सुंदर सार है। यदि आप ब्रह्माण्ड इकाइयों में ब्रह्मांड की आयु को मापते हैं, तो आपको लगभग 2e58 मिलते हैं, समय की इकाइयों की संख्या कुछ भी हो सकती थी।अगर किसी के पास 1e-300 से कम की संभावना है तो कल्पना करना मुश्किल है कि यह असंभव या कम से कम सैद्धांतिक रूप से अतुलनीय और अज्ञात नहीं है। बस कुछ माप के बारे में सोचें जो आपको जानने के लिए लेना होगा कि किसी चीज़ की संभावना 1e-58 है। –

यह समस्या हाल ही में computational science stack exchange site पर भी आई है, और हालांकि तत्काल चिंता वहां पर बहती है, समस्याएं उतनी ही कम हैं।

लॉग स्थान में परिवर्तन निश्चित रूप से एक उचित दृष्टिकोण है। आप जिस भी स्थान पर हैं, बड़ी संख्या में रकम सही तरीके से करने के लिए, आपके सारांशों की सटीकता को बेहतर बनाने के लिए आप कुछ विधियों का उपयोग कर सकते हैं। मुआवजा सारांश दृष्टिकोण, सबसे प्रसिद्ध Kahan summation, दोनों को एक योग रखें और प्रभावी रूप से "शेष" क्या है; यह आपको बिना किसी लागत के उच्च परिशुद्धता अंकगणित (और केवल आदिम प्रकारों का उपयोग करके) का उपयोग करने के कुछ फायदे देता है। शेष शब्द आपको कुछ संकेत देता है कि आप कितनी अच्छी तरह से कर रहे हैं।

आपके अतिरिक्त के वास्तविक यांत्रिकी को बेहतर बनाने के अलावा, आप अपनी शर्तों को कैसे जोड़ते हैं, इस क्रम को बदलने से बड़ा अंतर हो सकता है। अपनी शर्तों को क्रमबद्ध करना ताकि आप सबसे छोटे से सबसे बड़े से संक्षेप में मदद कर सकें, तब तक आप अक्सर शब्दों को जोड़ना नहीं चाहते हैं जो बहुत अलग हैं (जो महत्वपूर्ण राउंडऑफ समस्याओं का कारण बन सकते हैं); कुछ मामलों में, लॉग एन दोहराए गए जोड़ीदार रकम भी आपके शब्दों की तरह दिखने के आधार पर सीधे रैखिक राशि करने में सुधार कर सकते हैं।

इन सभी दृष्टिकोणों की उपयोगीता आपके डेटा के गुणों पर बहुत निर्भर करती है। मनमाने ढंग से परिशुद्धता गणित पुस्तकालय, जबकि गणना समय (और संभवतः स्मृति) में अत्यधिक महंगा है, इसका काफी सामान्य समाधान होने का लाभ है।

स्रोत

2012-02-18 15:38:51

उस बहुत ही रोचक जवाब के लिए धन्यवाद। हालांकि, मैं एक और अधिक कुशल विधि की तलाश में हूं, एक और सटीक नहीं (मुझे लॉग डोमेन चाल के साथ प्राप्त सटीकता से मैं खुश हूं)। और लॉग स्पेस में काम किए बिना मुआवजा सारांश का उपयोग केवल सटीकता की समस्या को ठीक करें, न कि अंडरफ्लो का जोखिम। – Edouard

आपको सटीकता में कोई दिलचस्पी नहीं है, लेकिन आप बहने के बारे में चिंतित हैं? अंडरफ्लोइंग एक सटीकता विचार नहीं है? मुझे नहीं लगता कि मैं समझता हूं कि आप क्या खोज रहे हैं। –

'शुद्धता' से मेरा क्या मतलब है सारांशों की सटीकता। मुआवजा सारांश का उपयोग करके, मैं अभी भी उन संख्याओं को प्राप्त कर सकता हूं जो दो छोटी संख्याओं को गुणा करते समय 'डबल' द्वारा प्रतिनिधित्व करने के लिए बहुत छोटे होते हैं। लंबे एचएमएम पर अनुमान लगाने पर, आप मध्यवर्ती मात्रा प्राप्त कर सकते हैं जो '10^-324' से छोटे होते हैं, लेकिन परिमाण का एक ही क्रम होता है। अधिकतम द्वारा फैक्टरोरिंग आपको सटीक योग की गणना करने की अनुमति देता है। यही मेरा वर्तमान समाधान कर रहा है। असल में, मैं कुशल जोड़ और गुणा के साथ, छोटी संख्याओं का प्रतिनिधित्व करने की तलाश में हूं। अब मेरे पास केवल कुशल गुणा है। – Edouard

विकल्प 1:Commons Math - The Apache Commons Mathematics Library

कॉमन्स मठ हल्के, आत्म निहित गणित और सांख्यिकी घटकों सबसे आम समस्याओं जावा प्रोग्रामिंग भाषा या कॉमन्स लैंग में उपलब्ध नहीं को संबोधित करने का एक पुस्तकालय है।

नोट: एपीआई, जबकि कारखाना DfpField (बजाय कुछ और अधिक सहज ज्ञान युक्त DfpFac या DfpFactory) नामकरण एक कारखाने पैटर्न मजबूर करने के लिए निर्माताओं के सुरक्षा करता है। तो तुम तो आप .multiply या जो कुछ भी इस पर कॉल कर सकते हैं

new DfpField(numberOfDigits).newDfp(myNormalNumber)

उपयोग करने के लिए एक Dfp का दृष्टांत है,। मैंने सोचा कि मैं इसका जिक्र करूँगा क्योंकि यह थोड़ा उलझन में है।

विकल्प 2:GNU Scientific Library या Boost C++ Libraries। इन मूल पुस्तकालयों को कॉल करने के लिए इन मामलों में आपको JNI का उपयोग करना चाहिए।

विकल्प 3: आप अन्य कार्यक्रमों और/या भाषाओं का उपयोग करने के लिए स्वतंत्र हैं, तो आप इस तरह के Octave, Scilab, और इसी तरह के रूप में संख्यात्मक गणनाओं के लिए कार्यक्रमों/भाषाओं के उपयोग पर विचार कर सकता है।

विकल्प 4: जावा केBigDecimal।

स्रोत

2012-02-17 23:35:30 enzom83

कम से कम मैटलैब और ऑक्टेव दोनों में कुछ जावा बाइंडिंग भी हैं। – Voo

ऑक्टैव Matlab की तुलना में बहुत सस्ता (मुफ़्त!) है। –

संदर्भों के लिए धन्यवाद, लेकिन मुझे नहीं लगता कि वे मेरे लिए काम करेंगे। विकल्प 1 और 4: मनमाने ढंग से सटीक दशमलव संख्याओं का उपयोग करना बहुत महंगा है क्योंकि वे ऑब्जेक्ट्स का उपयोग करते हैं, न कि आदिम प्रकार, और इसलिए इस तरह के प्रतिनिधित्व के साथ कंप्यूटिंग जोड़ और गुणा अधिक महंगा है। विकल्प 2: 1 और 4 (AFAIK) जैसी ही समस्याएं और मैं जावा के साथ रहना पसंद करता हूं। विकल्प 3: मैं कुछ समय के लिए numpy और matlab का उपयोग कर रहा हूं, और एक ही समस्या होती है, क्योंकि वे फ्लोट्स और युगल का भी उपयोग करते हैं। – Edouard

लघुगणक रूप में मूल्यों के भंडारण के बजाय, मुझे लगता है कि आप शायद बेहतर होगा double रों, अर्थात्, फ्लोटिंग प्वाइंट प्रतिनिधित्व के रूप में एक ही अवधारणा का उपयोग कर। उदाहरण के लिए, आप प्रत्येक मान को दो long एस के रूप में स्टोर कर सकते हैं, एक साइन-एंड-मंटिसा के लिए और एक एक्सपोनेंट के लिए। (रियल फ़्लोटिंग-पॉइंट में बहुत से किनारे के मामलों का समर्थन करने और एक बिट को बर्बाद करने से बचने के लिए सावधानी से ट्यून किए गए डिज़ाइन हैं, लेकिन आपको शायद उनमें से किसी के बारे में चिंता करने की आवश्यकता नहीं है, और इसे एक तरीके से डिजाइन करने पर ध्यान केंद्रित कर सकते हैं यह कार्यान्वित करने के लिए आसान है।)

स्रोत

2012-02-18 00:39:20 ruakh

ओपी संभाव्य मॉडल पर काम कर रहा है। लॉग इन संभावनाएं ऐसी समस्याओं में बहुत आम हैं। –

@ डेविड हैममेन: जानना अच्छा है, धन्यवाद! – ruakh

मैंने इसके बारे में सोचा। लेकिन जैसे-जैसे मैं अपने संपादित सवाल में कहा, मैं बजाय अधिक मेरी जरूरतों के अनुकूल एक नए प्रकार के विकास है, लेकिन प्रदर्शन के मुद्दों के लिए अग्रणी, दक्षता कारणों के लिए आदिम प्रकार ('doubles') से चिपके पसंद करते हैं। – Edouard

मैं कई साल पहले इसी तरह की समस्या में भाग गया था। समाधान लॉग का अनुमान लगाने के लिए था (1 + एक्सपी (-एक्स))। सन्निकटन की सीमा को इतना बड़ा होने की आवश्यकता नहीं है (0 से 40 तक x पर्याप्त से अधिक होगा), और कम से कम मेरे मामले में सटीकता को विशेष रूप से उच्च होने की आवश्यकता नहीं थी।

आपके मामले में, ऐसा लगता है कि आपको लॉग (1 + exp (-x1) + exp (-x2) + ...) की गणना करने की आवश्यकता है। उन बड़े नकारात्मक मूल्यों को फेंक दें। उदाहरण के लिए, मान लें कि ए, बी, और सी तीन लॉग संभावनाएं हैं, 0> ए> बी> सी के साथ। यदि सी-ए> 38 है तो आप सी को अनदेखा कर सकते हैं। यह आपकी संयुक्त लॉग संभावना में योगदान नहीं दे रहा है, कम से कम नहीं यदि आप युगल के साथ काम कर रहे हैं।

स्रोत

2012-02-18 16:52:15

चालाक चाल। लेकिन मुझे लगता है कि (1 + exp (x1) + exp (x2) + ...) '' लॉग का अनुमान है जो '' n' डबल्स के exp' समारोह लेने की तुलना में तेजी है विकासशील काफी चुनौतीपूर्ण है। – Edouard

आप अभी भी उन बेहद कम संभावना घटनाओं को छोड़ने की चाल का उपयोग कर सकते हैं। यदि आप आईईईई युगल के साथ काम कर रहे हैं, तो 1 + एक्सपी (-37) बिल्कुल 1 के बराबर है। यह तुरंत आपकी अंडरफ्लो समस्या से छुटकारा पा जाएगा। –

मुझे समझ नहीं आता क्यों यह काम करता है, लेकिन यह फार्मूला काम करने लगता है और है सरल:

c = a + log(1 + exp(b - a))

कहाँ c = log(exp(a)+exp(b))

स्रोत

2014-09-19 21:55:16 Houshalter

वैज्ञानिक कंप्यूटिंग में अंडरफ्लो से कैसे निपटें?

उत्तर

संबंधित मुद्दे