লিনিয়ার রিগ্রেশন এবং এর পুনরুদ্ধারের পদ্ধতি

উত্স: xkcd

লিনিয়ার রিগ্রেশন ডেটা বিশ্লেষণের সাথে সম্পর্কিত অনেক ক্ষেত্রের জন্য মৌলিক অ্যালগরিদমগুলির মধ্যে একটি। এই জন্য কারণ সুস্পষ্ট। এটি একটি খুব সহজ এবং বোধগম্য অ্যালগরিদম, যা শত শত বছর না হলেও বহু দশ বছর ধরে এর ব্যাপক ব্যবহারে অবদান রেখেছে। ধারণাটি হল যে আমরা অন্য ভেরিয়েবলের একটি সেটের উপর একটি ভেরিয়েবলের একটি রৈখিক নির্ভরতা অনুমান করি এবং তারপর এই নির্ভরতা পুনরুদ্ধার করার চেষ্টা করি।

কিন্তু এই নিবন্ধটি ব্যবহারিক সমস্যা সমাধানের জন্য লিনিয়ার রিগ্রেশন ব্যবহার করার বিষয়ে নয়। এখানে আমরা এর পুনরুদ্ধারের জন্য বিতরণ করা অ্যালগরিদম বাস্তবায়নের আকর্ষণীয় বৈশিষ্ট্যগুলি বিবেচনা করব, যা আমরা একটি মেশিন লার্নিং মডিউল লেখার সময় সম্মুখীন হয়েছিলাম অ্যাপাচি ইগনিট. সামান্য মৌলিক গণিত, মেশিন লার্নিং এবং ডিস্ট্রিবিউটেড কম্পিউটিং আপনাকে সাহায্য করতে পারে কিভাবে লিনিয়ার রিগ্রেশন সঞ্চালন করতে হয় এমনকি যখন আপনার ডেটা হাজার হাজার নোড জুড়ে বিতরণ করা হয়।

এটা কিসের ব্যাপারে?

আমরা রৈখিক নির্ভরতা পুনরুদ্ধারের কাজটির মুখোমুখি হয়েছি। ইনপুট ডেটা হিসাবে, অনুমিতভাবে স্বাধীন ভেরিয়েবলের ভেক্টরের একটি সেট দেওয়া হয়, যার প্রতিটি নির্ভরশীল ভেরিয়েবলের একটি নির্দিষ্ট মানের সাথে যুক্ত। এই ডেটা দুটি ম্যাট্রিসের আকারে উপস্থাপন করা যেতে পারে:

এখন, যেহেতু নির্ভরতা ধরে নেওয়া হয়েছে, এবং তদ্ব্যতীত, রৈখিক, আমরা আমাদের অনুমানকে ম্যাট্রিক্সের একটি গুণফলের আকারে লিখব (রেকর্ডিং সহজ করার জন্য, এখানে এবং নীচে এটি অনুমান করা হয় যে সমীকরণের মুক্ত শব্দটি লুকিয়ে আছে। , এবং ম্যাট্রিক্সের শেষ কলাম ইউনিট রয়েছে):

অনেকটা রৈখিক সমীকরণের সিস্টেমের মতো শোনাচ্ছে, তাই না? এটা মনে হয়, কিন্তু সম্ভবত এই ধরনের সমীকরণ সিস্টেমের কোন সমাধান হবে না। এর কারণ হ'ল গোলমাল, যা প্রায় কোনও বাস্তব ডেটাতে উপস্থিত থাকে। আরেকটি কারণ হতে পারে রৈখিক নির্ভরতার অভাব, যা অতিরিক্ত ভেরিয়েবল প্রবর্তনের মাধ্যমে মোকাবিলা করা যেতে পারে যেগুলি অরৈখিকভাবে মূলগুলির উপর নির্ভর করে। নিম্নলিখিত উদাহরণ বিবেচনা করুন:

উত্স: উইকিপিডিয়া

