మూలం:
డేటా విశ్లేషణకు సంబంధించిన అనేక ప్రాంతాలకు సంబంధించిన ప్రాథమిక అల్గారిథమ్‌లలో లీనియర్ రిగ్రెషన్ ఒకటి. దీనికి కారణం స్పష్టంగానే ఉంది. ఇది చాలా సరళమైన మరియు అర్థమయ్యే అల్గోరిథం, ఇది అనేక పదుల, వందల సంవత్సరాలు కాకపోయినా, దాని విస్తృత వినియోగానికి దోహదపడింది. ఆలోచన ఏమిటంటే, మేము ఇతర వేరియబుల్స్ సెట్‌పై ఒక వేరియబుల్ యొక్క లీనియర్ డిపెండెన్స్‌ని ఊహించి, ఆపై ఈ డిపెండెన్స్‌ని పునరుద్ధరించడానికి ప్రయత్నిస్తాము.
కానీ ఈ వ్యాసం ఆచరణాత్మక సమస్యలను పరిష్కరించడానికి సరళ రిగ్రెషన్‌ను ఉపయోగించడం గురించి కాదు. మెషీన్ లెర్నింగ్ మాడ్యూల్‌ను వ్రాసేటప్పుడు మేము ఎదుర్కొన్న దాని పునరుద్ధరణ కోసం పంపిణీ చేయబడిన అల్గోరిథంల అమలు యొక్క ఆసక్తికరమైన లక్షణాలను ఇక్కడ మేము పరిశీలిస్తాము. . మీ డేటా వేలాది నోడ్‌లలో పంపిణీ చేయబడినప్పుడు కూడా లీనియర్ రిగ్రెషన్‌ను ఎలా నిర్వహించాలో గుర్తించడంలో కొద్దిగా ప్రాథమిక గణితం, యంత్ర అభ్యాసం మరియు పంపిణీ చేయబడిన కంప్యూటింగ్ మీకు సహాయపడతాయి.
మనం దేని గురించి మాట్లాడుతున్నాం?
మేము సరళ ఆధారపడటాన్ని పునరుద్ధరించే పనిని ఎదుర్కొంటున్నాము. ఇన్‌పుట్ డేటాగా, ఇండిపెండెంట్ వేరియబుల్స్ యొక్క వెక్టర్స్ సెట్ ఇవ్వబడుతుంది, వీటిలో ప్రతి ఒక్కటి డిపెండెంట్ వేరియబుల్ యొక్క నిర్దిష్ట విలువతో అనుబంధించబడుతుంది. ఈ డేటాను రెండు మాత్రికల రూపంలో సూచించవచ్చు:
ఇప్పుడు, ఆధారపడటం ఊహింపబడినందున, మరియు, ఇంకా, సరళంగా, మన ఊహను మాత్రికల ఉత్పత్తి రూపంలో వ్రాస్తాము (రికార్డింగ్‌ను సరళీకృతం చేయడానికి, ఇక్కడ మరియు దిగువన సమీకరణం యొక్క ఉచిత పదం వెనుక దాగి ఉందని భావించబడుతుంది. , మరియు మాతృక యొక్క చివరి నిలువు వరుస యూనిట్లను కలిగి ఉంటుంది):
సరళ సమీకరణాల వ్యవస్థ లాగా అనిపిస్తుంది, కాదా? ఇది కనిపిస్తుంది, కానీ చాలా మటుకు అటువంటి సమీకరణాల వ్యవస్థకు పరిష్కారాలు ఉండవు. దీనికి కారణం శబ్దం, ఇది దాదాపు ఏదైనా నిజమైన డేటాలో ఉంటుంది. మరొక కారణం లీనియర్ డిపెండెన్స్ లేకపోవడమే కావచ్చు, అసలైన వాటిపై నాన్ లీనియర్‌గా ఆధారపడే అదనపు వేరియబుల్స్‌ని పరిచయం చేయడం ద్వారా దీనిని ఎదుర్కోవచ్చు. కింది ఉదాహరణను పరిగణించండి:
మూలం:
ఇది ఒక వేరియబుల్ (అక్షం వెంట) సంబంధాన్ని చూపే లీనియర్ రిగ్రెషన్‌కి ఒక సాధారణ ఉదాహరణ ) మరొక వేరియబుల్ నుండి (అక్షం వెంట ) ఈ ఉదాహరణకి అనుగుణమైన సరళ సమీకరణాల వ్యవస్థ ఒక పరిష్కారాన్ని కలిగి ఉండాలంటే, అన్ని పాయింట్లు ఖచ్చితంగా ఒకే సరళ రేఖపై ఉండాలి. కానీ అది నిజం కాదు. కానీ అవి శబ్దం కారణంగా (లేదా సరళ సంబంధం యొక్క ఊహ తప్పుగా ఉన్నందున) ఖచ్చితంగా ఒకే సరళ రేఖపై పడవు. కాబట్టి, వాస్తవ డేటా నుండి సరళ సంబంధాన్ని పునరుద్ధరించడానికి, సాధారణంగా మరొక ఊహను పరిచయం చేయడం అవసరం: ఇన్‌పుట్ డేటాలో శబ్దం ఉంటుంది మరియు ఈ శబ్దం ఉంటుంది . మీరు ఇతర రకాల శబ్దం పంపిణీ గురించి అంచనాలు చేయవచ్చు, కానీ చాలా సందర్భాలలో ఇది సాధారణ పంపిణీగా పరిగణించబడుతుంది, ఇది మరింత చర్చించబడుతుంది.
గరిష్ట సంభావ్యత పద్ధతి
కాబట్టి, యాదృచ్ఛికంగా పంపిణీ చేయబడిన శబ్దం ఉన్నట్లు మేము ఊహించాము. అటువంటి పరిస్థితిలో ఏమి చేయాలి? ఈ సందర్భంలో గణితంలో ఉంది మరియు విస్తృతంగా ఉపయోగించబడుతుంది . సంక్షిప్తంగా, దాని సారాంశం ఎంపికలో ఉంది మరియు దాని తదుపరి గరిష్టీకరణ.
మేము సాధారణ శబ్దంతో డేటా నుండి సరళ సంబంధాన్ని పునరుద్ధరించడానికి తిరిగి వస్తాము. ఊహించిన సరళ సంబంధం గణిత నిరీక్షణ అని గమనించండి ఇప్పటికే ఉన్న సాధారణ పంపిణీ. అదే సమయంలో, సంభావ్యత పరిశీలించదగిన వాటి ఉనికికి లోబడి, ఒక విలువ లేదా మరొకదానిని తీసుకుంటుంది , క్రింది విధంగా:
ఇప్పుడు బదులుగా ప్రత్యామ్నాయం చేద్దాం и మనకు అవసరమైన వేరియబుల్స్:
వెక్టర్‌ను కనుగొనడమే మిగిలి ఉంది , ఈ సంభావ్యత గరిష్టంగా ఉంటుంది. అటువంటి ఫంక్షన్‌ను గరిష్టీకరించడానికి, మొదట దాని సంవర్గమానాన్ని తీసుకోవడం సౌకర్యంగా ఉంటుంది (ఫంక్షన్ యొక్క సంవర్గమానం ఫంక్షన్ యొక్క అదే సమయంలో గరిష్ట స్థాయికి చేరుకుంటుంది):
ఇది క్రింది ఫంక్షన్‌ను తగ్గించడానికి క్రిందికి వస్తుంది:
మార్గం ద్వారా, దీనిని పద్ధతి అంటారు . తరచుగా పైన పేర్కొన్న అన్ని అంశాలు విస్మరించబడతాయి మరియు ఈ పద్ధతి కేవలం ఉపయోగించబడుతుంది.
QR కుళ్ళిపోవడం
ఈ ఫంక్షన్ యొక్క గ్రేడియంట్ సున్నాగా ఉన్న బిందువును కనుగొనడం ద్వారా పై ఫంక్షన్ యొక్క కనిష్టాన్ని కనుగొనవచ్చు. మరియు ప్రవణత క్రింది విధంగా వ్రాయబడుతుంది:
తక్కువ చతురస్రాల పద్ధతిలో ఉపయోగించే కనిష్టీకరణ సమస్యను పరిష్కరించడానికి మాతృక పద్ధతి. ఈ విషయంలో, మేము మాతృక రూపంలో సమీకరణాన్ని తిరిగి వ్రాస్తాము:
కాబట్టి మేము మాతృకను విచ్ఛిన్నం చేస్తాము మాత్రికలకు и మరియు పరివర్తనల శ్రేణిని నిర్వహించండి (QR కుళ్ళిపోయే అల్గోరిథం ఇక్కడ పరిగణించబడదు, చేతిలో ఉన్న పనికి సంబంధించి మాత్రమే దాని ఉపయోగం):
మాత్రిక ఆర్తోగోనల్ గా ఉంది. ఇది పనిని వదిలించుకోవడానికి మాకు అనుమతిస్తుంది :
మరియు మీరు భర్తీ చేస్తే న , అప్పుడు అది పని చేస్తుంది . పరిగణలోకి ఎగువ త్రిభుజాకార మాతృక, ఇది ఇలా కనిపిస్తుంది:
ప్రత్యామ్నాయ పద్ధతిని ఉపయోగించి దీనిని పరిష్కరించవచ్చు. మూలకం గా ఉంది , మునుపటి మూలకం గా ఉంది మరియు అందువలన న.
QR కుళ్ళిపోవడం వల్ల ఏర్పడే అల్గోరిథం యొక్క సంక్లిష్టత సమానంగా ఉంటుందని ఇక్కడ గమనించాలి. . అంతేకాకుండా, మ్యాట్రిక్స్ గుణకారం ఆపరేషన్ బాగా సమాంతరంగా ఉన్నప్పటికీ, ఈ అల్గోరిథం యొక్క సమర్థవంతమైన పంపిణీ సంస్కరణను వ్రాయడం సాధ్యం కాదు.
గ్రేడియంట్ డీసెంట్
ఫంక్షన్‌ను కనిష్టీకరించడం గురించి మాట్లాడేటప్పుడు, (యాదృచ్ఛిక) గ్రేడియంట్ సంతతికి సంబంధించిన పద్ధతిని గుర్తుంచుకోవడం ఎల్లప్పుడూ విలువైనదే. ఇది ఒక పాయింట్ వద్ద ఫంక్షన్ యొక్క ప్రవణతను పునరుక్తిగా లెక్కించడం మరియు దానిని ప్రవణతకు వ్యతిరేక దిశలో మార్చడం ఆధారంగా సరళమైన మరియు ప్రభావవంతమైన కనిష్టీకరణ పద్ధతి. అటువంటి ప్రతి దశ పరిష్కారాన్ని కనిష్ట స్థాయికి చేరుస్తుంది. గ్రేడియంట్ ఇప్పటికీ అలాగే కనిపిస్తుంది:
గ్రేడియంట్ ఆపరేటర్ యొక్క సరళ లక్షణాల కారణంగా ఈ పద్ధతి కూడా బాగా సమాంతరంగా మరియు పంపిణీ చేయబడుతుంది. పై సూత్రంలో, మొత్తం గుర్తు కింద స్వతంత్ర నిబంధనలు ఉన్నాయని గమనించండి. ఇతర మాటలలో, మేము అన్ని సూచికల కోసం స్వతంత్రంగా ప్రవణతను లెక్కించవచ్చు మొదటి నుండి , దీనికి సమాంతరంగా, సూచికల కోసం ప్రవణతను లెక్కించండి కు . అప్పుడు ఫలిత ప్రవణతలను జోడించండి. మేము మొదటి నుండి సూచీల కోసం గ్రేడియంట్‌ను వెంటనే లెక్కించినట్లయితే అదనంగా ఫలితం అదే విధంగా ఉంటుంది . ఈ విధంగా, డేటా అనేక డేటా ముక్కల మధ్య పంపిణీ చేయబడితే, గ్రేడియంట్ ప్రతి ముక్కపై స్వతంత్రంగా లెక్కించబడుతుంది మరియు తుది ఫలితాన్ని పొందేందుకు ఈ గణనల ఫలితాలను సంగ్రహించవచ్చు:
అమలు దృక్కోణం నుండి, ఇది నమూనాకు సరిపోతుంది . ప్రవణత సంతతికి చెందిన ప్రతి దశలో, గ్రేడియంట్‌ను లెక్కించడానికి ప్రతి డేటా నోడ్‌కు ఒక పని పంపబడుతుంది, ఆపై లెక్కించిన ప్రవణతలు కలిసి సేకరించబడతాయి మరియు వాటి మొత్తం ఫలితం ఫలితాన్ని మెరుగుపరచడానికి ఉపయోగించబడుతుంది.
అమలులో సౌలభ్యం మరియు MapReduce నమూనాలో అమలు చేయగల సామర్థ్యం ఉన్నప్పటికీ, ప్రవణత సంతతికి కూడా దాని లోపాలు ఉన్నాయి. ప్రత్యేకించి, ఇతర ప్రత్యేక పద్ధతులతో పోలిస్తే కన్వర్జెన్స్ సాధించడానికి అవసరమైన దశల సంఖ్య గణనీయంగా ఎక్కువగా ఉంటుంది.
LSQR
సమస్యను పరిష్కరించడానికి మరొక పద్ధతి, ఇది సరళ రిగ్రెషన్‌ను పునరుద్ధరించడానికి మరియు సరళ సమీకరణాల వ్యవస్థలను పరిష్కరించడానికి రెండింటికి అనుకూలంగా ఉంటుంది. దీని ప్రధాన లక్షణం ఏమిటంటే ఇది మాతృక పద్ధతుల యొక్క ప్రయోజనాలను మరియు పునరావృత విధానాన్ని మిళితం చేస్తుంది. ఈ పద్ధతి యొక్క అమలులను రెండు లైబ్రరీలలో చూడవచ్చు మరియు లోపల . ఈ పద్ధతి యొక్క వివరణ ఇక్కడ ఇవ్వబడదు (ఇది వ్యాసంలో చూడవచ్చు ) బదులుగా, పంపిణీ చేయబడిన వాతావరణంలో అమలు చేయడానికి LSQRని స్వీకరించడానికి ఒక విధానం ప్రదర్శించబడుతుంది.
LSQR పద్ధతి ఆధారంగా ఉంటుంది . ఇది పునరావృత ప్రక్రియ, ప్రతి పునరావృతం క్రింది దశలను కలిగి ఉంటుంది:
కానీ మేము మాతృక అని ఊహిస్తే క్షితిజ సమాంతరంగా విభజించబడింది, ఆపై ప్రతి పునరావృతం రెండు MapReduce దశలుగా సూచించబడుతుంది. ఈ విధంగా, ప్రతి పునరావృత సమయంలో డేటా బదిలీలను తగ్గించడం సాధ్యమవుతుంది (తెలియని సంఖ్యకు సమానమైన పొడవు ఉన్న వెక్టర్స్ మాత్రమే):
లీనియర్ రిగ్రెషన్‌ను అమలు చేస్తున్నప్పుడు ఈ విధానం ఉపయోగించబడుతుంది .
తీర్మానం
అనేక లీనియర్ రిగ్రెషన్ రికవరీ అల్గారిథమ్‌లు ఉన్నాయి, కానీ అవన్నీ అన్ని పరిస్థితులలో వర్తించవు. కాబట్టి చిన్న డేటా సెట్లలో ఖచ్చితమైన పరిష్కారం కోసం QR కుళ్ళిపోవడం అద్భుతమైనది. గ్రేడియంట్ అవరోహణ అమలు చేయడం సులభం మరియు మీరు త్వరగా సుమారుగా పరిష్కారాన్ని కనుగొనడానికి అనుమతిస్తుంది. మరియు LSQR మునుపటి రెండు అల్గారిథమ్‌ల యొక్క ఉత్తమ లక్షణాలను మిళితం చేస్తుంది, ఎందుకంటే ఇది పంపిణీ చేయబడుతుంది, గ్రేడియంట్ డీసెంట్‌తో పోలిస్తే వేగంగా కలుస్తుంది మరియు ఉజ్జాయింపు పరిష్కారాన్ని కనుగొనడానికి QR కుళ్ళిపోకుండా, అల్గారిథమ్‌ను ముందుగానే ఆపడానికి అనుమతిస్తుంది.
మూలం: www.habr.com