ক্রমবর্ধমান সিদ্ধান্ত গাছ

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

সিদ্ধান্ত গাছ প্রশিক্ষণের জন্য ব্যবহৃত বেশিরভাগ অ্যালগরিদম একটি লোভী বিভাজন এবং জয়ের কৌশল নিয়ে কাজ করে। অ্যালগরিদম একটি একক নোড (মূল) তৈরি করে শুরু হয় এবং পুনরাবৃত্তিমূলকভাবে এবং লোভের সাথে সিদ্ধান্ত গাছটি বৃদ্ধি করে।

প্রতিটি নোডে, সমস্ত সম্ভাব্য শর্ত মূল্যায়ন করা হয় এবং স্কোর করা হয়। অ্যালগরিদম "সেরা" শর্ত নির্বাচন করে, অর্থাৎ সর্বোচ্চ স্কোর সহ শর্ত। আপাতত, শুধু জেনে রাখুন যে স্কোর হল একটি মেট্রিক যা টাস্কের সাথে সম্পর্কযুক্ত, এবং সেই মেট্রিকটিকে সর্বাধিক করার জন্য শর্তগুলি নির্বাচন করা হয়েছে৷

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

One condition leading to two leaves. The condition is 'bill_length_mm >= 16'.
If yes, the leaf is 'Adelie or Chinstrap'.  If no, the leaf
is 'Gentoo'.

চিত্র 7. একটি গাছ বৃদ্ধির প্রথম ধাপ।

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

অ্যালগরিদম নিম্নরূপ:

def train_decision_tree(training_examples):
  root = create_root() # Create a decision tree with a single empty root.
  grow_tree(root, training_examples) # Grow the root node.
  return root

def grow_tree(node, examples):
  condition = find_best_condition(examples) # Find the best condition.

  if condition is None:
    # No satisfying conditions were found, therefore the grow of the branch stops.
    set_leaf_prediction(node, examples)
    return

  # Create two childrens for the node.
  positive_child, negative_child = split_node(node, condition)

  # List the training examples used by each children.
  negative_examples = [example for example in examples if not condition(example)]
  positive_examples = [example for example in examples if condition(example)]

  # Continue the growth of the children.
  grow_tree(negative_child, negative_examples)
  grow_tree(positive_child, positive_examples)

আসুন আরো বিস্তারিতভাবে একটি নির্দিষ্ট সিদ্ধান্ত বৃক্ষকে প্রশিক্ষণের ধাপগুলি দিয়ে যাই।

ধাপ 1: একটি রুট তৈরি করুন:

A node with a question mark.

ধাপ 2: নোড #1 বৃদ্ধি করুন। শর্ত "x1 ≥ 1" পাওয়া গেছে। দুটি চাইল্ড নোড তৈরি করা হয়:

A root node
   leading to two undefined nodes.

ধাপ 3: নোড #2 বৃদ্ধি করুন। কোন সন্তোষজনক শর্ত পাওয়া যায়নি. সুতরাং, নোডটিকে একটি পাতায় পরিণত করুন:

A root
   node leading to two undefined nodes.

ধাপ 4: নোড #3 বৃদ্ধি করুন। শর্ত "x2 ≥ 0.5" পাওয়া গেছে। দুটি চাইল্ড নোড তৈরি করা হয়।

A root node, a
condition, and three leaves.

সিদ্ধান্ত গাছ বাড়ানোর জন্য অন্যান্য পদ্ধতি বিদ্যমান। একটি জনপ্রিয় বিকল্প হল বিভাজন এবং বিজয় কৌশল ব্যবহার করার পরিবর্তে বিশ্বব্যাপী নোডগুলি অপ্টিমাইজ করা।

YDF কোড
YDF-এ ডিফল্টভাবে উপরে বর্ণিত "লোভী ডিভাইড অ্যান্ড কনক্যুয়ার" অ্যালগরিদম দিয়ে সিদ্ধান্ত গাছ জন্মানো হয়। বিকল্পভাবে, আপনি growing_strategy="BEST_FIRST_GLOBAL" প্যারামিটার দিয়ে বিশ্বব্যাপী বৃদ্ধি সক্ষম করতে পারেন। আরো বিস্তারিত জানার জন্য ডকুমেন্টেশন দেখুন.

ইনপুট বৈশিষ্ট্যের সংখ্যা এবং প্রকারের উপর নির্ভর করে, একটি প্রদত্ত নোডের সম্ভাব্য অবস্থার সংখ্যা বিশাল, সাধারণত অসীম হতে পারে। উদাহরণস্বরূপ, একটি প্রান্তিক অবস্থা $\mathrm{feature}_i \geq t$ দেওয়া হলে, $t \in \mathbb{R}$-এর জন্য সমস্ত সম্ভাব্য থ্রেশহোল্ড মানগুলির সমন্বয় অসীম।

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

স্প্লিটার দ্বারা সর্বাধিক স্কোর টাস্কের উপর নির্ভর করে। যেমন:

  • তথ্য লাভ এবং জিনি (উভয় পরে কভার) সাধারণত শ্রেণীবিভাগের জন্য ব্যবহৃত হয়।
  • গড় বর্গক্ষেত্র ত্রুটি সাধারণত রিগ্রেশন জন্য ব্যবহৃত হয়.

অনেকগুলি স্প্লিটার অ্যালগরিদম রয়েছে, যার প্রত্যেকটির জন্য বিভিন্ন সমর্থন রয়েছে:

  • বৈশিষ্ট্যের ধরন; উদাহরণস্বরূপ, সংখ্যাসূচক, শ্রেণীবদ্ধ, পাঠ্য
  • কার্য; উদাহরণস্বরূপ, বাইনারি শ্রেণীবিভাগ, বহু-শ্রেণীর শ্রেণীবিভাগ, রিগ্রেশন
  • অবস্থার ধরন; যেমন, থ্রেশহোল্ড কন্ডিশন, ইন-সেট কন্ডিশন, তির্যক কন্ডিশন
  • নিয়মিতকরণের মানদণ্ড; উদাহরণস্বরূপ, থ্রেশহোল্ড অবস্থার জন্য সঠিক বা আনুমানিক স্প্লিটার

এছাড়াও, মেমরি ব্যবহার, সিপিইউ ব্যবহার, গণনা বন্টন এবং আরও কিছু সম্পর্কিত বিভিন্ন ট্রেড-অফ সহ সমতুল্য স্প্লিটার ভেরিয়েন্ট রয়েছে।

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