এটি রৈখিক রিগ্রেশনের একটি সাধারণ উদাহরণ যা একটি পরিবর্তনশীলের সম্পর্ক দেখায় (অক্ষ বরাবর ) অন্য একটি পরিবর্তনশীল থেকে (অক্ষ বরাবর ) এই উদাহরণের সাথে সঙ্গতিপূর্ণ রৈখিক সমীকরণের সিস্টেমের সমাধান করার জন্য, সমস্ত বিন্দুকে অবশ্যই একই সরলরেখায় থাকতে হবে। কিন্তু তা সত্য নয়। কিন্তু গোলমালের কারণে (অথবা একটি রৈখিক সম্পর্কের ধারণাটি ভুল ছিল বলে) তারা একই সরলরেখায় অবিকল মিথ্যা বলে না। সুতরাং, বাস্তব ডেটা থেকে একটি রৈখিক সম্পর্ক পুনরুদ্ধার করার জন্য, সাধারণত আরও একটি অনুমান প্রবর্তন করা প্রয়োজন: ইনপুট ডেটাতে শব্দ থাকে এবং এই শব্দটি থাকে স্বাভাবিক বন্টন. আপনি অন্যান্য ধরণের শব্দ বিতরণ সম্পর্কে অনুমান করতে পারেন, তবে বেশিরভাগ ক্ষেত্রেই এটি সাধারণ বিতরণ যা বিবেচনা করা হয়, যা আরও আলোচনা করা হবে।

সর্বাধিক সম্ভাবনা পদ্ধতি

সুতরাং, আমরা এলোমেলোভাবে বিতরণ করা শব্দের উপস্থিতি ধরে নিয়েছি। এমন পরিস্থিতিতে কী করবেন? এই ক্ষেত্রে গণিত আছে এবং ব্যাপকভাবে ব্যবহৃত হয় সর্বাধিক সম্ভাবনা পদ্ধতি. সংক্ষেপে, এর সারমর্মটি পছন্দের মধ্যে রয়েছে সম্ভাবনা ফাংশন এবং এর পরবর্তী সর্বাধিকীকরণ।

আমরা স্বাভাবিক শব্দের সাথে ডেটা থেকে একটি রৈখিক সম্পর্ক পুনরুদ্ধার করতে ফিরে যাই। মনে রাখবেন যে অনুমান করা রৈখিক সম্পর্ক হল গাণিতিক প্রত্যাশা বিদ্যমান স্বাভাবিক বিতরণ। একই সময়ে, সম্ভাবনা যে পর্যবেক্ষণযোগ্য উপস্থিতি সাপেক্ষে একটি বা অন্য মান গ্রহণ করে , নিম্নরূপ:

এর পরিবর্তে এখন প্রতিস্থাপন করা যাক и আমাদের প্রয়োজন ভেরিয়েবল হল:

যা বাকি থাকে তা হল ভেক্টর খুঁজে বের করা , যেখানে এই সম্ভাবনা সর্বাধিক। এই ধরনের একটি ফাংশন সর্বাধিক করার জন্য, প্রথমে এটির একটি লগারিদম নেওয়া সুবিধাজনক (ফাংশনের লগারিদমটি ফাংশনের মতো একই বিন্দুতে সর্বাধিক পৌঁছাবে):

যা, ঘুরে, নিচের ফাংশনটি ছোট করার জন্য নেমে আসে:

উপায় দ্বারা, এটি একটি পদ্ধতি বলা হয় সর্বনিম্ন বর্গক্ষেত্র. প্রায়শই উপরের সমস্ত বিবেচনা বাদ দেওয়া হয় এবং এই পদ্ধতিটি সহজভাবে ব্যবহার করা হয়।

QR পচন

এই ফাংশনের গ্রেডিয়েন্ট যে বিন্দুতে শূন্য তা খুঁজে বের করে উপরের ফাংশনের ন্যূনতম পাওয়া যাবে। এবং গ্রেডিয়েন্টটি নিম্নরূপ লেখা হবে:

QR পচন ন্যূনতম বর্গ পদ্ধতিতে ব্যবহৃত ন্যূনতম সমস্যা সমাধানের জন্য একটি ম্যাট্রিক্স পদ্ধতি। এই বিষয়ে, আমরা ম্যাট্রিক্স আকারে সমীকরণটি পুনরায় লিখি:

