Multi-label learning methods assign multiple labels to one object. In practice, in addition to differentiating relevant labels from irrelevant ones, it is often desired to rank <italic>relevant</italic> labels for an object, whereas the ranking of <italic>irrelevant</italic> labels is not important. Thus, we require an algorithm to do classification and ranking of relevant labels simultaneously. Such a requirement, however, cannot be met because most existing methods were designed to optimize existing criteria, yet there is no criterion which encodes the aforementioned requirement. In this paper, we present a new criterion, <sc>PRO Loss</sc>, concerning the prediction of all labels as well as the ranking of only relevant labels. We then propose ProSVM which optimizes <sc>PRO Loss</sc> efficiently using alternating direction method of multipliers. We further improve its efficiency with an upper approximation that reduces the number of constraints from <inline-formula><tex-math notation="LaTeX">$O(T^2)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mi>T</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="xu-ieq1-2908898.gif"/></alternatives></inline-formula> to <inline-formula><tex-math notation="LaTeX">$O(T)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>T</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="xu-ieq2-2908898.gif"/></alternatives></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math><alternatives><mml:math><mml:mi>T</mml:mi></mml:math><inline-graphic xlink:href="xu-ieq3-2908898.gif"/></alternatives></inline-formula> is the number of labels. We then notice that in real applications, it is difficult to get full supervised information for multi-label data. To make the proposed algorithm more robust to supervised information, we adapt ProSVM to deal with the multi-label learning with partial labels problem. Experiments show that our proposal is not only superior on <sc>PRO Loss</sc>, but also highly competitive on existing evaluation criteria.
Paper
Full text
Robust Multi-Label Learning with PRO Loss
Semantic Scholar · Computer Science · 2020
Abstract
Multi-label learning methods assign multiple labels to one object. In practice, in addition to differentiating relevant labels from irrelevant ones, it is often desired to rank <italic>relevant</italic> labels for an object, whereas the ranking of <italic>irrelevant</italic> labels is not important. Thus, we require an algorithm to do classification and ranking of relevant labels simultaneously. Such a requirement, however, cannot be met because most existing methods were designed to optimize existing criteria, yet there is no criterion which encodes the aforementioned requirement. In this paper, we present a new criterion, <sc>PRO Loss</sc>, concerning the prediction of all labels as well as the ranking of only relevant labels. We then propose ProSVM which optimizes <sc>PRO Loss</sc> efficiently using alternating direction method of multipliers. We further improve its efficiency with an upper approximation that reduces the number of constraints from <inline-formula><tex-math notation="LaTeX">$O(T^2)$</tex-math><alternatives>mml:mathmml:mrowmml:miO</mml:mi>mml:mo(</mml:mo>mml:msupmml:miT</mml:mi>mml:mn2</mml:mn></mml:msup>mml:mo)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="xu-ieq1-2908898.gif"/></alternatives></inline-formula> to <inline-formula><tex-math notation="LaTeX">$O(T)$</tex-math><alternatives>mml:mathmml:mrowmml:miO</mml:mi>mml:mo(</mml:mo>mml:miT</mml:mi>mml:mo)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="xu-ieq2-2908898.gif"/></alternatives></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math><alternatives>mml:mathmml:miT</mml:mi></mml:math><inline-graphic xlink:href="xu-ieq3-2908898.gif"/></alternatives></inline-formula> is the number of labels. We then notice that in real applications, it is difficult to get full supervised information for multi-label data. To make the proposed algorithm more robust to supervised information, we adapt ProSVM to deal with the multi-label learning with partial labels problem. Experiments show that our proposal is not only superior on <sc>PRO Loss</sc>, but also highly competitive on existing evaluation criteria.