Sequential minimal optimization
ಸೀಕ್ವೆನ್ಷಿಯಲ್ ಮಿನಿಮಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ (ಎಸ್ಎಂಒ) ಎಂಬುದು ಬೆಂಬಲ-ವಾಹಕ ಯಂತ್ರಗಳ (ಎಸ್ವಿಎಂ) ತರಬೇತಿಯ ಸಮಯದಲ್ಲಿ ಉದ್ಭವಿಸುವ ಕ್ವಾಡ್ರಾಟಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ (ಕ್ಯುಪಿ) ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದನ್ನು 1998 ರಲ್ಲಿ ಮೈಕ್ರೋಸಾಫ್ಟ್ ರಿಸರ್ಚ್ನಲ್ಲಿ ಜಾನ್ ಪ್ಲಾಟ್ ಕಂಡುಹಿಡಿದರು. ಎಸ್ಎಂಒಅನ್ನು ಬೆಂಬಲ ವಾಹಕ ಯಂತ್ರಗಳ ತರಬೇತಿಗಾಗಿ ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ ಮತ್ತು ಇದನ್ನು ಜನಪ್ರಿಯ ಎಲ್ಐಬಿಎಸ್ವಿಎಂ ಉಪಕರಣದಿಂದ ಕಾರ್ಯಗತಗೊಳಿಸಲಾಗುತ್ತದೆ. 1998 ರಲ್ಲಿ ಎಸ್. ಎಂ. ಓ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರಕಟಣೆಯು ಎಸ್. ವಿ. ಎಂ ಸಮುದಾಯದಲ್ಲಿ ಸಾಕಷ್ಟು ಉತ್ಸಾಹವನ್ನು ಸೃಷ್ಟಿಸಿದೆ, ಏಕೆಂದರೆ ಎಸ್. ವಿ. ಎಂ ತರಬೇತಿಗಾಗಿ ಈ ಹಿಂದೆ ಲಭ್ಯವಿದ್ದ ವಿಧಾನಗಳು ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾಗಿದ್ದವು ಮತ್ತು ದುಬಾರಿ ತೃತೀಯ ಕ್ಯೂ. ಪಿ. ಪರಿಹಾರಕಗಳ ಅಗತ್ಯವಿತ್ತು. ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆ ಡೇಟಾಸೆಟ್ (x1, y1),., (xn, yn) ನೊಂದಿಗೆ ಬೈನರಿ ವರ್ಗೀಕರಣದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ, ಅಲ್ಲಿ xi ಒಂದು ಇನ್ಪುಟ್ ವೆಕ್ಟರ್ ಮತ್ತು ಅದಕ್ಕೆ ಅನುಗುಣವಾದ ಬೈನರಿ ಲೇಬಲ್ ಆಗಿದೆ. ಸಾಫ್ಟ್-ಮಾರ್ಜಿನ್ ಬೆಂಬಲ ವೆಕ್ಟರ್ ಯಂತ್ರವನ್ನು ಕ್ವಾಡ್ರಾಟಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ತರಬೇತಿ ನೀಡಲಾಗುತ್ತದೆ, ಇದನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಎರಡು ರೂಪದಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಲಾಗುತ್ತದೆಃ ಇಲ್ಲಿ C ಒಂದು SVM ಹೈಪರ್ಪ್ಯಾರಾಮೀಟರ್ ಮತ್ತು K (xi, xj) ಕರ್ನಲ್ ಕಾರ್ಯವಾಗಿದೆ, ಇವೆರಡನ್ನೂ ಬಳಕೆದಾರರು ಪೂರೈಸುತ್ತಾರೆ; ಮತ್ತು ಅಸ್ಥಿರಗಳು ಲ್ಯಾಗ್ರೇಂಜ್ ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳಾಗಿವೆ. ಅಲ್ಗಾರಿದಮ್ ಎಸ್ಎಂಒ ಮೇಲೆ ವಿವರಿಸಿದ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಪುನರಾವರ್ತಿತ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಎಸ್ಎಂಒ ಈ ಸಮಸ್ಯೆಯನ್ನು ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾದ ಉಪ-ಸಮಸ್ಯೆಗಳ ಸರಣಿಯಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ನಂತರ ಅವುಗಳನ್ನು ವಿಶ್ಲೇಷಣಾತ್ಮಕವಾಗಿ ಪರಿಹರಿಸಲಾಗುತ್ತದೆ. ಲ್ಯಾಗ್ರೇಂಜ್ ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ರೇಖೀಯ ಸಮಾನತೆಯ ನಿರ್ಬಂಧದಿಂದಾಗಿ, ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕ ಸಮಸ್ಯೆಯು ಅಂತಹ ಎರಡು ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ನಂತರ, ಯಾವುದೇ ಎರಡು ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳಿಗೆ ಮತ್ತು, ನಿರ್ಬಂಧಗಳನ್ನು ಈ ಕೆಳಗಿನವುಗಳಿಗೆ ಇಳಿಸಲಾಗುತ್ತದೆಃ ಮತ್ತು ಈ ಕಡಿಮೆಯಾದ ಸಮಸ್ಯೆಯನ್ನು ವಿಶ್ಲೇಷಣಾತ್ಮಕವಾಗಿ ಪರಿಹರಿಸಬಹುದುಃ ಕನಿಷ್ಠ ಒಂದು ಆಯಾಮದ ಚತುರ್ಭುಜ ಕಾರ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಇದು ಸಮಾನತೆಯ ನಿರ್ಬಂಧದಲ್ಲಿನ ಉಳಿದ ಪದಗಳ ಮೊತ್ತದ ಋಣಾತ್ಮಕವಾಗಿರುತ್ತದೆ, ಇದನ್ನು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ನಿಗದಿಪಡಿಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನಂತೆ ಮುಂದುವರಿಯುತ್ತದೆಃ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗೆ ಕರುಶ್-ಕುಹ್ನ್-ಟಕ್ಕರ್ (ಕೆಕೆಟಿ) ಷರತ್ತುಗಳನ್ನು ಉಲ್ಲಂಘಿಸುವ ಲ್ಯಾಗ್ರೇಂಜ್ ಮಲ್ಟಿಪ್ಲೈಯರ್ ಅನ್ನು ಹುಡುಕಿ. ಎರಡನೇ ಗುಣಕವನ್ನು ಆರಿಸಿ ಮತ್ತು ಜೋಡಿಯನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸಿ. ಒಮ್ಮುಖವಾಗುವವರೆಗೆ 1 ಮತ್ತು 2 ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಿ. ಎಲ್ಲಾ ಲ್ಯಾಗ್ರೇಂಜ್ ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳು ಕೆಕೆಟಿ ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸಿದಾಗ (ಬಳಕೆದಾರ-ವ್ಯಾಖ್ಯಾನಿತ ಸಹಿಷ್ಣುತೆಯೊಳಗೆ), ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲಾಗಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಒಮ್ಮುಖವಾಗುವುದು ಖಚಿತವಾಗಿದ್ದರೂ, ಒಮ್ಮುಖದ ದರವನ್ನು ವೇಗಗೊಳಿಸಲು ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳ ಜೋಡಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಅನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ದೊಡ್ಡ ದತ್ತಾಂಶ ಸೆಟ್ಗಳಿಗೆ ಇದು ನಿರ್ಣಾಯಕವಾಗಿದೆ ಏಕೆಂದರೆ ಮತ್ತು ಗಾಗಿ ಸಂಭವನೀಯ ಆಯ್ಕೆಗಳಿವೆ. ದೊಡ್ಡ ಎಸ್ವಿಎಂ ಕಲಿಕೆಯ ಸಮಸ್ಯೆಗಳನ್ನು ಸಣ್ಣ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕಾರ್ಯಗಳ ಸರಣಿಯಾಗಿ ವಿಭಜಿಸುವ ಮೊದಲ ವಿಧಾನವನ್ನು ಬರ್ನ್ಹಾರ್ಡ್ ಬೋಸರ್, ಇಸಾಬೆಲ್ಲೆ ಗಯಾನ್, ವ್ಲಾಡಿಮಿರ್ ವಾಪ್ನಿಕ್ ಅವರು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಇದನ್ನು "ಚಂಕಿಂಗ್ ಅಲ್ಗಾರಿದಮ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ದತ್ತಾಂಶದ ಯಾದೃಚ್ಛಿಕ ಉಪವಿಭಾಗದೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ ಮತ್ತು ಆಪ್ಟಿಮಾಲಿಟಿ ಪರಿಸ್ಥಿತಿಗಳನ್ನು ಉಲ್ಲಂಘಿಸುವ ಉದಾಹರಣೆಗಳನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಸೇರಿಸುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ನ ಒಂದು ಅನನುಕೂಲವೆಂದರೆ, ಎಸ್ವಿಗಳ ಸಂಖ್ಯೆಯೊಂದಿಗೆ ಕ್ಯೂಪಿ-ಸಮಸ್ಯೆಗಳ ಸ್ಕೇಲಿಂಗ್ ಅನ್ನು ಪರಿಹರಿಸುವುದು ಅಗತ್ಯವಾಗಿದೆ. ನೈಜ ಜಗತ್ತಿನ ವಿರಳ ದತ್ತಾಂಶ ಸೆಟ್ಗಳಲ್ಲಿ, ಎಸ್. ಎಂ. ಓ. ಯು ಚಂಕಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಗಿಂತ 1000 ಪಟ್ಟು ಹೆಚ್ಚು ವೇಗವಾಗಿರುತ್ತದೆ. 1997 ರಲ್ಲಿ, ಇ. ಒಸುನಾ, ಆರ್. ಫ್ರಾಯಂಡ್ ಮತ್ತು ಎಫ್. ಗಿರೊಸಿ ಅವರು ಒಂದು ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು, ಇದು ಎಸ್ವಿಎಂಗಳಿಗೆ ಕ್ಯೂಪಿ ಕ್ರಮಾವಳಿಗಳ ಸಂಪೂರ್ಣ ಹೊಸ ಗುಂಪನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಈ ಪ್ರಮೇಯದ ಆಧಾರದ ಮೇಲೆ ದೊಡ್ಡ ಕ್ಯೂ. ಪಿ. ಸಮಸ್ಯೆಯನ್ನು ಸಣ್ಣ ಕ್ಯೂ. ಪಿ. ಉಪ-ಸಮಸ್ಯೆಗಳ ಸರಣಿಯಾಗಿ ವಿಂಗಡಿಸಬಹುದು. ಕರುಶ್-ಕುಹ್ನ್-ಟಕ್ಕರ್ (ಕೆಕೆಟಿ) ಷರತ್ತುಗಳನ್ನು ಉಲ್ಲಂಘಿಸುವ ಕನಿಷ್ಠ ಒಬ್ಬ ವ್ಯಕ್ತಿಯನ್ನು ಯಾವಾಗಲೂ ಸೇರಿಸುವ ಕ್ಯೂಪಿ ಉಪ-ಸಮಸ್ಯೆಗಳ ಸರಣಿಯು ಒಮ್ಮುಖವಾಗುವುದು ಖಚಿತವಾಗಿದೆ. ಚಂಕಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಪ್ರಮೇಯದ ಷರತ್ತುಗಳನ್ನು ಪಾಲಿಸುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಒಮ್ಮುಖವಾಗುತ್ತದೆ. ಎಸ್ಎಂಒ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಒಸುನಾ ಅಲ್ಗಾರಿದಮ್ನ ವಿಶೇಷ ಪ್ರಕರಣವೆಂದು ಪರಿಗಣಿಸಬಹುದು, ಅಲ್ಲಿ ಆಪ್ಟಿಮೈಸೇಶನ್ನ ಗಾತ್ರವು ಎರಡು ಮತ್ತು ಎರಡೂ ಲ್ಯಾಗ್ರೇಂಜ್ ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳನ್ನು ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಉತ್ತಮ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಮೂಲಕ ಆಯ್ಕೆ ಮಾಡಲಾದ ಹೊಸ ಮಲ್ಟಿಪ್ಲೈಯರ್ಗಳೊಂದಿಗೆ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಎಸ್ಎಂಒ ಅಲ್ಗಾರಿದಮ್ ಬ್ರೆಗ್ಮನ್ ವಿಧಾನಗಳು ಅಥವಾ ರೋ-ಆಕ್ಷನ್ ವಿಧಾನಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ಗಳ ಕುಟುಂಬಕ್ಕೆ ನಿಕಟ ಸಂಬಂಧ ಹೊಂದಿದೆ. ಈ ವಿಧಾನಗಳು ಕನ್ವೆಕ್ಸ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಸಮಸ್ಯೆಗಳನ್ನು ರೇಖೀಯ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಪರಿಹರಿಸುತ್ತವೆ. ಅವು ಪುನರಾವರ್ತಿತ ವಿಧಾನಗಳಾಗಿವೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಹಂತವು ಪ್ರಸ್ತುತ ಪ್ರೈಮಲ್ ಬಿಂದುವನ್ನು ಪ್ರತಿ ನಿರ್ಬಂಧದ ಮೇಲೆ ಯೋಜಿಸುತ್ತದೆ. ಕರ್ನಲ್ ಪರ್ಸೆಪ್ಟ್ರಾನ್ ಉಲ್ಲೇಖಗಳು ಆಪ್ಟಿಮೈಸೇಶನ್ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ವಿಧಾನಗಳು ಬೆಂಬಲ ವೆಕ್ಟರ್ ಯಂತ್ರಗಳನ್ನು ಸಹ ನೋಡಿ.