তাই আমরা ম্যাট্রিক্স পচন ম্যাট্রিকে и এবং একটি ধারাবাহিক রূপান্তর সঞ্চালন করুন (QR পচন অ্যালগরিদম নিজেই এখানে বিবেচনা করা হবে না, শুধুমাত্র হাতে থাকা টাস্কের সাথে এর ব্যবহার):

জরায়ু অর্থোগোনাল হয়। এটি আমাদের কাজ পরিত্রাণ পেতে অনুমতি দেয় :

এবং যদি আপনি প্রতিস্থাপন উপর , তারপর এটা কাজ করবে . সেই বিবেচনায় একটি উপরের ত্রিভুজাকার ম্যাট্রিক্স, এটি দেখতে এইরকম:

এটি প্রতিস্থাপন পদ্ধতি ব্যবহার করে সমাধান করা যেতে পারে। উপাদান হিসাবে অবস্থিত , পূর্ববর্তী উপাদান হিসাবে অবস্থিত ইত্যাদি।

এখানে এটি লক্ষণীয় যে QR পচন ব্যবহার করার কারণে ফলাফলের অ্যালগরিদমের জটিলতা সমান . তদুপরি, ম্যাট্রিক্স গুণন ক্রিয়াকলাপটি ভালভাবে সমান্তরাল হওয়া সত্ত্বেও, এই অ্যালগরিদমের একটি কার্যকর বিতরণ সংস্করণ লেখা সম্ভব নয়।

গ্রেডিয়েন্ট ডিসেন্ট

একটি ফাংশন মিনিমাইজ করার বিষয়ে কথা বলার সময়, (স্টোকাস্টিক) গ্রেডিয়েন্ট ডিসেন্টের পদ্ধতিটি সর্বদা মনে রাখা মূল্যবান। এটি একটি সহজ এবং কার্যকর মিনিমাইজেশন পদ্ধতি যা পুনরাবৃত্তিমূলকভাবে একটি বিন্দুতে একটি ফাংশনের গ্রেডিয়েন্ট গণনা করে এবং তারপর এটিকে গ্রেডিয়েন্টের বিপরীত দিকে স্থানান্তরিত করে। এই জাতীয় প্রতিটি পদক্ষেপ সমাধানটিকে ন্যূনতমের কাছাকাছি নিয়ে আসে। গ্রেডিয়েন্ট এখনও একই দেখায়:

গ্রেডিয়েন্ট অপারেটরের রৈখিক বৈশিষ্ট্যের কারণে এই পদ্ধতিটিও সমান্তরাল এবং বিতরণ করা হয়েছে। উল্লেখ্য যে উপরের সূত্রে যোগফল চিহ্নের অধীনে স্বাধীন পদ রয়েছে। অন্য কথায়, আমরা সমস্ত সূচকের জন্য স্বাধীনভাবে গ্রেডিয়েন্ট গণনা করতে পারি প্রথম থেকে , এর সমান্তরালে, এর সাথে সূচকগুলির জন্য গ্রেডিয়েন্ট গণনা করুন থেকে . তারপর ফলস্বরূপ গ্রেডিয়েন্ট যোগ করুন। সংযোজনের ফলাফল একই হবে যদি আমরা অবিলম্বে প্রথম থেকে সূচকগুলির জন্য গ্রেডিয়েন্ট গণনা করি . এইভাবে, যদি ডেটা বিভিন্ন টুকরো ডেটার মধ্যে বিতরণ করা হয়, তবে প্রতিটি অংশে গ্রেডিয়েন্টটি স্বাধীনভাবে গণনা করা যেতে পারে এবং তারপরে চূড়ান্ত ফলাফল পাওয়ার জন্য এই গণনার ফলাফলগুলিকে যোগ করা যেতে পারে:

বাস্তবায়নের দৃষ্টিকোণ থেকে, এটি দৃষ্টান্তের সাথে খাপ খায় মানচিত্র কমাতে. গ্রেডিয়েন্ট ডিসেন্টের প্রতিটি ধাপে, গ্রেডিয়েন্ট গণনা করার জন্য প্রতিটি ডেটা নোডে একটি টাস্ক পাঠানো হয়, তারপর গণনা করা গ্রেডিয়েন্টগুলি একত্রে সংগ্রহ করা হয় এবং তাদের যোগফলের ফলাফলটি উন্নত করতে ব্যবহার করা হয়।

বাস্তবায়নের সহজতা এবং MapReduce দৃষ্টান্তে কার্যকর করার ক্ষমতা থাকা সত্ত্বেও, গ্রেডিয়েন্ট ডিসেন্টেরও এর ত্রুটি রয়েছে। বিশেষ করে, অভিসার অর্জনের জন্য প্রয়োজনীয় ধাপের সংখ্যা অন্যান্য বিশেষায়িত পদ্ধতির তুলনায় উল্লেখযোগ্যভাবে বেশি।

LSQR

LSQR সমস্যা সমাধানের আরেকটি পদ্ধতি, যা রৈখিক রিগ্রেশন পুনরুদ্ধার এবং রৈখিক সমীকরণের সিস্টেমগুলি সমাধান করার জন্য উভয়ই উপযুক্ত। এর প্রধান বৈশিষ্ট্য হল এটি ম্যাট্রিক্স পদ্ধতির সুবিধা এবং একটি পুনরাবৃত্তিমূলক পদ্ধতির সমন্বয় করে। এই পদ্ধতির বাস্তবায়ন উভয় লাইব্রেরিতে পাওয়া যাবে SciPy, এবং ইন ম্যাটল্যাব. এই পদ্ধতির একটি বিবরণ এখানে দেওয়া হবে না (এটি নিবন্ধে পাওয়া যাবে LSQR: স্পার্স রৈখিক সমীকরণ এবং স্পার্স ন্যূনতম বর্গক্ষেত্রের জন্য একটি অ্যালগরিদম) পরিবর্তে, বিতরণ করা পরিবেশে LSQR-কে কার্যকর করার জন্য একটি পদ্ধতির প্রদর্শন করা হবে।

LSQR পদ্ধতির উপর ভিত্তি করে দ্বিদলীয়করণ পদ্ধতি. এটি একটি পুনরাবৃত্তিমূলক পদ্ধতি, প্রতিটি পুনরাবৃত্তি নিম্নলিখিত পদক্ষেপগুলি নিয়ে গঠিত:


কিন্তু আমরা যদি ধরে নিই যে ম্যাট্রিক্স অনুভূমিকভাবে বিভাজন করা হয়, তারপর প্রতিটি পুনরাবৃত্তি দুটি MapReduce ধাপ হিসাবে উপস্থাপন করা যেতে পারে। এইভাবে, প্রতিটি পুনরাবৃত্তির সময় ডেটা স্থানান্তর হ্রাস করা সম্ভব (শুধুমাত্র অজানা সংখ্যার সমান দৈর্ঘ্য সহ ভেক্টর):

লিনিয়ার রিগ্রেশন বাস্তবায়ন করার সময় এই পদ্ধতিটি ব্যবহার করা হয় Apache Ignite ML.

উপসংহার

অনেক রৈখিক রিগ্রেশন পুনরুদ্ধার অ্যালগরিদম আছে, কিন্তু সেগুলির সবকটি সব অবস্থায় প্রয়োগ করা যায় না। তাই ছোট ডেটা সেটের সঠিক সমাধানের জন্য QR পচন চমৎকার। গ্রেডিয়েন্ট ডিসেন্ট বাস্তবায়ন করা সহজ এবং আপনাকে দ্রুত একটি আনুমানিক সমাধান খুঁজে পেতে অনুমতি দেয়। এবং LSQR পূর্ববর্তী দুটি অ্যালগরিদমের সর্বোত্তম বৈশিষ্ট্যগুলিকে একত্রিত করে, যেহেতু এটি বিতরণ করা যেতে পারে, গ্রেডিয়েন্ট ডিসেন্টের তুলনায় দ্রুত একত্রিত হয় এবং একটি আনুমানিক সমাধান খুঁজে পেতে QR পচনের বিপরীতে অ্যালগরিদমকে প্রাথমিকভাবে থামানোর অনুমতি দেয়।

উত্স: www.habr.com